Seeking comments on proposed fusion rules

David Feuer david.feuer at
Thu Jul 31 18:38:00 UTC 2014

The rules:

The boring explanation:

As I mentioned earlier, we currently can't fuse things like

foldr (x : build g)

The foldr can't see the build. Earlier, I considered a simple
cons/build rule that would rewrite

x : build g


build (\c n -> x `c` g c n)

I wasn't quite satisfied with this approach, largely because it treats

foldr c n (x1 : x2 : ... : xn : build g)

one way, and

foldr c n ([x1, x2, ..., xn) : build g)

another way. The former expands out the foldr, while the latter (via
various rules involving augment) translates into a foldr over [x1, x2,
..., xn].

I therefore came up with the idea of translating x1:x2:...:xn:build g
into [x1:x2:..:xn]++build g, and then letting the current rules do
their thing. dolio and carter (in #ghc) were concerned about what
would happen if fusion *didn't* occur, in which case the resulting
code appears to be *worse*. So then I wrote some rules to fix that up,
which actually look likely to be good rules in general. They turn

[x1:x2:...:xn] ++ ys



I ended up having to do more that I had originally expected in my
rules, because they miss a phase they need (it may be possible to fix
that; I'm not sure, because I'm very new to this business); I left
comments showing each step of the translation. One thing of note is
that I ended up using (by hand) the augment/augment rule that is
commented out as probably not being useful.

In my limited testing, the rules seem to do what they're supposed to
(when I can understand the Core), and the profiler is very pleased.

More information about the Libraries mailing list