Seeking comments on proposed fusion rules

[David Feuer]

On Thu, Jul 31, 2014 at 3:12 PM, Simon Peyton Jones
<simonpj at microsoft.com> wrote:
> Turning (:) into (++) feels like the wrong way round to me.
>
> What's wrong with rewriting
>         x : build g
> into
>         build (\cn. x `c` g c n)
> as you suggest?

Turning (:) into (++) *is* the wrong way around, but there is some
method to my madness. If you look in GHC.Base, you'll see the
following comments:

-- The foldr/cons rule looks nice, but it can give disastrously
-- bloated code when commpiling
--      array (a,b) [(1,2), (2,2), (3,2), ...very long list... ]
-- i.e. when there are very very long literal lists
-- So I've disabled it for now. We could have special cases
-- for short lists, I suppose.
-- "foldr/cons" forall k z x xs. foldr k z (x:xs) = k x (foldr k z xs)

Something similar would happen with the above rule if someone wrote

foldr c n $ this : is : a : very : long : prefix : of : precomputed :
values : the : rest : of : which : are : computed : live : build g

With the current rules, folding over that would actually fold over
that whole thing, with no fusion. With the simple rule above, you
presumably get the "disastrously bloated code" above. If you, today,
rewrote it as

foldr c n $ [this, is, ..., live] ++ build g

then a different set of rules comes into play, producing a fold over
[this, is, ..., live] and fusion on the end.

Although I suppose having two different translations for these two
equivalent things allows the programmer more power, I don't think it's
terribly intuitive. More importantly, anyone who currently does
something like that will end up with the potential bloated code
problem. I think there may even be some such code in arithmoi, but I
could be misremembering. What the more complicated set of rules does
(essentially) is make  foldr c n (this:is:...:live:build g)  act
pretty much the way that foldr c n ([this, is, ..., live] ++ build g)
 does today. As a special sort of case, the foldr/single rule will end
up turning

foldr c n (x : build g)

into

x `c` g c n

which is what currently happens with

foldr c n ([x] : build g)

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

Yes, I think it is.

David