jmaessen at alum.mit.edu
Thu Apr 13 10:13:22 EDT 2006
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
> 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
> 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.
> Note that the intermediate list for xs is still there, really just
> as a
> form of ad hoc memoisation buffer. It seems unlikely that
> 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
> 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.
> Libraries mailing list
> Libraries at haskell.org
More information about the Libraries