[Haskell-cafe] More on performance
Henning Thielemann
lemming at henning-thielemann.de
Wed Jun 4 05:51:42 EDT 2008
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)
More information about the Haskell-Cafe
mailing list