`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#filter>

--
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