On Wed, 4 Jun 2008, Duncan Coutts wrote:
On Wed, 2008-06-04 at 09:32 +0200, Henning Thielemann wrote:
Now the difficult question: How to write the 'mean' function in terms of 'sum' and 'length' while getting the same performance?
There's another rather harder fusion transformation that notices when two left folds are demanded in the same strictness context and they fold over the same input list then they can be performed together.
sum = foldl (\s x -> s + x) 0 length = foldl (\l x -> l + 1) 0
mean xs = sum xs / length xs
So we must note that sum and length are demanded at the same time and since they are both foldl's will consume the whole of xs.
So we can merge the two foldl's into one just by tupling them up:
sumlength = foldl (\(s, l) x -> (s + x, l + 1)) (0, 0)
mean xs = s / l where (s, l) = sumlength xs
How about assisting the compiler with a helper function named 'parallel' ? parallel :: ([a] -> b, [a] -> c) -> [a] -> (b,c) parallel (f,g) xs = (f xs, g xs) mean xs = uncurry (/) $ parallel (sum,length) xs ? We could state RULES in terms of 'parallel'. By calling 'parallel', the user tells, that he wants fusion here. Say "parallel/foldl/foldl" forall f, g, x0, y0. parallel (foldl f x0, foldl g y0) = foldl (\(x,y) z -> (f x z, g y z)) (x0,y0)