inits

[Sebastian Sylvan]

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