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

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…

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…

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…

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…

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