On 4/10/06, Malcolm Wallace
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