Initial Ideas and Final Thoughts

We encountered algebras for endofunctors in the previous post. In this post, shall introduce the dual notion, endofunctor coalgebras, and shall look at some special endofunctor algebras and coalgebras. These constructions have wide applications, but we shall be particularly interested in their usefulness for systematically constructing certain classes of monads.

Initial Algebras

For an endofunctor $F$ , an initial $F$ -algebra is simply an initial object in $\mathsf{Alg}(F)$ . Explicitly, this is an $F$ -algebra $(\mu(F),\mathsf{in})$ such that for every $F$ -algebra $(A,a)$ there is a unique morphism $! : \mu(F) \rightarrow A$ such that

$! \circ \mathsf{in} = a \circ F(!)$

The first crucial fact to know about initial algebras, known as Lambek’s Lemma, is that $\mathsf{in}$ is always an isomorphism. This highlights that initial algebras generalise the notion of least fixed points for monotone maps.

Lambek’s lemma immediately tells us that certain initial algebras cannot exist.

Example: The powerset functor does not have an initial algebra. as there is no set $X$ such that $X \cong \mathcal{P}(X)$ .

As usual, we will motivate constructions by considering algebraic examples of initial algebras.

Example: Consider a signature $\Sigma$ . We inductively define sets $T_i$ , with $T_0 = \emptyset$ , and:

If $c$ is a constant symbol in $\Sigma$ , $c \in T_{n + 1}$ .
If $o$ is an $n$ -ary operation symbol, and $t_1,\ldots,t_n \in T_n$ then $o(t_1,\ldots,t_n) \in T_{n + 1}$ .

It is hopefully clear that if the signature contains no constant symbols, all of the $T_i$ will be empty. To see what happens with a signature with constants, let $\Sigma = \{ 0, + \}$ , with $0$ a constant, and $+$ a binary operation. We then have:

$T_1 = \{ 0 \}$ .
$T_2 = \{ 0, 0 + 0 \}$ .
$T_3 = \{ 0, 0 + 0, 0 + (0 + 0), (0 + 0) + 0, (0 + 0) + (0 + 0) \}$ .
And so on …

The least fixed point of this process is the set of ground terms over the signature, and is $\mu(\Sigma)$ for the corresponding signature functor. The algebra structure map $\mathsf{in} : 1 + \mu(\Sigma)^2 \rightarrow \mu(T)$ maps the left component to the term $0$ , and on the second component:

$(t_1, t_2) \mapsto t_1 + t_2$

The general case for an arbitrary signature is formally identical.

So the initial algebra of a signature functor is the set of ground terms, equipped with the obvious purely syntactic operations that just form new terms. As usual, we are actually interested in monads, but these don’t involve just ground terms, we need to get the variables involved. So we’re really interested in free algebras over some set, not just the initial algebra.

Example: Let $\Sigma$ be some signature. To build the free algebra over the set $X$ , we construct sets $T_i$ , with $T_0 = \emptyset$ , and:

If $c$ is a constant symbol then $c \in T_{n + 1}$ .
If $x \in X$ then $x \in T_{n + 1}$ .
If $o$ is an $n$ -ary operation symbol, and $t_1,\ldots,t_n \ in T_n$ then $o(t_1,\ldots,t_n) \in T_{n + 1}$ .

If we take $\Sigma = \{ 0, + \}$ as in the previous example, and $X = \{ x \}$ for simplicity, we have:

$T_1 = \{ 0, x \}$ .
$T_2 = \{ 0, x, 0 + x, x + 0, x + x, 0 + 0 \}$ .
$T_3 = \{ 0, x, 0 + x, x + 0, x + x, 0 + 0, 0 + (0 + x), 0 + (x + 0), \ldots \}$ .
And so on…

The least fixed point of this process is the set of all such terms over $X$ , which is $\mu(\Sigma + X)$ , where $\Sigma$ is the corresponding signature functor. We can think of this as forming the initial algebra for a signature extended with a constant symbol for each element of $X$ . Recalling the notation for the free monad, we have deduced that, at least at the level of objects $\Sigma^*(X) = \mu(\Sigma + X)$ .

In fact, this approach works in great generality. For an endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ on a category with binary coproducts, if the functor $F(-) + X$ has an initial algebra, then $\mathsf{in} \circ \kappa_1 : F(\mu(F + X)) \rightarrow \mu(F + X)$ is the free $F$ -algebra over $X$ .

From the above, it follows that if all the functors $F + X$ have initial algebras, the free monad on $F$ is given by:

$F^*(X) = \mu(F +X)$

If we restrict our attention to signature functors, this simply yields another perspective on the description of free monads we saw in the previous post. For other functors, it does yield new monads.

Example: Although there is no initial algebra for the full powerset functor, life is much better for the finite powerset functor $\mathcal{P}_{\omega}$ . Each of the functors $\mathcal{P}_{\omega} + X$ has an initial algebra. The elements of $\mathcal{P}^*_{\omega}(\emptyset)$ are the hereditarily finite sets. These are finite sets, with all elements also hereditarily finite. Similarly the elements of $\mathcal{P}^*_{\omega}(X)$ are hereditarily finite sets with atoms from $X$ . That is, finite sets, with all elements either elements of $X$ , or hereditarily finite sets with atoms from $X$ .

Final Coalgebras

For an endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ , a coalgebra is a pair $(A,a)$ consisting of a $\mathcal{C}$ -object $A$ , and a $\mathcal{C}$ -morphism $a : A \rightarrow F(A)$ . This is the dual notion to that of an $F$ -algebra. These form a category $\mathsf{Coalg}(F)$ , with morphisms $(A,a) \rightarrow (B,b)$ being $\mathcal{C}$ -morphisms $h : A \rightarrow B$ such that

$F(h) \circ a = b \circ h$

Coalgebras are interesting objects, to which we could devote a great deal of discussion. If algebras are about composing things, coalgebras are about taking them apart again. In compute science, they are often used to model objects with some sort of observable behaviour. We consider one very simple example to illustrate the idea.

Example: A coalgebra for the endofunctor $(-) + 1$ is simply a function of the form $a : A \rightarrow A + 1$ . We could interpret this as a device, for which when we press the “go button” either jumps to a new state, ready to go again, or moves to a failure state.

We will resist the temptation to discuss coalgebra theory more generally at this point, and move rapidly on to the construction we are interested in.

A final coalgebra (also sometime termed a terminal coalgebra) for an endofunctor $F$ is a final object in $\mathsf{Coalg}(A,a)$ . Explicitly, this is an object $(\nu(F), \mathsf{out})$ such that for every coalgebra $(A,a)$ there is a unique map $! : A \rightarrow \nu(F)$ such that

$\mathsf{out} \circ ! = F(!) \circ a$

Final coalgebras generalise the notion of greatest fixed point for a monotone map, and satisfy a dual form of Lambek’s lemma.

Example: There is no final coalgebra for the powerset functor, as Lambek’s lemma for coalgebras would lead to a contradiction about cardinalities of powersets.

For our purposes in this post, we are not going to delve deeply into questions about the terminal coalgebra, although it does have great conceptual and mathematical significance. Informally, it can be seen as abstracting all possible behaviours that a coalgebra can exhibit, but we won’t pursue this remark now.

Instead, we’re going to ask a very naive question. Assuming they exist, the objects $\mu(F + X)$ yielded a monad, the free monad $F^*$ . Do the objects of the form $\nu(F + X)$ also carry the structure of a monad as well?

This wouldn’t make a very satisfying end to this blog post if the answer were no, so unsurprisingly, the switch to considering terminal coalgebras does yield a monad. For an endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ , if all the required final coalgebras exist, we construct a monad in Kleisli form as follows:

The object map is $X \mapsto \nu(F +X)$ .
By Lambek’s lemma $\mathsf{out} : \nu(F + X) \rightarrow F(\nu(F + X)) + X$ is an isomorphism. We take as our monad unit the composite $\mathsf{out}^{-1} \circ \kappa_2 : X \rightarrow \nu(F + X)$ .
For a morphism $f : X \rightarrow \nu(F + Y)$ , we can define its Kleisli extension $f^* : \nu(F + X) \rightarrow \nu(F + Y)$ as the unique $F$ -algebra morphism such that $f^* \circ \eta = f$ . That there is such an $f^*$ requires some more theory, that hopefully we can discuss another time. There is a more explicit description of this morphism, but unfortunately it is cumbersome to describe in this format.

Obviously we need to check the appropriate axioms hold for a Kleisli triple, but this works out. The resulting monad is known as the free completely iterative monad on $F$ . Furthermore, it is hopefully not too hard to see that, similarly to the free monad construction, this monad “keeps variables separate”. That is, the resulting monad is another example of the ideal monads that we discussed in the previous post. There is a lot more to say about completely iterative monads, and what the various adjectives mean, but we shall defer that to a later post. Instead, we shall conclude with an example.

Example: Let $\Sigma$ be an algebraic signature. For the corresponding signature functor, the final coalgebra for all of the functors of the form $\Sigma + X$ exists. Therefore the free completely iterative monad on $\Sigma$ exists. The elements of $\nu(\Sigma + X)$ are $\Sigma$ -trees. That is, trees such that:

Every internal node of arity $n$ is labelled by an $n$ -ary operation symbol.
Every leaf node is labelled by either a constant symbol, or an element of $X$ .

Note, these trees can be either finite or infinite, unlike for any of our previously examples, where we work with $\Sigma$ -terms, which are equivalently finite $\Sigma$ -trees. Intuitively, we should think of the extra elements in $\nu(\Sigma + X)$ as “infinite $\Sigma$ -terms”.

Remark: In this post, we have simply introduced various initial algebras and final coalgebras. This sort of “guess and check” approach to finding the right construction is ok, but there are a lot of more systematic strategies for establishing both the existence and a description of these objects. This is a large subject, and involves more technical background that we have introduced so far. A later post may return to this topic.

2 thoughts on “Initial Ideas and Final Thoughts”

Pingback: Completely Iterative Monads – Dan Marsden
Pingback: Further Kleisli and Eilenberg-Moore laws – Dan Marsden

Initial Algebras

Final Coalgebras

Share this:

Like this:

Related

2 thoughts on “Initial Ideas and Final Thoughts”

Leave a Reply Cancel reply