Correction to one slide

[jwiegley]

Hi Tim! I met you at the London users group meeting where you gave the presentation on recursion schemes.

In the slide on catamorphisms, you write:

• for a list, it describes processing from the right
• for a tree, it describes a bottom-up traversal, i.e. children first

However, this is not correct. The list is processed from the left, with the "rest" argument being a thunk that evaluates to processing the remainder of the list. It's not that the list is actually processed from right to left, even though sometimes it's easier to read the code that way.

Likewise, for a tree, traversal is top-down, where at each node the children are presented to you as thunks that evaluate to continuing the recursion.

In order words, you have the option of examining only the first value with a catamorphism and ignoring the rest. From your description, it makes it sound like that first value would be the last member of the list, rather than the first.

[willtim]

Hi John,
Thanks for the feedback. I agree that "processing" is a confusing choice of word on my part, I did not intend to describe the operational semantics of foldr, which is as you describe for a non-strict language. I still believe that foldr and cata are best thought of as "bracketing" or "associating" from the right and bottom-up respectively, even though they are deconstructed left-to-right and top-down.
Tim

[willtim]

Slides updated

[jwiegley]

Thanks, @willtim. Since your presentation I've had occasion to use your ideas, and have found that they lead to very convenient evaluators. I refer to your slides often, and recommend them to people even more.

I'm heading to London Sep 7-21. Do you know if any Haskell meetups will be happening again?