haskell at list.mightyreason.com
Mon Apr 10 13:00:59 EDT 2006
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. Barring fusion,
it is creating an extra list. The "scanl" makes a list, the "map" makes a list
and the "(f )" makes a list.
The helper function makes a list with "(f)" and with "(...):helper...".
> but this is also competitive:
> 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.
More information about the Libraries