Recursion Schemes, Part V: Hello, Hylomorphisms

Previous installments: 1, 2, 3, 4, 4½. Thus far, we’ve explored a myriad array of recursion schemes. Catamorphisms and anamorphisms fold and unfold data structures, paramorphisms and apomorphisms fold with additional information, and histomorphisms and futumorphisms allow us to fold using historical values and unfold with user-defined control flow.…

Recursion Schemes, Part 4½: Better Living Through Base Functors

In an effort to publish more than one blog post a year, I’ve decided to write about smaller topics. Today I’m going to talk about the notion of a ‘base functor’, and how the popular recursion-schemes library uses base functors to make recursion schemes more elegant and ergonomic…

Recursion Schemes, Part IV: Time is of the Essence

Though we’ve only just begun our dive into Bananas, Lenses, Envelopes, and Barbed Wire, the next natural step in understanding recursion schemes brings us outside its purview. We must turn our attention to a paper written seven years later—Primitive(Co)Recursion and Course-of-Value (Co)Iteration, Categorically, by Tarmo…

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,…