Malcolm.Wallace at cs.york.ac.uk
Tue Apr 11 12:28:19 EDT 2006
"Josef Svenningsson" <josef.svenningsson at gmail.com> wrote:
> First of all, I'm glad to see you've also discovered how fun it can be
> to do transformations of functional programs. This is real fun! :)
Yes, calculating new programs from old is fun, if somewhat mind-bending.
> there simply doesn't seem to be a way which
> maintains the initial simplicity of foldr/build and which enables
> significantly more fusion.
Perhaps you are right, but the phrase "open research question" invited
me to give it a try.
> So, what you demonstrate is that given that we have two functions,
> both represented as unfoldr, then they can be fused with zipWith even
> though it is represented as a foldr2. But if we try to imagine a more
> concrete scenario things become more problematic. Which two functions
> could those be? Suppose they were both map functions. That's fine, map
> can be represented as an unfoldr. But wait a second! If we want to use
> foldr/build then we want to represent map in terms of foldr and build
> - not unfoldr! Dang!
Well, the core of my idea is that instead of two stages, foldr/build or
destroy/unfoldr, there are really three: foldr/build/genUnfoldr. I
insist that, instead of writing good producers with just build, you must
use build + genUnfoldr. This applies equally to hand-written producers
and producers generated internally through RULES. There is still only
one type of good consumer: those that can fuse foldr with build:
"foldr/build" foldr f z (build g) = g f z
"foldr/unfoldr" foldr f z (build (genUnfoldr g s)) = genUnfoldr g s f z
But the crucial new thing is that, whilst there is no way to fuse
multiple ordinary 'build' generators into a single pass, you *can* fuse
'genUnfoldr' generators together, to get simultaneous generation of
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.
> And this is really the core of the problem with unifying foldr/build
> and destroy/unfoldr - which representation certain functions should
In my scheme, there is a consistent representation, so I think it can be
More information about the Libraries