<div dir="ltr"><div><div>I'm not sure about the theory of it, but if I load the module in GHCi and run<br>head $ last $ initsR [0..100000::Int]<br></div>I get a response *immediately*.<br>If I run<br>head $ last $ initsDL [0..100000::Int]<br>
</div>I wrote this email while waiting for that to complete, and gave up on it. There may be an asymptotic performance bug here.<br></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>
</blockquote></div><br></div>