Am I missing something about unfoldr?

David Feuer david.feuer at gmail.com
Fri Aug 15 05:24:50 UTC 2014


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 Aug 15, 2014 12:55 AM, "wren romano" <winterkoninkje at gmail.com> wrote:

> On Thu, Aug 14, 2014 at 10:44 PM, David Feuer <david.feuer at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140815/4c438780/attachment-0001.html>


More information about the Libraries mailing list