I've read the Short Cut paper. Note that what it describes as fold/unfold is completely unrelated to fusing foldr with unfoldr—they're talking about "unfold" in Wadler's sense, which is part of a program transformation. I just did work through what foldr/unfoldr fusion proper looks like—it looks like hyloList. This all works out very well with map/unfoldr as well. I don't think foldr/unfoldr makes for a proper "fusion framework", per se, because you can't use it to make fusing transformers like map. I believe, however, that bringing unfoldr into the foldr/build framework is still valuable, because it's a convenient way to generate lists, and, if wrapped in build, offers a limited but safe way to write good producers.
On Thu, Aug 14, 2014 at 10:44 PM, David Feuer <david.feuer@gmail.com> wrote:
> I think that "for lists" version is pretty much what I ended up with (I
> haven't worked through what all the others might be about yet). I don't
> understand the "fight" you refer to, unless you actually mean trying to
> implement both foldr/build and destroy/unfoldr at the same time.
Suppose that build does not exist. (Also that destroy does not exist.)
Now try to think about performing list fusion in a foldr/unfoldr
framework. What would that framework look like? how would it work?
Because both foldr and unfoldr use value-level fixedpoints, you run
into problems trying to make that foldr/unfoldr framework actually
work out. Don't take my word for it, go read some of the early papers
like A Short Cut to Deforestation (1993) by Gill, Launchbury, & Peyton
Jones, or The Concatenate Vanishes (1987) by Wadler, and then try to
work through implementing foldr/unfoldr.
This is a good chunk of why the foldr/build stuff in base has so many
explicitly non-recursive functions to decompose things into before
rewriting. The problem isn't that the inliner doesn't like recursive
functions, the problem is that fixedpoints get in the way of being
able to see what the terms are in order to rewrite them and that you
can't fuse away buffers when there's an impedance mismatch between
producers and consumers.
--
Live well,
~wren