good fusion (was Re: inits)

[Josef Svenningsson]

On 4/10/06, Malcolm Wallace <Malcolm.Wallace at cs.york.ac.uk> wrote:
> > Wasn't there some consensus that foldr/build
> > cannot deforest both lists that go into zip?
>
> I'd like to find out if that is indeed part of the folklore.
>
I'd rather call it an open research problem. But I think it is
generally considered as unlikely to be possible.

> Hmm, and yet, one also feels that it must be possible to generate items
> from multiple lists in "lock-step" (without the list structure), since
> that is exactly the pattern being expressed by the zipWith family.
>
I totally agree with your intuition. In fact, it is possible to
achieve fusion in this case, we just don't know how to do it within
the foldr/build setting.
<plug>
I couple of years ago I wrote a paper about it:
http://www.cs.chalmers.se/~josefs/publications/fusion.pdf
Readers digest: Using a variation on foldr/build (I call it the dual,
but that's stretching it a bit) zipWith can be a good consumer in both
its arguments at the same time. But this variation is unfortunately
incompatible with foldr/build.
</plug>

It'd be really cool if you managed to crack the problem, but be warned
that Smart People (read Simon Peyton :-) has tried hard and failed.

Cheers,

/Josef