# Catamorphisms in Python

**24 Sep 2017, 14:07 • python, catamorphism**

*In functional programming, fixpoints of data types are used to define recursive types.
Let’s see an example of how one can use this technique in Python.*

As an example, let's take arithmetic expressions:

class Expr: pass class ExprConst(Expr): def __init__(self, x): self.x = x def __str__(self): return self.x.__str__() def fmap(self, f): return self class ExprPlus(Expr): def __init__(self, x, y): self.x = x self.y = y def __str__(self): return self.x.__str__() + "+" + self.y.__str__() def fmap(self, f): return ExprPlus(f(self.x), f(self.y))

To make things simple, we'll only consider constants and addition. Python has no static typing but we can think of `Expr`

as a generic class.
Note that it is functorial, since it has an `fmap`

method.
If we have a non-recursive expression tree (of depth at most 2), the following function can be used to evaluate it:

def alphaExpr(e): if isinstance(e, ExprConst): return e.x elif isinstance(e, ExprPlus): return e.x + e.y

This function together with a carrier, for example \(\mathbb{N}\), forms a so-called F-algebra, \((\mathbb{N},\alpha)\). But what we want is a function capable of evaluating recursive trees (of arbitrary depth). Looked at from a category-theoretic perspective, it turns out that what we need is the least fixpoint of the type, which we can represent as a functor like so:

\[ F(A) = 1 + A \times A \]where 1 is the terminal object, + is the coproduct and \(\times\) the product. The least fixpoint \(\mu F\) is an object such that \(\mu F \cong F\mu F\). Let's have a look at this diagram:

The morphism \(\kappa\) is the recursive evaluator we want. The morphism *in* can be defined in Python (called `Fix`

) as follows:

class Fix: def __init__(self, x): self.x = x def __str__(self): return "Fix<" + self.x.__str__() + ">"

It's important to note that by Lambek's lemma *in* is an isomorphism,
which means that it can be inverted and \(\kappa\) can be defined by

In Python, we have

def cata(a): return lambda x: a(x.x.fmap(cata(a)))

which is a generic function assigning a (unique) \(\kappa\) to any \(\alpha\).
It's unique because *in* is an initial algebra.

We can use the code, for example, as follows:

x = Fix(ExprPlus(Fix(ExprConst(1)), Fix(ExprPlus(Fix(ExprConst(2)), Fix(ExprConst(4)))))) print(cata(alphaExpr)(x))