inits

Tim Toorop timtoorop at quicknet.nl
Sat Apr 8 10:30:14 EDT 2006


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


More information about the Libraries mailing list