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:

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:

FμF FA μF A κ in α

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

\[ \kappa = \alpha \circ F\kappa \circ in^{-1} \]

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))))))