good fusion

[Malcolm Wallace]

"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
multiple values.

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
> have.

In my scheme, there is a consistent representation, so I think it can be
deterministic.

Regards,
    Malcolm