Jan-Willem Maessen
foldr can be expressed in terms of destroy: The converse does not seem to be true, destroy is strictly more expressive than foldr.
This is an intriguing question, and a way to get hackers like me interested...
Please hack away! I'm just a humble user with an application that is running too slowly due to lots of intermediate structures that the compiler won't throw away without some persuasion ...
we can indeed obtain a zipWith / unfoldr fusion rule
1) zip (unfoldr f z) (unfoldr g y) = unfoldr (hoist f g) (z,y) where hoist f g (z,y) = f z >>= \u -> g y >>= \v -> (u,v)
Yes, I worked something like this one out myself.
2) foldr g y (zip (unfoldr f z) xs) = foldr h (const y) xs z where h x k z = maybe y (\(v,w)-> g (x,v) (k w)) (f z) 3) as above, with arguments commuted.
These are the versions that deforest just one of the producers, like ghc already does.
We can squeeze reasonable-looking loops out of higher-order folds if we're willing to do a little bit of work. We do end up relying on transformations like worker/wrapper quite a bit to get rid of all those tuples... But that's what worker/wrapper is for.
What I'm wondering is whether the foldr/unfoldr rules are strictly better than foldr/build, in the sense that they work on all the same subjects, but foldr/unfoldr additionally tackles some situations (zipWith) that foldr/build does not. I'm guessing from what you say they are actually incomparable - each handles some situations the other does not.
Absolutely. The frustrating part: all those list transducers like reverse, take, drop, inits, tails... Some of them are expressible as folds or unfolds, but it's never terribly natural; we should expect the resulting code to be pretty awful. For these, either build or destroy seem to be indispensible.
Ah. In my application I have a lot of these (especially 'drop'). Udo Stenzel wrote:
I'd expect problems in situations with a single producer and multiple consumers, but those aren't currently deforested anyway.
Oops, my application has a lot of *those* as well! For instance, zipWith4 f xs (drop 1 xs) (drop line xs) (drop plane xs) Ideally, I want the work of computing xs to be shared, *and* for zipWith4 to be a tight loop, something like unfoldr generate xs where generate f s = (f (s!!0) (s!!1) (s!!line) (s!!plane), tail s) Note that the intermediate list for xs is still there, really just as a form of ad hoc memoisation buffer. It seems unlikely that deforestation could introduce e.g. a circular buffer or whatever technique you would use in an imperative setting. Maybe some other program-calculational technique is required for this. Graham Hutton has a nice way of deriving such machine-level operational concepts from pure code. His example is exception-handling, where you start with a functional specification of what it should mean, and the technique derives stack markers to implement it. I wonder if the same technique could derive the minimal sharing buffer for the arguments of zipWith? IIRC, first you de-functionalise the specification, then use the continuation-passing transform, then re-functionalise. I'll have to look it up. Regards, Malcolm