Seeking comments on proposed fusion rules

Simon Peyton Jones simonpj at
Thu Jul 31 19:12:24 UTC 2014

Turning (:) into (++) feels like the wrong way round to me.

What's wrong with rewriting
	x : build g
	build (\cn. x `c` g c n)
as you suggest?

Now, [x1,x2,x3] ++ ys
is just syntactic sugar for
     (x1 : x2 : x2 : []) ++ ys
and I suppose that optimising that into
	x1 : x2 : x3 : ys
is a good thing quite independent of the (x : build g) stuff isn't it?


| -----Original Message-----
| From: Libraries [mailto:libraries-bounces at] On Behalf Of David
| Feuer
| Sent: 31 July 2014 19:38
| To: Haskell Libraries
| Subject: Seeking comments on proposed fusion rules
| 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
| to
| 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
| into
| 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.
| _______________________________________________
| Libraries mailing list
| Libraries at

More information about the Libraries mailing list