Re: inits

On 4/8/06, Tim Toorop wrote:

Sebastian Sylvan wrote:

...

On 4/7/06, 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)

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@haskell.org http://www.haskell.org/mailman/listinfo/libraries

The length xs wont work on infinite lists.

Ah of course! /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862