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. -- Chris