Hi <div><br></div><div>I find it useful. I benchmarked it with criterion and your test file (see below) and it is a *lot* faster:</div><div><br></div><div><div>warming up</div><div>estimating clock resolution...</div><div>

mean is 3.776987 us (160001 iterations)</div><div>found 887 outliers among 159999 samples (0.6%)</div><div>  662 (0.4%) high severe</div><div>estimating cost of a clock call...</div><div>mean is 1.404134 us (27 iterations)</div>

<div>found 5 outliers among 27 samples (18.5%)</div><div>  1 (3.7%) low mild</div><div>  1 (3.7%) high mild</div><div>  3 (11.1%) high severe</div><div><br></div><div>benchmarking randAccess IndexList</div><div>mean: 2.614148 ms, lb 2.603860 ms, ub 2.642045 ms, ci 0.950</div>

<div>std dev: 79.90122 us, lb 33.73238 us, ub 165.6168 us, ci 0.950</div><div>found 13 outliers among 100 samples (13.0%)</div><div>  12 (12.0%) high severe</div><div>variance introduced by outliers: 25.781%</div><div>variance is moderately inflated by outliers</div>

<div><br></div><div>benchmarking randAccess list</div><div>mean: 42.62869 ms, lb 42.38446 ms, ub 43.48986 ms, ci 0.950</div><div>std dev: 2.088308 ms, lb 598.3515 us, ub 4.751391 ms, ci 0.950</div><div>found 3 outliers among 100 samples (3.0%)</div>

<div>  2 (2.0%) high severe</div><div>variance introduced by outliers: 47.437%</div><div>variance is moderately inflated by outliers</div><div><br></div><div>benchmarking seqAccess IndexList</div><div>mean: 6.347177 ms, lb 6.325560 ms, ub 6.369031 ms, ci 0.950</div>

<div>std dev: 111.3361 us, lb 102.5431 us, ub 123.4909 us, ci 0.950</div><div>variance introduced by outliers: 10.386%</div><div>variance is moderately inflated by outliers</div><div><br></div><div>benchmarking seqAccess list</div>

<div>collecting 100 samples, 1 iterations each, in estimated 207.9468 s</div><div>mean: 1.919024 s, lb 1.916933 s, ub 1.927423 s, ci 0.950</div><div>std dev: 19.69444 ms, lb 1.966086 ms, ub 46.74818 ms, ci 0.950</div></div>

<div><br></div><div><br></div><div>Maybe an elevator list is a nice name?</div><div><br></div><div>Greets,</div><div><br></div><div>Edgar </div><div><br></div><div><br></div><div><div>module Main where </div><div>import Criterion.Main </div>

<div>import System.Random</div><div>-- | Type of index wrapping an underlying list</div><div>data LI a = LI Int [LInode a]</div><div>data LInode a = LiNonLeaf (LInode a) (LInode a) | LiLeaf (LInode a) [a]</div><div><br></div>

<div>-- | Constructs index from specified list and fanout</div><div>fromList :: [a] -&gt; Int -&gt; LI a</div><div>fromList l fo =</div><div>  let topLevel = mkTopLevelNode l</div><div>      mkTopLevelNode l = LiLeaf (mkTopLevelNode (drop fo l)) l</div>

<div>      mkLevel plv = let lv = mkMidLevelNode plv</div><div>                    in lv : mkLevel lv</div><div>      mkMidLevelNode l = LiNonLeaf (mkMidLevelNode (nodeDrop fo l)) l</div><div>  in LI fo (topLevel : mkLevel topLevel)</div>

<div><br></div><div>-- drop i nodes from a linear node stream</div><div>nodeDrop :: Int -&gt; LInode a -&gt; LInode a</div><div>nodeDrop 0 n = n</div><div>nodeDrop i n = let i&#39; = i - 1</div><div>               in case n of</div>

<div>                    LiNonLeaf n&#39; _ -&gt; nodeDrop i&#39; n&#39;</div><div>                    LiLeaf    n&#39; _ -&gt; nodeDrop i&#39; n&#39;</div><div><br></div><div>-- | access specified element of underlying list using index to speed access</div>

<div>(!) :: LI a -&gt; Int -&gt; a</div><div>(!) (LI fo ns) i =</div><div>  let getLevel k (n : ns) = let (q,r) = k `quotRem` fo</div><div>                                l = if q == 0</div><div>                                      then n</div>

<div>                                      else parent $ getLevel q ns</div><div>                            in nodeDrop r l</div><div>      parent (LiNonLeaf _ p) = p</div><div>      (q, r) = i `quotRem` fo</div><div>      (LiLeaf _ l) = getLevel q ns</div>

<div>  in l !! r</div><div><br></div><div>a = [1 :: Int ..]</div><div>b = fromList a 4</div><div><br></div><div>testSequential hi = [(!) b n | n &lt;- [1,3..hi :: Int]]</div><div>testSequentialList hi = [a!!n | n &lt;- [1,3..hi :: Int]]</div>

<div><br></div><div>randAccess hi = </div><div>             let seed = 12345813</div><div>                 g = mkStdGen seed</div><div>                 lst = [1,3..hi]</div><div>                 lst&#39; = fromList lst 32</div>

<div>                 nIter = 1000</div><div>                 randR _ 0 = []</div><div>                 randR g n = let (a,g&#39;) = randomR (0, hi `div` 2 - 1) g </div><div>                                 n&#39; = n - 1</div>

<div>                             --in (lst!!a) : randR g&#39; n&#39;</div><div>                             in (lst&#39;!a) : randR g&#39; n&#39;</div><div>             in sum $ randR g nIter</div><div>-- main = putStrLn $ show $ randAccess</div>

<div><br></div><div>randAccessList  hi = </div><div>             let seed = 12345813</div><div>                 g = mkStdGen seed</div><div>                 lst = [1,3..hi]</div><div>                 nIter = 1000</div><div>

                 randR _ 0 = []</div><div>                 randR g n = let (a,g&#39;) = randomR (0, hi `div` 2 - 1) g </div><div>                                 n&#39; = n - 1</div><div>                             in (lst!!a) : randR g&#39; n&#39;</div>

<div>             in sum $ randR g nIter</div><div><br></div><div>main = let hi = 50000 in defaultMain [ bench &quot;randAccess IndexList&quot; (nf (randAccess) hi),</div><div>                     bench &quot;randAccess list&quot; (nf (randAccessList) hi),</div>

<div>                     bench &quot;seqAccess IndexList&quot; (nf (testSequential) hi),</div><div>                     bench &quot;seqAccess list&quot; (nf (testSequentialList) hi)</div><div>                    ]</div>
<div>
<br></div></div><div><br><div class="gmail_quote">On Sat, Sep 8, 2012 at 8:55 AM, Alex Stangl <span dir="ltr">&lt;<a href="mailto:alex@stangl.us" target="_blank">alex@stangl.us</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

Hi,<br>
<br>
I have written a small &quot;wrapper&quot; to speed random-access to a list. The<br>
usage scenario I have in mind is a &quot;stream&quot; computation yielding an<br>
infinite list, and I want to randomly access elements w/o having to<br>
traverse the entire list from the beginning for each access.<br>
<br>
I suspected something similar must already exist, but nothing I looked<br>
at seemed to do the trick. IntMap seems to want a finite input list.<br>
Ditto for the various array types, except possibly dynamic array.<br>
<br>
Attached is the list indexer I came up with, and a small test program<br>
(I swap the commented-out lines to switch btw. list &amp; list index tests).<br>
I am interested to hear any feedback on this -- whether it duplicates<br>
something that already exists, or whether there&#39;s a better approach, and<br>
comments on the code, etc. Also if somebody can suggest a better name<br>
(so as not to overlay the word index too much.) I&#39;ll publish it on<br>
hackage (or at least github) if people think it&#39;s useful. It sped up<br>
the program I initally wrote it for enormously.<br>
<br>
Thanks,<br>
<br>
Alex<br>
<br>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>