good fusion (was Re: inits)

[Malcolm Wallace]

Udo Stenzel <u.stenzel at web.de> wrote:

> Malcolm Wallace wrote:
> > {-# RULES
> > "foldr2/both"   forall k z (g::forall c.(a->c->c)->c->c)
> >                            (h::forall c.(b->c->c)->c->c) . 
> >     foldr2 f z (build g) (build h) =
> >         g (\x _-> h (\y r-> f x y r) z) z
> > #-}
> 
> Looks wrong to me.  Somehow it doesn't feel right that the first
> argument to g doesn't use its sencond argument and I think, what you
> wrote is actually
> 
> 	foldr (f (head (build g))) z (build h)

I was a bit worried that might be the case, yes.

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

> Intuitively it feels
> right: the "loop" that drives the calculation is contained in the
> build, and it cannot call out to the other generator to just get one
> element.

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.

Regards,
    Malcolm