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 paperBy “meat of the paper”, I mean “the first two pages”. Have patience.
. We’ll define four simple recursion schemes, explore how they relate to each other, and I’ll offer up some example sitations (both real-world and contrived) of situations that admit the use of recursion schemes.
We’ll start by defining a simple syntax tree, as we did last time.
We define two root constructors to represent the leaf nodes of the tree (
String values respectively) and five other constructors. Every position in which subexpressions may appear—the left-hand and right-hand sides to a binary operation, the target of a unary operation, the function and arguments in a function invocation—is represented by a value of type
a, in terms of which Expr is definedIn other words,
Expr is an inductively-defined data type of kind
* -> *.
We use the
DeriveFunctor GHC extension to provide a definition of the
Functor typeclass for
Expr, which provides us with an
fmap f, applied to a given
f to each subexpression
a, and is the identity function when passed a
Ident value, as they contain no subexpressions.
At this point, we can represent expressions with no subexpressions with the type
Expr (); for expressions at most one level of subexpressions, we can use
Expr (Expr ()); for two,
Expr (Expr (Expr ()), and so on and so forth. What we want is to represent an arbitrarily-nested
Expr—in essence, an
Expr (Expr (Expr (Expr ...)))—but, since Haskell doesn’t support infinite types, we have to resort to a least-fixed-point combinator. We call this combinator
Term, with an
In constructor and an
out accessor function.
Now we represent arbitrarily-nestable
Expr values with values of type
Term Expr, obtained by applying the
In constructor with a constructor from
ExprPackages like compdata provide Template Haskell magic to avoid the syntactic clutter associated with applying the
In constructor everywhere: given our above definition of
Expr, we could use the
smartConstructors splice to generate
iUnary, etc. functions, each of which are straightforward compositions of the constructors of
Expr with the
In fixed-point operator. GHC’s support for pattern synonyms can also eliminate applications of
>>> operator for left-to-right function composition, we expressed a generalized bottom-up traversal capable of operating on any data type that implements the
While this is a pleasing and concise representation of bottom-up transformations, it’s not as powerful as it could be: specifically,
fn is limited to taking and returning a value of type
Term f. We could not use
bottomUp to count the total number of subexpressions in a tree (going from
Int), nor could we transform this tree to a DOM representation (
Node), nor could we render a term into a pretty-printed representation (
This is a direct result of the third step above: after recursing into the data structure with
fn in step #2, we stuff it into a
Term using the
In constructor in step #3 before passing it to
fn. This forces
fn to both take and return a
Term. What if we wrote a version of
bottomUp that omitted that particular call to
In? Does it typecheck?
You’re damn right it does:
Loading this function in
ghci and querying its type yields the following result:
mystery :: Functor f => (f a -> a) -> Term f -> a
Cool. How does this work?
Let’s take a closer look at that first parameter:
This is a function type, taking as input a containerThe purists in the audience are no doubt cringing at my use of “container” to describe the capabilities of a
Functor. As the Typeclassopedia points out, The
Functor class is broader than just the concept of containing values: the best phrase for a
Functor f => f a is “a value
a within some computational context
f. That doesn’t exactly roll off the tongue, though, so I will be using”container" throughout. Sorry, purists. (But I already lost the purists with my hand-wavy treatment of least-fixed-points and codata last time.)
f of values of type
a and returning a bare value of type
a. If we wanted to write a
countNodes function that counts (as an
Int) the number of subexpressions within a given
f would be equal to
Expr (which has a
Functor instance), and
a would be
The crucial element of understanding this function is its first parameter, here
Expr Int. It captures an
Expr in the process of transformation—because subexpressions (the
rhs field of
args fields of
Call) were represented as values of the parameterized type
a, we can capture the bottom-up nature of transformation in the type itself. This means that each case for
countNodes is easy to express: merely add 1 to the sum of all the contained subexpressions.
And our base case for this transformation falls out easily:
Ident have no subexpressions, so they just return 1:
mystery countNodes to our example
add(10, 10) datum should yield 4 (one for the identifier
add, one for the function call, and two for the . Does it?
I had a major mental block in understanding when, in fact, the
countNodes function was actually called, and how
mystery managed to recurse as deeply as possible into the passed structure. The key lies in the invocation of
fmap f applies
f to each subexpression within an
mystery starts out by recursing as deeply as possible into the
Term it is passed, since it calls itself recursively with
fmap. It’s almost magical how
mystery “knows” how to stop recursing—but it lies in the definition of
fmap mystery is the identity function over
Ident values, as they do not contain any subexpressions. At this point,
mystery stops recursing, applies the function
f, and returns into its previous invocations. As the stack unwinds,
fn gets applied to the next-highest node in the tree, then the next, then the next, until all the original
Expr values are gone and we yield only an
a. It all comes down to the capabilities of
fmap—from a straightforward purpose and declaration emerges a deep and subtle way to fold over a structure.
Indeed, functions of type
f a -> a are so ubiquitous that we refer to them by their own name:
When you see a value of type
Algebra f a, know that it’s a function from a container
f to a collapsed value
a. We could rewrite the type signature of the above
countNodes function to use it:
The use of the term “algebra” to in this context may seen a bit discomfiting. Most people use the term “algebra” to describe manipulating numerical expressions (as well as the associated drudgery of childhood math courses). Why are we overloading this term to represent a class of functions?
The etymology of “algebra” can shed some light on this—it stems from the Arabic root جبر, jabr, which means “restoration” or “reunion”. An algebra as a function that reunites a container of
f a—into a single accumulated
So, now that we have a grasp on what an algebra is and why we’re calling it that, let’s rewrite the type signature of
mystery using the
Algebra type synonym.
mystery function is known as a catamorphism, usually given the name
Again, though the term “catamorphism” may seem needlessly arcane, its etymology both simplifies and clarifies its purpose: the “cata” in “catamorphism” is the same “cata” in “catastrophe”, “catabolism”, and “catalyst”—from the Greek κατα, meaning “downwards”, “into”, or “collapse”. Just as a catastophe is an unlucky event that tears things down, and catabolism is the collapse of muscle fibers, a catamorphism uses an algebra (a reunion) to collapse a container of values into a single value.
If you’re reminded of the
fold operation on lists, you’re on the right track: a list fold (specifically
foldrDigression: Some of you may be wondering “if the catamorphism applied to lists is equivalent to
foldr, what’s the analogous construct for
foldl?” This is somewhat of a trick question, as
foldl can be expressed in terms of
foldr, as Oleg demonstrates.
) is merely a catamorphism limited to operate on lists (the
 type, the archetypal
Functor). That’s the essence of catamorphisms: they’re generalized fold operations, applicable to any functor—not just lists—all without having to write a line of boilerplate traversals and without sacrificing a mote of type safety.
Another excellent example of catamorphisms is pretty-printers for trees. If the representation you require of a tree type can be expressed in a purely bottom-up manner—that is to say, it requires no information about the original structure of the tree being transformed—you can express pretty-printing functions in a truly wonderfully concise manner. (Spoiler alert: later on, we’ll figure out how to do this even when you need access to the original structure.) We can describe a pretty-printing algebra from
Doc, an abstract document type provided by the Text.PrettyPrint module.
Again, expanding the type synonym yields us a function type, going from
Expr values containing
Doc values as their subexpressions, out to a final
Doc value. These values represent the leaves of the nodes that have already been pretty-printed.
Our base cases are straightforward:
And our inductively-defined cases are beautifully clutter-free:
prettyPrint (Call f as) = f <> P.parens (mconcat (P.punctuate "," as)) ---f(a,b...) prettyPrint (Index it idx) = it <> P.brackets idx ---a[b] prettyPrint (Unary op it) = (P.text op) <> it ---op x prettyPrint (Binary l op r) = l <> (P.text op) <> r ---lhs op rhs prettyPrint (Paren exp) = P.parens exp ---(op)
prettyPrint to our example
call datum should yield a nice representation:
One final detail: we can represent our
bottomUp function in terms of
bottomUp f is just
cata f, with the additional step of stuffing the accumulator value into a
In before handing it off to
This formulation of recursive traversals sure is elegant—but elegance isn’t enough. The real reason to use catamorphisms is that every catamorphism obeys a set of laws.This is assuming that we’re working in a purely functional language (and that nobody’s calling out to
The simplest law is the identity law:
This is pretty straightforwardThe
≍ symbol is Unicode’s
EQUIVALENT TO glyph, and is read as such. This wouldn’t be valid Haskell syntax, unless you defined a
≍ function of your own.
In constructor, which provides the fixed-point of a functor, is the simplest algebra: given a functor
f wrapping a
Term f, it turns it into a
Term f, leaving the value untouched. And iterating over the contents of a structure without changing them is clearly the identity function.
Catamorphisms can also fuse:
This is an extraordinarily powerful property of catamorphisms: in the above example, it allows you to avoid successive invocations of fmap.
Catamorphisms also compose: given an algebra over a given type
That is to say, the result of composing two separate catamorphisms is equivalent to a single catamorphism using the combination of the contained algebras. This is amazing, almost magically so: the composition law allows us to turn two separate calls to
cata into one.
In the last post, we defined a corresponding topDown method, the opposite of bottomUp. Furthermore, we did so by “reversing the arrows” in bottomUp: we changed the left-to-right composition operator
>>> to its flipped
<<< (which is equivalent to the
. operator), and we flipped around all invocations of
By applying this “reversing the arrows” trick, we managed to express the duality between bottom-up and top-down traversals. So what happens if we do the same to our definition of cata? Does it typecheck?
You’re damn right it does. What’s its type signature?
what :: (Functor f) => (a -> f a) -> a -> Term f
Just as when we yielded a top-down traversal by reversing a bottom-up one, we yield an unfold when we reverse the arrows in our generalized fold function. Again, let’s take a look at the type of the first parameter, the unfolding function:
Similar to our Algebra type
a -> f a, right? Exactly the same, except the direction of the function arrow has reversed: whereas algebras are mappings from
f a to
a, this new function type maps as to f as. We call this function type a coalgebra.
We call the what an anamorphism – the “ana” prefix, from the Greek “ἀνά” meaning “building”Anabolic steroids build muscle mass, anagenesis is the development (the building, in a sense) of new species, &c &c.
, is the opposite of “cata”, meaning “destruction”. Just like cata generalized fold from lists to any Functor, ana generalizes unfold to any Functor.
If we thought about algebras as reunions, we can think about coalgebras as disassembly or dispersion. We’re taking one established a value and stuffing it inside a context
f. If that
Maybe, then we’re allowing for the possibility that no value will be present; if that
f is a list data type, it means we’re allowing there to be zero or more results.
cata is a generalized version of the
foldr function on list values,
ana is a generalization of
unfoldr. In our previous examples, we used
cata to destroy a
Term Expr; here, we’ll use
ana to build one, consisting of
n nested values.
The case for
0 is our base case: the unfold process stops there, because
Literal nodes have no children: future invocations of
fmap on that
Literal node will not produce further recursion. The second case is our inductive case. Rather than an explicitly recursive call (e.g.
Paren (nested (n - 1))), we express the desired course of our recursion by passing that
n - 1 value directly inside a
Paren node. Remember that this
Coalgebra is ultimately yielding a value of type
Expr Int; by constructing that
Paren around an
Int, we specify that
ana should continue the unfold by recursing and carrying on subsequent iterations with
n - 1 as the seed value.
Was That Really So Hard?
Thanks to Colin Barrett and Rob Rix for reading drafts of this essay, and thanks to Rob for pushing me to publish it.
On a personal note, I am deeply grateful for all the comments I’ve received thus far, both complimentary and constructive.
In part 3, we explore the limits of catamorphisms, and address these limits with paramorphisms and apomorphisms.