inits

Chris Kuklewicz haskell at list.mightyreason.com
Mon Apr 10 10:54:09 EDT 2006


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

-- 
Chris Kuklewicz



More information about the Libraries mailing list