[Haskell-cafe] More on performance

[Henning Thielemann]

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)