Formal proposal: replace Data.List.inits

[Bertram Felgenhauer]

David Feuer wrote:
> I don't know why you're looking at initsHO, which is almost the same as
> initsR but slightly slower. Have you looked at initsQ (preferably
> implemented with scanl')? That's the one that fixes the bad cases.

No, because I looked at the wrong part of your mail. Adding timings:

> > - using only first elements of result lists:
> >
> > > sum' $ map head $ tail $ inits [1..10000]
> > 10000
> > (5.38 secs, 5905331504 bytes)
> > > sum' $ map head $ tail $ initsR [1..10000]
> > 10000
> > (0.55 secs, 1203045184 bytes)
> > > sum' $ map head $ tail $ initsHO [1..10000]
> > 10000
> > (1.11 secs, 1205462216 bytes)
> > > sum' $ map head $ tail $ initsT [1..10000]
> > 10000
> > (0.01 secs, 7226208 bytes)
> > > sum' $ map head $ tail $ initsT' [1..10000]
> > 10000
> > (0.01 secs, 8119224 bytes)
> sum' $ map head $ tail $ initsQ [1..10000]
10000
(0.01 secs, 7309616 bytes)
> sum' $ map head $ tail $ initsQ' [1..10000]
10000
(0.01 secs, 8908320 bytes)

All these results are pretty meaningless beyond demonstrating
that initsT and initsQ are sufficiently lazy.

> >
> > - using whole result:
> >
> > > sum' $ map sum' $ tail $ inits [1..10000]
> > 166716670000
> > (7.79 secs, 7900276296 bytes)
> > > sum' $ map sum' $ tail $ initsR [1..10000]
> > 166716670000
> > (1.35 secs, 2006560272 bytes)
> > > sum' $ map sum' $ tail $ initsHO [1..10000]
> > 166716670000
> > (1.93 secs, 2003170216 bytes)
> > > sum' $ map sum' $ tail $ initsT [1..10000]
> > 166716670000
> > (2.16 secs, 3603697344 bytes)
> > > sum' $ map sum' $ tail $ initsT' [1..10000]
> > 166716670000
> > (1.61 secs, 3603897320 bytes)

> sum' $ map sum' $ tail $ initsQ [1..10000]
166716670000
(3.30 secs, 3194869384 bytes)
> sum' $ map sum' $ tail $ initsQ' [1..10000]
166716670000
(3.26 secs, 3195015296 bytes)

I've also run some criterion benchmarks, see the html files at

  http://int-e.eu/~bf3/haskell/inits/

(Is there a way to get criterion to split the summary table in
its html output by groups?)

Inits.hs contains the various inits implementations.
inits.tar.gz contains everything.

Interestingly, initsQ looks better than initsT in these benchmarks.

Cheers,

Bertram