Re: good fusion

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

Jan-Willem Maessen 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..] 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@haskell.org http://www.haskell.org/mailman/listinfo/libraries