Help with fusion rules and such

David Feuer david.feuer at gmail.com
Thu Aug 14 17:46:39 UTC 2014


I've worked out the basics of how to make more functions from
GHC.Base, GHC.List, and Data.List participate in foldr/build fusion,
but I could really use some help figuring out how to write the RULES
to accompany them. I have too little experience with GHC's
simplification process to manage this on my own, it seems. One
complication I recognize already:

REVERSE

reverse xs = build $ \c n -> foldl (\a x -> x `c` a) n xs

works as well as we can probably expect for fusion (it fuses nicely
with map and a modified unfoldr), but when it doesn't fuse, it ends up
duplicating its "worker" at the top level, potentially multiple times.
I tried to write a rule to rewrite that to a simpler version, but
that's complicated by the fact that foldl is INLINEd unconditionally.
I'm thinking maybe the "right" thing is to allow all this duplication
to happen, and then clean it up at the end ( see
https://ghc.haskell.org/trac/ghc/ticket/9441 ), but that will not
happen soon if it does at all.


More information about the ghc-devs mailing list