good fusion

[Udo Stenzel]

Malcolm Wallace wrote:
> Well, the core of my idea is that instead of two stages, foldr/build or
> destroy/unfoldr, there are really three: foldr/build/genUnfoldr.

As Josef already realized, foldr can be expressed in terms of destroy:

*> foldr c n xs = destroy foldrDU xs
*>   where foldrDU g y = case g y of
*>           Nothing -> n
*>           Just (x,y') -> c x (foldrDU g y')

The converse does not seem to be true, destroy is strictly more
expressive than foldr.  Similarly any unfoldr can be expressed as a
build:

*> unfoldr g y = build (unfoldrFB y)
*>   where unfoldrFB Nothing       c n = n
*>         unfoldrFB (Just (x,y')) c n = c x (unfoldrFB y' c n)

Using these definitions we get a foldr/unfoldr rule for free.  (Or do
we?  I'm leaving the details as an exercise.)  What we don't get is a
destroy/build rule, but that seems impossible anyway.

So to get maximum fusion, the general rule seems to be "prefer to write
producers in terms of unfoldr and consumers in terms of foldr".
However, the libraries of GHC have to be changed anyway.

> I'm still working out all the details - it may yet turn out that you
> quickly reach dead-ends where further fusion does not occur.  But I'm
> hoping that it is possible to express whole trees of computation
> (composition pipelines + branching at zipWith) rather than just
> pipelines, in the one framework.

That's my feeling, too.  But that should already be possible using
destroy/unfoldr alone.  Actually I can think of lots of interesting
consumers that (seem to) require destroy (foldl, zip, ReadP), but of no
interesting producers that would require build.  I'd expect problems in
situations with a single producer and multiple consumers, but those
aren't currently deforested anyway.


Regards,

Udo.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/libraries/attachments/20060411/b5e083dd/attachment.bin