<div dir="ltr">Good catch, the common inits and tails version of subsequences makes pretty heavy use of that, as do many of the uses of inits where you use it to get k-element substrings.<div><br></div><div>I'd be curious if an okasaki-style catenable output restricted deque could recover both efficient head access and reasonably efficient appends, but the overhead of that is probably way out of line with the performance at stake!</div>
<div><br></div><div>-Edward</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Jul 19, 2014 at 4:14 AM, Henning Thielemann <span dir="ltr"><<a href="mailto:schlepptop@henning-thielemann.de" target="_blank">schlepptop@henning-thielemann.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Am 19.07.2014 09:51, schrieb David Feuer:<div class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Background: I was looking at the code for Data.List.inits in<br>
base-4.7.0.0 (function renamed for clarity):<br>
<br>
initsDL                   :: [a] -> [[a]]<br>
initsDL xs                =  [] : case xs of<br>
                                   []      -> []<br>
                                   x : xs' -> map (x :) (initsDL xs')<br>
<br>
The recursive maps made me suspicious. I decided to try writing a<br>
different version:<br>
<br>
initsHO xs = map ($ []) (scanl q id xs)<br>
   where<br>
     q f x = f . (x:)<br>
<br>
I mentioned this on #haskell and noted that it would be a nice exercise<br>
to write it with less fancy function footwork using map reverse. rasfar<br>
responded (modulo naming) with<br>
<br>
initsR xs = map reverse (scanl q [] xs)<br>
   where<br>
     q acc x = x : acc<br>
</blockquote>
<br>
<br></div>
The 'map' gives efficient access to the first elements of the sub-lists, thus it seems that initsDL is faster than initsR when you access only prefixes of the sub-lists. E.g.<br>
<br>
Prelude> head $ last $ inits [0..10000000::Int]<br>
<br>
______________________________<u></u>_________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/libraries</a><br>
</blockquote></div><br></div>