Finite trees as initial algebra

In the last Theory Lunch session I talked about a category theoretic approach to finite trees. I presented an interesting procedure in the analysis of syntax and semantics of programming languages and formal languages in general, that is to focus the attention on the abstract representation of the syntax as the initial object in the category of algebras for an endofunctor. In this way any object in the category can be seen as a possible interpretation of the syntax and the unique morphisms from the initial algebra, usually called catamorphisms, can be seen as meaning functions.

A signature is a ranked alphabet $\Sigma$ , i.e. $\Sigma$ is a set together with a function $\rho : \Sigma \rightarrow \mathbb{N}$ called arity. The elements of $\Sigma$ are called function symbols.
A tree on the signature $\Sigma$ is a partial function $t : \mathbb{N}^* \rightharpoonup \Sigma$ such that

$\varepsilon \in Dom(t)$ ;
if $\alpha, \beta \in \mathbb{N}^*, \alpha\beta \in Dom(t)$ then $\alpha \in Dom(t)$ ;
if $t(\alpha) = f$ then, for every $i \in \mathbb{N}$ , $\alpha i \in Dom(t)$ iff $i \le \rho(f)$ .

As an example consider what follows. Let $\Sigma = \{ a,b,c,d,e \}$ with $\rho(a) = 2, \rho(b) = \rho(c) =1, \rho(d) = \rho(e) = 0$ . A possible tree on $\Sigma$ is $t(\varepsilon) = a, t(0) = b,$ $t(00) = d, t(1) = c, t(10) = c, t(100) = e$ . We represent this tree as the string $a(bd,cce)$ . In general we represent a tree with root $f$ and direct subtrees $t_1,\dots,t_{\rho(f)}$ as $f(t_1,\dots,t_{\rho(f)})$ . Note that every tree on $\Sigma$ can be represented in this way. We call $M(\Sigma)$ the set of finite trees on the signature $\Sigma$ .

Let $\mathcal{C}$ be a category and $F: \mathcal{C} \rightarrow \mathcal{C}$ an endofunctor. An algebra for $F$ is a pair $(A,a)$ where $A$ is an object of $\mathcal{C}$ and $a: FA \rightarrow A$ is an arrow in $\mathcal{C}$ . A morphism of algebras $\pi : (A,a) \rightarrow (B,b)$ is an arrow $\pi : A \rightarrow B$ in $\mathcal{C}$ such that $\pi \circ a = b \circ F(\pi)$ . Given an endofunctor $F$ , algebras for $F$ and related morphisms form a category.

Now we show that $M(\Sigma)$ is an algebra for the functor $F: Set \rightarrow Set$ ,

$F (A) = \sum_{f \in \Sigma} A^{\rho(f)}.$

Note that every map $a: FA \rightarrow A$ is actually a collection of maps $[ a_f]_{f \in \Sigma}$ such that $a_f : A^{\rho(f)} \rightarrow A$ , and if $c \in \Sigma$ is a costant, i.e. has arity 0, then $a_c$ is just an element of $A$ . The map that makes $M(\Sigma)$ an algebra for $F$ is $a_f (t_1,\dots,t_{\rho(f)}) = t'$ where

$t'(\varepsilon) = f$ ;
$t'(\alpha i)=t_i (\alpha)$ , for every $i \le \rho(f)$ ;
$t'(\alpha)$ undefined otherwise.

Basically $a_f(t_1,\dots,t_{\rho(f)}) = f(t_1,\dots,t_{\rho(f)})$ , so $a$ represents the standard operation for constructing a new tree from a function symbol $f$ and a set of trees with cardinality $\rho(f)$ . Moreover $M(\Sigma)$ is the initial object in the category of algebras for $F$ , so is the initial algebra for $F$ . We just need to find the catamorphisms. Let $(B,b)$ be an algebra for $F$ , then we define $\pi : (M(\Sigma),a) \rightarrow (B.b)$ recursively as follows:

$\pi(f(t_1,\dots,t_{\rho(f)}) = b_f (\pi(t_1),\dots,\pi(t_{\rho(f)}))$ .

Note that $\pi$ is well defined because we are dealing with finite trees. So for every finite tree $t$ , $\pi(t)$ depends on the values of $\pi$ on constants $c \in \Sigma$ , $\pi(c) = b_c$ , and these values are univocally determined by $b$ . Also it’s easy to see that $\pi$ is a morphism of algebras and that is unique.