GHC’s rewrite rules facility allows a user to easily add peephole optimizations.  It’s used to implement deforestation, where intermediate data structures are completely eliminated.

A trivial example involves mapping over a list twice.  Consider:

map (*2) (map (+10) [1..10])

Evaluated as written, a temporary list [11..21] would be created by the inner map, which would then be consumed by the outer map, resulting in [22,24..40].  One could fuse these two traverals by hand, resulting in

map ((*2) . (+10)) [1..10]

which does not compute an intermediate list.  A rewrite rule that performs this fusion automatically is defined in the rewrite rules documentation.

I was hoping to use rewrite rules to fuse more complicated expressions, such as the naive implementation of arithmetic mean of a list:

mylen xs = foldr (\_ a -> a+1) 0 xs
mysum xs = foldr (+) 0 xs
avg xs = mysum xs / mylen xs

Here, two traversals are made over the list, but the two traversals are not nested.

Fusing by hand, we get the following uglier code:

avg2 xs = sum / len
  where (sum, len) = foldr (\x (s,l) -> (s+x,l+1)) (0,0) xs

I tried the following rewrite rule in an attempt to fuse things like avg automatically:

{-# RULES
"foldr-fuse" forall c f g fs gs xs.
             c (foldr f fs xs) (foldr g gs xs) =
               let (v1,v2) = foldr (\x (a1,a2) -> (f x a1, g x a2)) (fs, gs) xs in c v1 v2
  #-}

GHC doesn’t like this:

$ ghc -O --make -ddump-simpl-stats -fforce-recomp list_fusion
[1 of 1] Compiling Main             ( list_fusion.hs, list_fusion.o )

list_fusion.hs:16:0:
   Rule foldr-fuse:
       Illegal expression: c
       in left-hand side: c (foldr f fs xs) (foldr g gs xs)
   LHS must be of form (f e1 .. en) where f is not forall'd

On #haskell, I was told that a general RULES pragma for doing this sort of fusion is probably not possible. Of course, I could specialize the rule for division, and this does indeed work, but it is not general-purpose. Specializing for division looks like this:

{-# RULES
"foldr-fuse" forall f g fs gs xs.
             (/) (foldr f fs xs) (foldr g gs xs) =
               let (v1,v2) = foldr (\x (a1,a2) -> (f x a1, g x a2)) (fs, gs) xs in (/) v1 v2
#-}
 
{-# INLINE mysum #-}
mysum xs = foldr (+) 0 xs
 
{-# INLINE mylen #-}
mylen xs = foldr (\_ a -> a+1) 0 xs
 
avg2 xs = mysum xs / mylen xs
 
main = do  print $ avg2 [1..10]

The INLINE pragmas are necessary to get the rewrite rule applied, since inlining and rewriting happen at the same time.  The output from GHC indicates that foldr-fuse was used to fuse the definition of avg2.

Is there some way to make the more general fusion rewrite rule work? If not, Template Haskell could probably be used, but then the fusion would not be transparent. One would have to write something like

avg2 xs = $(fuse [|mysum xs / mylen xs|])

with a suitably defined fuse function. Hmmpf.