good fusion (was Re: inits)

[Malcolm Wallace]

"Josef Svenningsson" <josef.svenningsson at gmail.com> wrote:

> The GHC documentation is rather clear at this point.
> The larger zipWiths are not listed as good producers, hence you cannot
> expect fusion to happen.

Thanks for the pointer, it was very useful.

So now, I am trying to write some RULES that will turn zipWith[3..n]
into both good producers and good consumers.  But to simplify a bit,
I'll first concentrate on improving the existing RULES for pair-wise
zipWith.  zipWith is essentially turned into a foldr2, and then
I see that GHC.Base has rules for consuming either of the lists via
the foldr/build mechanism:

    foldr2 f z (build g) ys
    foldr2 f z xs (build g)

but there is no rule for consuming both lists simultaneously.  Let's
have a go at defining it:

{-# RULES
"foldr2/both"   forall k z (g::forall c.(a->c->c)->c->c)
                           (h::forall c.(b->c->c)->c->c) . 
    foldr2 f z (build g) (build h) =
        g (\x _-> h (\y r-> f x y r) z) z
#-}

The intuition is that we run the first generator, g, to get x, then the
second generator, h, to get y, then apply the pairwise function f to x
and y, with r being the recursive call back into the next iteration.  If
either of the generators fails to produce a new element, we drop out of
the iteration through the z (nil) argument.

Does this look about right?

So the main problem now is that the type annotations for g and h in the
rule are not correct.  GHC insists that if the bound variable is
polymorphic, it must have a type signature.  The result type of both g
and h should be the same, yet the way it is written with separate
quantifications, they can be different, so the rule will not fire.  I
really want to quantify the 'forall c' at an outer level, but I don't
think there is a mechanism to do that?

Regards,
    Malcolm