`mapFB` is part of the fold-build definition of `map`, not `map` written with `foldr` and `build`. `map f xs` gets rewritten to `build (\c n -> foldr (mapFB c f) n xs)`. If you have two maps: map f (map g xs) => rewrite map map f (build (\c1 n1 -> foldr (mapFB c1 g) n1 xs)) => rewrite map build (\c2 n2 -> foldr (mapFB c2 f) n2 (build (\c1 n1 -> foldr (mapFB c1 g) n1 xs))) => rewrite fold/build build (\c2 n2 -> (\c1 n1 -> foldr (mapFB c1 g) n1 xs) (mapFB c2 f) n2) => beta reduce build (\c2 n2 -> foldr (mapFB (mapFB c2 f) g) n2 xs) Now the `mapFB` rule simplifies this to: build (\c2 n2 -> foldr (mapFB c2 (f.g)) n2 xs) It's possible that inlining and simplification of `mapFB` could have the same effect, but if it were inlined, then the rule that writes back into ordinary `map` would never fire: foldr (mapFB (:) f) [] = map f This rule matches exactly what the rewritten map-map looks like after `build` is inlined: build (\c2 n2 -> foldr (mapFB c2 (f.g)) n2 xs) => inline build foldr (mapFB (:) (f.g)) [] xs => rewrite mapList map (f.g) xs -- Dan On Tue, Jul 22, 2014 at 7:34 PM, David Feuer <david.feuer@gmail.com> wrote:

These rules seem ... weird. Why, for example, do we need a special mapFB/mapFB rule? Shouldn't map f . map g translate to a build/foldr/build/foldr, fuse to build/foldr, and then translate back to map? Is this a case of something that almost works but not quite, and that needs patching up for a lot of cases? On Jul 22, 2014 6:53 PM, "wren romano" <winterkoninkje@gmail.com> wrote:

...

On Tue, Jul 22, 2014 at 6:42 PM, David Feuer <david.feuer@gmail.com> wrote:

...

I'm looking for some help writing some translate/untranslate rules to implement fusion for a couple of basic functions (the ones I'm looking at right now are takeWhile and scanr, but there may be others). I have a translation for takeWhile that seems to be at least decent, and one for scanr that is completely untested. I've never mucked about with GHC RULES, however, so I don't even know where to begin.

Probably the best place to start is to take a look at the source for GHC.Base and GHC.List, in particular the rules for map and filter capture the overarching pattern of how to stage the different rules.

< http://hackage.haskell.org/package/base-4.7.0.1/docs/src/GHC-Base.html#map

...

< http://hackage.haskell.org/package/base-4.7.0.1/docs/src/GHC-List.html#filte...

...

-- Live well, ~wren _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

And -ddump-rule-firings shows you which rules fire And -ddump-rule-rewrites shows you the before-and-after for each rule that fires Simon | -----Original Message----- | From: Libraries [mailto:libraries-bounces@haskell.org] On Behalf Of | Henning Thielemann | Sent: 23 July 2014 09:06 | To: David Feuer; libraries@haskell.org | Subject: Re: Looking for help writing some GHC RULES | | Am 23.07.2014 00:42, schrieb David Feuer: | > I'm looking for some help writing some translate/untranslate rules to | > implement fusion for a couple of basic functions (the ones I'm | looking | > at right now are takeWhile and scanr, but there may be others). I | have | > a translation for takeWhile that seems to be at least decent, and one | > for scanr that is completely untested. I've never mucked about with | > GHC RULES, however, so I don't even know where to begin. | | It is helpful to watch the simplifier working. E.g. | | -ddump-simpl-stats | | shows you the rules that fired and | | -ddump-simpl | | shows the Core outputs, that the simplifier phase produce. | | _______________________________________________ | Libraries mailing list | Libraries@haskell.org | http://www.haskell.org/mailman/listinfo/libraries