good fusion

[Malcolm Wallace]

Jan-Willem Maessen <jmaessen at alum.mit.edu> wrote:

> > foldr can be expressed in terms of destroy:
> > The converse does not seem to be true, destroy is strictly more
> > expressive than foldr.
> 
> This is an intriguing question, and a way to get hackers like me  
> interested...

Please hack away!  I'm just a humble user with an application that is
running too slowly due to lots of intermediate structures that the
compiler won't throw away without some persuasion ...

> we can indeed obtain a zipWith / unfoldr fusion rule
> 
>    1) zip (unfoldr f z) (unfoldr g y) = unfoldr (hoist f g) (z,y)
>         where hoist f g (z,y) = f z >>= \u -> g y >>= \v -> (u,v)

Yes, I worked something like this one out myself.

>    2) foldr g y (zip (unfoldr f z) xs) = foldr h (const y) xs z
>         where h x k z = maybe y (\(v,w)-> g (x,v) (k w)) (f z)
>    3) as above, with arguments commuted.

These are the versions that deforest just one of the producers, like ghc
already does.

> We can squeeze reasonable-looking loops out of higher-order folds if  
> we're willing to do a little bit of work.  We do end up relying on  
> transformations like worker/wrapper quite a bit to get rid of all  
> those tuples...  But that's what worker/wrapper is for.

What I'm wondering is whether the foldr/unfoldr rules are strictly
better than foldr/build, in the sense that they work on all the same
subjects, but foldr/unfoldr additionally tackles some situations
(zipWith) that foldr/build does not.  I'm guessing from what you say
they are actually incomparable - each handles some situations the other
does not.

> Absolutely.  The frustrating part: all those list transducers like  
> reverse, take, drop, inits, tails...  Some of them are expressible as 
> folds or unfolds, but it's never terribly natural; we should expect  
> the resulting code to be pretty awful.  For these, either build or  
> destroy seem to be indispensible.

Ah.  In my application I have a lot of these (especially 'drop').

Udo Stenzel wrote:
> > I'd expect problems in
> > situations with a single producer and multiple consumers, but those
> > aren't currently deforested anyway.

Oops, my application has a lot of *those* as well!  For instance,

    zipWith4 f xs
               (drop 1 xs)
               (drop line xs)
               (drop plane xs)

Ideally, I want the work of computing xs to be shared, *and* for
zipWith4 to be a tight loop, something like

    unfoldr generate xs
  where
    generate f s =  (f (s!!0) (s!!1) (s!!line) (s!!plane), tail s)

Note that the intermediate list for xs is still there, really just as a
form of ad hoc memoisation buffer.  It seems unlikely that deforestation
could introduce e.g. a circular buffer or whatever technique you would
use in an imperative setting.

Maybe some other program-calculational technique is required for this.
Graham Hutton has a nice way of deriving such machine-level operational
concepts from pure code.  His example is exception-handling, where you
start with a functional specification of what it should mean, and the
technique derives stack markers to implement it.  I wonder if the same
technique could derive the minimal sharing buffer for the arguments of
zipWith?  IIRC, first you de-functionalise the specification, then use
the continuation-passing transform, then re-functionalise.  I'll have to
look it up.

Regards,
    Malcolm