good fusion (was Re: inits)
Malcolm.Wallace at cs.york.ac.uk
Mon Apr 10 10:40:02 EDT 2006
"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:
"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?
More information about the Libraries