Looking for help writing some GHC RULES

[Dan Doel]

`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 at 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 at gmail.com> wrote:
>
>> On Tue, Jul 22, 2014 at 6:42 PM, David Feuer <david.feuer at 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 at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
>>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140722/d62cd633/attachment-0001.html>