good fusion

[Jan-Willem Maessen]

On Apr 12, 2006, at 10:25 AM, Malcolm Wallace wrote:

> Jan-Willem Maessen <jmaessen at alum.mit.edu> wrote:
>> 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.

That is my present understanding, yes---all because there's a foldr/ 
build, a foldr/unfoldr, and a destroy/unfoldr, but no destroy/build.

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

Actually, take and drop aren't so hard (proving that my memory is  
indeed a bit fuzzy):

take n = map snd . filter ((<n).fst) . zipWith [0..]
drop n = map snd . filter ((>=n).fst) . zipWith [0..]

Where of course we write [0..] in unfoldr form.

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

Yes, multiple consumers are a problem, and RULES can't capture the  
most interesting cases.
If we transform the whole program into arrow-form we could turn all  
those binding constructs into function compositions and reason about  
them equationally, but I'm pretty sure that would *not* be an  
improvement in the average hacker's life.  Haven't seen Graham  
Hutton's work on exception handling, but it sounds like it has this  
flavor.  Cool, but very tricky.

-Jan

> 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
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries