ross:
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.
Ah! Looks like a bit like DList code, from a lib by Manuel Chakravarty: -- | a difference list is a function that given a list returns the original -- contents of the difference list prepended at the given list type DList a = [a] -> [a] -- | open a list for use as a difference list openDL :: [a] -> DList a openDL = (++) -- | create a difference list containing no elements zeroDL :: DList a zeroDL = id -- | create difference list with given single element unitDL :: a -> DList a unitDL = (:) -- | append a single element at a difference list snocDL :: DList a -> a -> DList a snocDL dl x = \l -> dl (x:l) -- | appending difference lists joinDL :: DList a -> DList a -> DList a joinDL = (.) -- | closing a difference list into a normal list closeDL :: DList a -> [a] closeDL = ($[]) Which I've used on occasion to write faster code when doing lots of appends. -- Don