inits

[Tim Toorop]

Tim Toorop wrote:
> Sebastian Sylvan wrote:
>> On 4/7/06, Spencer Janssen <spencerjanssen at gmail.com> 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)
>>>>       
>>> This function seems to perform significantly better.  For example, the
>>> program below takes about 15 seconds with the old inits, and only 3
>>> seconds with the new version (tested with GHC 6.4.1 and -O2).
>>>
>>>    
>>>> main = print $ sum $ map sum $ inits [1..7000]
>>>>       
>>> As this version performs much better and will work as a drop in
>>> replacement, I suggest that it be included in the hierarchical
>>> libraries.
>>>
>>>     
>>
>> That's quite a bit faster on my machine as well. I think the following
>> slight variation may be a bit clearer, though:
>> inits xs = [] : zipWith take [1..length xs] (repeat xs)
>>
>> -- 
>> Sebastian Sylvan
>> +46(0)736-818655
>> UIN: 44640862
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>>   
> The length xs wont work on infinite lists.
> So you can't do :
>   take 100 (length (inits [1..]))
>
> -- 
> Tim Toorop
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
Hmm.. that won't work anyway.
It should have been:   take 100 (inits [1..]) ,  ofcourse.
My bad.

--
Tim Toorop