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.