Recursion Schemes, Part III: Folds in Context

On the last episode of this exploration of recursion schemes, we defined the catamorphism, our first generalized fold operation over any recursive data structure. Catamorphisms admit a beautiful definition and are useful in hosts of situations. But they have their limits: in this installment, we'll explore these limits, and we'll…

Recursion Schemes, Part II: A Mob of Morphisms

On the last episode of this very-infrequently-updated analysis of Programming with Bananas, Lenses, Envelopes, and Barbed Wire, we took a look at how to represent and traverse nested structures. This time, we’ll start getting into the meat of the paper1. We’ll define two simple recursion schemes, explore how…

An Introduction to Recursion Schemes

In 1991, Erik Meijer, Maarten Fokkinga, and Ross Paterson published their now-classic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Though this paper isn’t widely known outside of the functional programming community, its contributions are astonishing: the authors use category theory to express a set of simple,…