inits

[Tim Toorop]

Chris Kuklewicz wrote:
> Simon Marlow wrote:
>   
>> Spencer Janssen wrote:
>>     
>>> Earlier today on the #haskell IRC channel, Tim Toorop (bolrod on
>>> #haskell) pointed out that Data.List.inits is rather slow, and
>>> proposed an alternative.  After some collabrative tweaking, we came up
>>> with the following:
>>>
>>>
>>>       
>>>> inits xs = [] : (zipWith take [1..] $ map (const xs) xs)
>>>>         
>> I propose to replace inits in Data.List with this one.  Objections about
>> the relaxed strictness are noted, but I subscribe to the view that the
>> original is more strict than necessary, and the general trend for
>> Data.List functions is to be as lazy as possible.
>>
>> Cheers,
>>     Simon
>>     
>
> If the goal is speed, then this definition is running over 10% faster with ghc
> -O2 on my powerbook for (sum $ map length $ inits [1..10000])
>
> inits' = helper id
>     where helper f [] = (f []):[]
>           helper f (x:xs) = (f []):helper (f.(x:)) xs
>
>   
Seems to be quite faster in some cases!
Though other cases it's a bit slower.
Probably depends on the thing you want to use the inits for which one 
might be better.
Though with getting the actual contents of inits (like with sum $ map 
sum $ intis)  yours sure is faster!

--
Tim Toorop