inits

[Ross Paterson]

On Mon, Apr 10, 2006 at 06:00:59PM +0100, Chris Kuklewicz wrote:
> Ross Paterson wrote:
> > On Mon, Apr 10, 2006 at 03:54:09PM +0100, Chris Kuklewicz wrote:
> >> If the goal is speed, then this definition is running over 10% faster with ghc
> >> -O2 on my powerbook for (sum $ map length $ inits [1..10000])
> >>
> >> inits' = helper id
> >>     where helper f [] = (f []):[]
> >>           helper f (x:xs) = (f []):helper (f.(x:)) xs
> > 
> > I rather like
> > 
> > 	inits = map ($ []) . scanl (.) id . map (:)
> 
> That takes 3 times longer than the helper function definition.

Sorry, I meant it appeals to my perverse sense of aesthetics.  It is of
course the de-fused version of helper.

> > 	inits = map reverse . scanl (flip (:)) []
> 
> I would never try "reverse" when looking for performance, but that runs at the
> same speed as the helper and allocates the same amount of space.

It's not really surprising: the nested composition built by helper is
essentially a list, which is traversed by ($ []).  If scanl were defined
using build it might run a tiny bit faster.