Recursion Schemes

A nice saturday morning, I’m drinking my tea browsing YouTube when a video pops up:

• Rust and the price of ignoring theory.

Putting to the side that this is probably one of the most well-made commentaries about programming languages I’ve ever seen, he mentioned something which threw me into a rabbit hole for the rest of the day and I am now writing this at 7PM on that same Saturday. I’m talking about hylomorphisms – he talks about them at 6:26 – he defines them as follows:

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo f g = f << fmap (hylo f g) << g

Which already looks pretty interesting. Digging deeper into what a “hylomorphism” is, I arrived at the following nLab article: Recursion Scheme. This article details the hylomorphism as:

a recursive $F$-coalgebra $(c, X)$ has a unique mapping – the hylomorphism – $f : X \to Y$ into any other $F$-algebra $(Y, a)$ such that $f = a \circ F (f) \circ c$.

This seems way too terse to make sense. So let’s take it apart piece by piece. First, the most important part is that the hylomorphism is a supposedly unique mapping. Second, this mapping is constructed from three parts:

• an endofunctor $F : \mathcal{C} \to \mathcal{C}$
• a morphism $a : F(Y) \to Y$ (called an “algebra”)
• a morphism $c : X \to F(X)$ (called a “co-algebra”)

We can already start to write this in Haskell:

type Algebra f y = f y -> y
type CoAlgebra f x = x -> f x

In Haskell, all functors are endofunctors, so that property is trivially satisfied. So then, if we want to construct a hylomorphism, we can just use that same definition from nLab:

hylo a c = a . fmap (hylo a c) . c

That’s it. The hylomorphism is called a “recursion scheme”. Now, to continue talking about recursion schemes, we need to take a brief detour to polynomial functors and algebras.

Algebra

I will assume some familiarity with abstract algebra here, specifically the basic definition for groups. Now, we know that a group is a set of objects $G$ with an operation $* : G \times G \to G$ that satisfy the group axioms:

1. The set $G$ contains an identity $e$ such that $e * g = g * e = g, \forall g \in G$.
2. The set $G$ contains, for every element $g \in G$ an inverse $h \in G$ such that $g * h = e$.
3. The operation is associative, such that $\forall a, b, c \in G$ we have that $a * (b * c) = (a * b) * c$.
4. The operation $* : G \times G \to G$ is total, such that $\forall g, h \in G$ we have that $g * h$ is defined.

In Category Theory, we try to take this data and make a functor out of it. So, for now let’s assume that we are working in a Cartesian closed category. This means that for every two objects $A, B \in \mathcal{C}$ we can create:

• the product of the two: $A \times B \in \mathcal{C}$
• the coproduct of the two: $A + B \in \mathcal{C}$
• the exponential object of the two: $A^B \in \mathcal{C}$

Taking the group data, we can look at the set as an object $G$ and the operation as an object of type $G^{G \times G}$. Putting the set and operation objects together we get a third object of type $G + G^{G \times G}$. Additionally, there’s a specific element of $G$ that is supposed to be the identity. This is then a singleton set ${e}$ which I will denote as $\mathbb{1}$. Putting this together we get the object $G + G^{G \times G} + \mathbb{1}$. Now, to encode inverses, recall that we can create a bijective mapping between $G$ and the inverses of $G$. This means that the inverses of $G$ can be encoded as $G^G$. Finally, the functor we get is:

We can then take this, and turn it into a functor:

Hence, the name “polynomial functor”. We have just constructed a polynomial-like expression out of products, coproducts and exponentials which means that this is also a functor. This is obviously missing the axioms relating to the operation like associativity and totality but I won’t get into the nitty-gritty about that. Then, we can encode arbitrary groups as $\text{Group}(G)$.

An object of type $\text{Group}(G)$ as an expression like for example: $a * (b * c) * ((c * d) * e) * e$. If we know how to evaluate this expression, we can take this expression and turn it into an object $h = \text{eval}(a * (b * c) * ((c * d) * e))$ and we know that $h \in G$ because of the previous axioms. So, we know that $\text{eval}$ must be a morphism of type $\text{eval} : \text{Group}(G) \to G$. This morphism: $\text{eval}$ is what is commonly called “an $F$-algebra” (along with the object $G$).

More generally, a morphism $a : F(X) \to X$ with $X$ an object where $F$ is a polynomial functor is called an $F$-algebra. In this case $X$ is called the “carrier object” and $a$ is called “the algebra”. One can view the algebra as “evaluating” expressions of type $F(X)$ and simplifying them to just $X$. Because this is Category Theory, we can also flip the arrows. In this case we’d get a morphism of the form $c : X \to F(X)$, in this case it’s called a “coalgebra” (unsurprisingly).

Other Recursion Schemes

Now, on that same “recursion schemes” page, there is also a mention of “catamorphisms” and “anamorphisms” but an implementation for these is not provided.

1. A catamorphism (a.k.a. a fold) is the unique $F$-algebra homomorphism from an initial algebra for the functor $F$.
2. An anamorphism (a.k.a. unfold) is the unique $G$-coalgebra homomorphism into the final coalgebra for the functor $G$.

Now let’s try and do the same strategy we did with hylomorphisms here; first focusing on catamorphisms. First, we need to know what an initial algebra for a functor $F$ is. Second, we need to find out what the unique “F”-algebra homomorphism is. Initial and final algebras for an endofunctor $F : \mathcal{C} \to \mathcal{C}$ come from finding the fixed-point of that functor.

Fixed points

In Mathematics, the concept of a fixed point for a function $f : A \to A$ is an element of $a \in A$ such that $f(a) = a$. This can be thought of as $f$ sending $a$ to $a$, it’s not “doing anything” to $a$, it is leaving it “untouched” or in other words “fixing it”. We can apply this same logic to functors. The fixed point for a functor $F$ is an object $A$ such that $F(A) \cong A$.

Some functions might have many fixed points, others might have no fixed points. In the same vein, in some categories, fuctors don’t have fixed points. Which immediately becomes a problem when we want to find the supposedly “unique $F$-algebra homomorphism from an initial algebra”. This changes our perspective, instead of saying that $a$ is a fixed point of $f$, we’d like to know whether we can “find a fixed-point” for any $f$. An intuitive way of finding a fixed point for a function is to repeatedly evaluate it on the result of previous evaluations. In other words, doing something like this $f(f(f(f(f(\dots)))))$. If you were to do that infinitely many times, and in the case when $f$ does indeed have a fixed-point, you’ll eventually find that the result of all of that is just the fixed-point $a$.

Now coming back to functor-land, what object should you initially evaluate $F$ on? The definition specifies that there is an initial algebra and a final coalgebra, this is related to that first object with which you evaluate $F$ on. In some categories, there is an initial object and a final object in the category. When building a terminal coalgebra, you evaluate $F$ on the terminal object – usually denoted as $\mathbb{1}$ –, likewise for initial algebras.

This is where programming languages come in and in this case. Recall the nlab entry for recursion schemes:

most functional programming languages are endowed with an unrestricted fixed-point operator at all types, which simplifies the implementation of the language, but allows the user to write functions that are not-well defined mathematically

In Haskell, the category is called $\mathbf{Hask}$, you can think of types in $\mathbf{Hask}$ as sets with the added information that they all have an element in them called $\bot$ which you can think of as the value that is returned from functions that don’t return. This is because all functions can technically be written in such a way that they don’t return, and figuring out which functions do and don’t return is an open problem. This means, that the set with one object – which is usually considered to be the terminal object – is the set $\{\bot\}$.

-- this type has no values
data Void

bot :: Void
bot = bot -- this function infinitely recurses and never returns, hence it is of type Void

Then, the initial object is an object that has a morphism of type

ini :: Initial -> a

But look at this:

absurd :: Void -> a
absurd a = case a of {}

As it turns out, since there are no values in Void, this morphism is basically defined as “don’t return anything” but not “returning anything” is still returning something of type a. Namely, what is returned from here is simply the value $\{\bot\}$ which never returns. Try it yourself:

absurd bot -- this will never return

So, this initial algebra and terminal coalgebra in $\mathbf{Hask}$ are actually equal. In Haskell, the fixed-point of a functor is defined as:

newtype Fix f = In { out :: f (Fix f) }

This is related to the above part where I mentioned that in order to find a fixed-point for a function one would recursively evaluate the function until you get something that is equal to its input. This is nice and all, but we lose the categorical semantics about initial algebras and terminal coalgebras. That does not mean that we can’t make a distinction of sorts between them, it just won’t be recognized by the compiler. In this case we get:

-- initial algebra
newtype Mu f = Mu { unMu :: f (Mu f) }

-- terminal coalgebra
newtype Nu f = Nu { unNu :: f (Nu f) }

Example 1: The Maybe functor

What is the fixed-point of the Maybe functor? First, the definition for the Maybe fuctor I’ll be using:

data Maybe a = Nothing | Just a

The Nothing side is just the singleton set $\mathbb{1}$ and the Just a is the object $a$. As we saw previously, the alternative is represented with a $+$ (coproduct). This definition is equivalent to the polynomial functor:

Looking at Maybe as a polynomial functor will prove immensely useful when calculating its fixed-point. Then, if we apply Fix to this, we get:

Fix Maybe = Maybe (Fix Maybe)

Unwrapping that Maybe we get this:

Fix Maybe = Nothing | Just (Fix Maybe)

Now, let’s continue this process of substitution and unwrapping:

Fix Maybe = Nothing | Just (Fix Maybe)
    = Nothing | Just (Maybe (Fix Maybe))          -- unwrapped
    = Nothing | Just (Nothing | Just (Fix Maybe)) -- substituted
    = Nothing | Just Nothing | Just (Fix Maybe)   -- simplified
    = Nothing | Nothing | Just (Fix Maybe)        -- simplified
    .
    .
    .
    = Nothing | Nothing | Nothing | ...

If we look at each of these steps as a polynomial functor, then we get:

The fixed point of the Maybe functor is the natural numbers!

Catamorphisms

1. A catamorphism (a.k.a. a fold) is the unique $F$-algebra homomorphism from an initial algebra for the functor $F$.

Now, we can finally talk about catamorphisms. Let’s start by writing some code. We know that it must go from the initial algebra of the functor $F$ to whatever the “carrier object” is for the initial algebra that was supplied. So, we’re constructing a catamorphism:

buildCata :: Functor f = Algebra f a -> Mu f -> a
buildCata alg = undefined

We now need to construct this supposedly unique morphism. Notice something here:

    cata alg :: Mu f -> a
    fmap (cata alg) :: f (Mu f) -> f a

And we have:

    unMu :: Mu f -> f (Mu f)

We can put them together like this:

fmap (cata alg) . unMu :: f a

We’re almost there, the catamorphism returns something of type a, not f a. Luckily, recalling the definition of an algebra being a morphism f a -> a we can just do the following:

buildCata :: Functor f = Algebra f a -> Mu f -> a
buildCata alg = alg . fmap (cata alg) . unMu

Anamorphisms

2. An anamorphism (a.k.a. unfold) is the unique $G$-coalgebra homomorphism into the final coalgebra for the functor $G$.

In the previous step whatt we did was:

1. unwrap the Mu
2. fmap (cata alg)
3. apply the algebra to that

Anamorphisms are supposed to be the dual of this, so we should do the opposite of this:

buildAna :: Functor f => CoAlgebra f a -> a -> Nu f
buildAna coalg = Nu . fmap (ana coalg) . coalg

Recursion Schemes 2

If you search on Google for hylomorphisms, you’ll most likely arrive at the Wikipedia article for the hylomorphism definition used in Philosophy. The disambiguation page takes you to the actual computer science definition of a hylomorphism. In there, we can see a third definition for a hylomorphism:

a hylomorphism is a recursive function, corresponding to the composition of an anamorphism (which first builds a set of results; also known as ‘unfolding’) followed by a catamorphism (which then folds these results into a final return value).

Then, the hylomorphism is really just the mix of a catamorphism and anamorphism. How can we put the previous things together to achieve this? Well, first we need a mapping between Nu and Mu because I’ve been making the distinction between those but really they are equal and interchangeable in $\mathbf{Hask}$. Here’s that interchange:

nuToMu :: Functor f => Nu f -> Mu f
nuToMu (Nu x) = Mu $ fmap nuToMu x

Now, for that definition of hylomorphism, finally get that:

buildHylo :: Functor f => Algebra f b -> CoAlgebra f a -> a -> b
buildHylo alg coalg = cata alg . nuToMu . ana coalg

This definition also lets us trivially flip the arrows and get something that’s called a “metamorphism”:

meta :: Functor f => Algebra f a -> CoAlgebra f a -> Mu f -> Nu f
meta alg coalg = ana coalg . cata alg

Let’s finally see this in action. Say we want to compute the factorial of an integer. This creates a data structure on the stack sort of like this:

Notice how it expands into a huge structure and then collapses? This is exactly what the hylomorphism does for you. It expands a structure using the anamorphism and then collapses it using the catamorphism. First, we need to represent how computations look like inside a data structure:

data Computation b a = Return | Compute b a deriving Functor

Now, we need to define the algebra that evaluates a computation and the coalgebra that generates the computation. Those would look like this:

factAlg :: Computation Integer Integer -> Integer
factAlg Return = 1
factAlg (Compute n prod) = n * prod

factCoAlg :: Integer -> Computation Integer Integer
factCoAlg 0 = Return
factCoAlg n = Compute n (n - 1)

Now, we can construct the factorial hylomorphism:

fact :: Integer -> Integer
fact = buildHylo factAlg factCoAlg

The cool thing about this is that the data structure is actually never created and the compiler know that this computation can trivially be turned into a loop. So using hylomorphisms are super powerful, you can represent any computation with them. The compiler knows what to do with hylomorphisms and all you have to do is write the algebra and coalgebra.