good fusion (was Re: inits)
josef.svenningsson at gmail.com
Mon Apr 10 13:22:31 EDT 2006
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.
I couple of years ago I wrote a paper about it:
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.
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.
More information about the Libraries