Malcolm.Wallace at cs.york.ac.uk
Wed Apr 12 10:25:02 EDT 2006
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
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
> 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
> 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
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.
More information about the Libraries