--- title: Algebras for an Endofunctor and Recursion module: Monads and Algebras moduleNumber: 7 lessonNumber: 4 order: 704 summary: > Dropping the monad laws leaves algebras for a bare endofunctor, whose initial objects are the least fixed points of the functor by Lambek's lemma. The natural numbers, lists, and trees are initial algebras; the unique map out of an initial algebra is the fold of functional programming; and the Smyth–Plotkin fixed-point technique builds Scott domains the same way. topics: [Monads and Algebras] sources: - book: Barr & Wells ref: "§14.1 Fixed points for a functor; §14.2 Recursive categories" - book: Barr & Wells ref: "§14.5 Scott domains" draft: false --- A [monad algebra](/category-theory/monads-algebras/algebras-eilenberg-moore) is a structure map $a : TA \to A$ constrained by two laws tied to the monad's unit and multiplication. Delete the laws (and the unit and multiplication with them), and what remains is an **algebra for an endofunctor**: any object with any map $F(A) \to A$. The definition looks weak, but its initial objects are the least fixed points of $F$, and the least fixed points of suitable functors are the natural numbers, lists, and trees of programming. Recursion over a datatype is one universal property applied repeatedly.[^bw-intro] ## Fixed points of a functor For a monotone function on a poset, a fixed point is an element with $f(x) = x$, and among the fixed points there may be a least one. Barr & Wells open Chapter 14 by asking what the analogue is for a functor $R : \mathcal{A} \to \mathcal{A}$, and the obvious candidate fails.[^bw-naive] Consider $R : \mathbf{Set} \to \mathbf{Set}$ with $R(S) = 1 + S$ (disjoint union with a one-point set), the functor whose fixed point ought to be the natural numbers. Demanding a set with $R(S) = S$ on the nose is hopeless: the equality would depend on the arbitrary choice of how disjoint unions are implemented. Weakening to isomorphism $S \cong 1 + S$ fixes that but breaks leastness: **every** infinite set satisfies $S \cong 1 + S$, and infinite sets have proper infinite subsets also satisfying it, so nothing is least in any containment sense. The resolution is to change the structure carrying the question. > **Definition ($F$-algebra).** Let $F : \mathcal{A} \to \mathcal{A}$ be an > endofunctor. An **$F$-algebra** is a pair $(A, a)$ with $a : F(A) \to A$ an > arrow of $\mathcal{A}$. A **homomorphism** $(A, a) \to (B, b)$ is an arrow > $f : A \to B$ with $f \circ a = b \circ F(f)$. Algebras and homomorphisms > form the category $(F : \mathcal{A})$. > **Definition (Fixed point; least fixed point).** An $F$-algebra $(A, a)$ is a > **fixed point** of $F$ if $a$ is an isomorphism. A **least fixed point** of > $F$ is an initial object of $(F : \mathcal{A})$.[^bw-lfp] "Least" reads a category as a generalized poset: in a poset-as-category, an initial object is a bottom element. A lemma justifies the definition by guaranteeing that initial algebras are fixed points. > **Theorem (Lambek's lemma).** If $(A, a)$ is an initial object of > $(F : \mathcal{A})$, then $a : F(A) \to A$ is an isomorphism.[^bw-lambek] > **Proof.** Since $(F(A), F(a))$ is itself an $F$-algebra, initiality gives a > unique homomorphism $f : (A, a) \to (F(A), F(a))$; the diagram below stacks > the homomorphism square for $f$ on the trivially commuting square for $a$. Its > outer rectangle makes $a \circ f$ an algebra endomorphism of $(A, a)$, so > initiality forces $a \circ f = \mathrm{id}_A$. Then > $$ > f \circ a = F(a) \circ F(f) = F(a \circ f) = F(\mathrm{id}) = \mathrm{id}_{F(A)}, > $$ > so $f = a^{-1}$, and $a$ is an isomorphism. $$ % caption: The proof of Lambek's lemma. The top row is the composite $a \circ f$, % an endomorphism of the initial algebra, so it is the identity; the bottom row % is its image $F(a \circ f)$. The right-hand square is the homomorphism square % for $f$, giving $f \circ a = Fa \circ Ff = \mathrm{id}$. \begin{tikzpicture}[>=stealth, font=\small, nd/.style={minimum size=8mm, inner sep=2pt}] \definecolor{acc}{HTML}{4A6FA5} \node[nd] (a1) at (0,2.4) {$A$}; \node[nd] (fa1) at (3.4,2.4) {$F A$}; \node[nd] (a2) at (6.8,2.4) {$A$}; \node[nd] (fa2) at (0,0) {$F A$}; \node[nd] (f2a) at (3.4,0) {$F^2 A$}; \node[nd] (fa3) at (6.8,0) {$F A$}; \draw[->, acc, thick] (a1) -- (fa1) node[midway, above] {$f$}; \draw[->, acc, thick] (fa1) -- (a2) node[midway, above] {$a$}; \draw[->, acc, thick] (fa2) -- (f2a) node[midway, below] {$Ff$}; \draw[->, acc, thick] (f2a) -- (fa3) node[midway, below] {$Fa$}; \draw[->, black, thick] (a1) -- (fa2) node[midway, left] {$f$}; \draw[->, black, thick] (fa1) -- (f2a) node[midway, right] {$Ff$}; \draw[->, black, thick] (a2) -- (fa3) node[midway, right] {$f$}; \end{tikzpicture} $$ Initial algebras also inherit the two other virtues of initial objects: they have no proper subobjects (the categorical residue of "least"), and they are unique up to unique isomorphism.[^bw-unique] ## The natural numbers as an initial algebra Return to $R(S) = 1 + S$. The natural numbers carry the $R$-algebra structure $$ (0; s) : 1 + \mathbb{N} \to \mathbb{N}, $$ where $0$ picks out zero on the left summand and $s$ is the successor on the right. This algebra is initial: given any algebra $f : 1 + S \to S$, decompose $f$ into a chosen element $x_0 = f(\ast) \in S$ and a map $t = f|_S : S \to S$; the unique homomorphism $h : \mathbb{N} \to S$ is defined by induction as $$ h(0) = x_0, \qquad h(n+1) = t(h(n)). $$ Commuting with the structure maps means this pair of equations, so $h$ is a homomorphism and is the only one.[^bw-nno] Definition by recursion — "start at $x_0$, keep applying $t$" — is the universal property of an initial algebra, stated in $\mathbf{Set}$. $$ % caption: Initiality of the naturals ($N$ in the figure stands for % $\mathbb{N}$): any set $S$ with a point and an endomap is an algebra for % $1 + ({-})$, and $h$ defined by recursion is the unique homomorphism from % $(0; s)$. \begin{tikzpicture}[>=stealth, font=\small, nd/.style={minimum size=8mm, inner sep=2pt}] \definecolor{acc}{HTML}{4A6FA5} \node[nd] (fn) at (0,2.3) {$1 + N$}; \node[nd] (n) at (3.8,2.3) {$N$}; \node[nd] (fs) at (0,0) {$1 + S$}; \node[nd] (s) at (3.8,0) {$S$}; \draw[->, acc, thick] (fn) -- (n) node[midway, above] {$(0; s)$}; \draw[->, acc, thick] (fs) -- (s) node[midway, below] {$f$}; \draw[->, black, thick] (fn) -- (fs) node[midway, left] {$1 + h$}; \draw[->, black, thick, dashed] (n) -- (s) node[midway, right] {unique $h$}; \end{tikzpicture} $$ > **Worked example (A fold on the naturals).** Take the target algebra > $f : 1 + \mathbb{N} \to \mathbb{N}$ with $f(\ast) = 1$ on the left summand and > $f(m) = 2m$ on the right, so $x_0 = 1$ and $t(m) = 2m$. The unique homomorphism > $h : \mathbb{N} \to \mathbb{N}$ out of the initial algebra $(0; s)$ is fixed by > the two clauses $h(0) = 1$ and $h(n + 1) = 2\,h(n)$, which solve to $h(n) = 2^n$: > $$ > h(0) = 1, \qquad h(1) = 2, \qquad h(2) = 4, \qquad h(3) = 8. > $$ > Any algebra homomorphism $\mathbb{N} \to \mathbb{N}$ into this target satisfies > the same two equations, so $h$ is the only one. This map is the fold that > iterates doubling from the seed $1$. ### Folds In functional programming the unique map out of an initial algebra is called a **fold** (or catamorphism). The data of an arbitrary algebra $f : F(S) \to S$ (one clause per summand of $F$) is the body of a structural recursion, and initiality says the recursion has exactly one solution. For the naturals, `fold x0 t` is the function iterating $t$ from $x_0$; for lists and trees (below), it is the usual `fold` over the datatype. Uniqueness is as useful as existence: two functions agreeing on the algebra clauses are equal, which is the fusion-style reasoning used to prove program transformations correct. ```algorithm caption: $\textsc{Fold}_F(f)$ — the unique homomorphism from the initial $F$-algebra $(A, a)$ to an algebra $f : F(S) \to S$ given an element of $A$, expose its structure via $a^{-1} : A \to F(A)$ for each constructor cell in the exposed structure do recursively apply $\textsc{Fold}_F(f)$ to every child of type $A$ replace the constructor by the corresponding clause of $f$ return the resulting element of $S$ ``` The step "expose via $a^{-1}$" is licensed precisely by Lambek's lemma: the structure map of the initial algebra is invertible, so every element decomposes uniquely into a constructor applied to children. ## Constructing initial algebras: the colimit chain Existence of initial algebras needs a hypothesis on the functor. In $\mathbf{Set}$, the right condition is that the functor is **finitary**: every element of $R(S)$ comes from $R(S_0)$ for some finite subset $S_0 \subseteq S$ — the functor's behavior is determined by what it does on finite sets.[^bw-finitary] The functor $1 + S$ is finitary; the powerset functor is not, since an infinite subset of $S$ is not contained in any finite subset. > **Theorem.** Let $R$ be a finitary endofunctor of $\mathbf{Set}$ and let $Z$ > be the colimit of the chain > > $$ > \emptyset \xrightarrow{\;\eta\;} R(\emptyset) \xrightarrow{\;R\eta\;} R^2(\emptyset) > \xrightarrow{\;R^2\eta\;} \cdots > $$ > > where $\eta$ is the unique map out of the initial object. Then $R(Z) \cong Z$ > canonically, and this isomorphism makes $Z$ an initial > $R$-algebra.[^bw-colimit] The chain starts from nothing and applies the functor repeatedly; the colimit is the union if the maps are inclusions. Finitarity lets $R$ commute with this colimit, so that $R(Z)$ is the colimit of the shifted chain, which is canonically $Z$ again. For $R(S) = 1 + S$ the chain is $$ 0 \to 1 \to 2 \to \cdots \to n \to \cdots $$ (with $n$ the $n$-fold sum $1 + \cdots + 1$ and the maps the sum injections), and the colimit is $\mathbb{N}$ with successor: the initial algebra built floor by floor, the $n$-th stage containing the numbers writable with at most $n$ constructor applications. $$ % caption: The initial-algebra chain for $R(S) = 1 + S$. Start from the empty % set, apply $R$ at each step (the sum injections), and take the colimit: stage % $n$ holds the numbers needing at most $n$ constructor applications, and the % colimit is $N$ (drawn for $\mathbb{N}$) with successor. \begin{tikzpicture}[>=stealth, font=\small, nd/.style={minimum size=7mm, inner sep=2pt}] \definecolor{acc}{HTML}{4A6FA5} \node[nd] (z) at (0,0) {$0$}; \node[nd] (o) at (1.7,0) {$1$}; \node[nd] (t) at (3.4,0) {$2$}; \node[nd] (h) at (5.1,0) {$3$}; \node[nd] (N) at (9.0,0) {$N$}; \draw[->, acc, thick] (z) -- (o); \draw[->, acc, thick] (o) -- (t); \draw[->, acc, thick] (t) -- (h); \draw[->, acc, thick] (h) -- (6.1,0); \fill[acc] (6.6,0) circle (1.3pt); \fill[acc] (7.05,0) circle (1.3pt); \fill[acc] (7.5,0) circle (1.3pt); \draw[->, acc, thick] (8.0,0) -- (N); \node[font=\footnotesize, black] at (9.0,-0.8) {colimit}; \end{tikzpicture} $$ ### Inductive datatypes The same construction interprets datatype declarations. A **polynomial endofunctor** is one built from constant functors and the identity by finite products and sums[^bw-poly]; each summand is a constructor, each factor a field. | Declaration | Endofunctor $F(X)$ | Initial algebra | | --- | --- | --- | | natural numbers | $1 + X$ | $\mathbb{N}$ with zero and successor | | lists over $A$ | $1 + A \times X$ | $A^\ast$ with nil and cons | | binary trees, data $D$ at nodes | $D + X \times D \times X$ | finite binary trees | | nonempty trees over $A$ | $A + X \times X$ | binary leaf trees | Barr & Wells work in the setting of a **locos** (a coherent, locally recursive category), where every polynomial endofunctor admits free algebras: the underlying functor from $(F : \mathcal{C})$ back to $\mathcal{C}$ has a left adjoint.[^bw-locos] The free algebra on the terminal object $1$ is the initial algebra, and for the tree functor $T(X) = D + X \times D \times X$ its structure map $$ D + F(1) \times D \times F(1) \longrightarrow F(1) $$ reads as the two constructors: a leaf datum, or a datum with two subtrees. This is initial-algebra semantics: the meaning of a recursive datatype is the initial algebra of its signature functor. ## Recursive categories and list objects Recursion can also be internalized: made available inside a category rather than stated about it. For an object $A$ of a category with finite products, the endofunctor $A \times({-})$ has as algebras the **$A$-actions** $x : A \times X \to X$, forming a category $\mathbf{act}(A)$. > **Definition (Recursive category).** A category $\mathcal{C}$ with finite > products is **recursive** if for every object $A$ the underlying functor > $U_A : \mathbf{act}(A) \to \mathcal{C}$ has a left adjoint > $F_A$.[^bw-recursive] Write $\mathrm{rec}(A, B) = U_A(F_A(B))$, the free $A$-action on $B$. Its universal property: given any $t_0 : B \to X$ and $t : A \times X \to X$, there is a unique $f : \mathrm{rec}(A, B) \to X$ compatible with both: a seed and a step determine a unique recursive map. In $\mathbf{Set}$, $\mathrm{rec}(A, B) \cong A^\ast \times B$: a list of $A$'s waiting to be consumed, together with a seed $b$. Two specializations matter: - $\mathrm{rec}(A, 1) = A^\ast$ is the **list object** on $A$, available in any recursive category, with well-defined head and tail operations. - $\mathrm{rec}(1, 1)$ is a **natural numbers object**: lists over a one-point alphabet are tallies. The definition strengthens in stages: a **locally recursive** category has $\mathrm{rec}(A,B) \cong A^\ast \times B$ uniformly and all slices recursive, and a locos is additionally coherent. The stronger axioms yield a computability theorem: in a locos generated by decidable objects, every object is decidable, so the constructions of a locos never manufacture undecidable equality from decidable ingredients.[^bw-decidable] ### State machines as algebras An algebra for $A \times ({-})$ is also exactly a deterministic transition system: $\delta : A \times C \to C$ takes an input letter and a state to a next state. Barr & Wells package this as **categorical dynamics**: an endofunctor $R$ whose algebra category has free objects is an **input process**, an $R$-algebra is an $R$-**dynamic**, and a machine is a dynamic with an initial state arrow $\tau : I \to C$ and an output arrow $\beta : C \to Y$.[^bw-machine] The free-monoid action $\delta^\ast : A^\ast \times C \to C$ extends $\delta$ to strings, recovering the classical automaton; reachability becomes "$\tau$ factors through no proper subalgebra." Choosing a different functor (say $R(C) = C \times C$) gives machine notions with no classical counterpart. ## Terminal coalgebras Dualizing once more: a **coalgebra** for $F$ is a map $c : X \to F(X)$, and the **terminal** coalgebra is the greatest fixed point of $F$ (Lambek's lemma dualizes, so its structure map is again an isomorphism). Where the initial algebra of $1 + A \times X$ is finite lists, the terminal coalgebra of $A \times X$ is infinite **streams** over $A$: a stream is observed by its head and tail, $\langle \mathrm{hd}, \mathrm{tl}\rangle : X \to A \times X$, and the unique map into the terminal coalgebra assigns to every state of any transition system the stream of outputs it generates. Folds consume finite structure; unfolds produce possibly-infinite structure. The pairing — datatypes as initial algebras, codatatypes as terminal coalgebras — organizes recursion and corecursion into one picture. $$ % caption: Two fixed points of the structure functor: the initial algebra % (a map $F(A) \to A$, the least solution) builds data from constructors; the % terminal coalgebra (a map $X \to F(X)$, the greatest solution) observes % possibly-unbounded behavior via destructors. \begin{tikzpicture}[>=stealth, font=\small, bx/.style={draw, minimum width=34mm, minimum height=13mm, align=center}] \definecolor{acc}{HTML}{4A6FA5} \node[bx] (ia) at (0,0) {initial algebra\\(least solution)}; \node[bx] (tc) at (7.0,0) {terminal coalgebra\\(greatest solution)}; \node[font=\footnotesize, align=center] at (0,-1.35) {constructors, folds,\\lists and trees}; \node[font=\footnotesize, align=center] at (7.0,-1.35) {destructors, unfolds,\\streams and behaviors}; \draw[<->, acc, thick] (ia) -- (tc) node[midway, above] {duality}; \end{tikzpicture} $$ ## Scott domains by the same technique Fixed points of functors also produce a model of the untyped lambda calculus, an object $D$ in a cartesian closed category with $$ D \;\cong\; [D \to D], $$ so that every element of $D$ is simultaneously a function $D \to D$ and can be applied to itself. In $\mathbf{Set}$ this is impossible for cardinality reasons (except for $D = 1$). Worse, the assignment $D \mapsto [D \to D]$ is not even a functor: an arrow $D \to E$ induces maps $[D \to D] \to [D \to E]$ and $[E \to D] \to [D \to D]$, but nothing between $[D \to D]$ and $[E \to E]$ — the exponential is contravariant in one variable and covariant in the other.[^bw-scott] The Smyth–Plotkin technique repairs functoriality by enriching. A **Smyth–Plotkin category** is a cartesian closed category whose hom-sets are posets, with composition and the exponential monotone, and with limits and colimits along countable chains that are order-isomorphisms on homs.[^bw-spdef] From such a $\mathcal{C}$ build the category $\mathbf{LA}(\mathcal{C})$: same objects, but an arrow $A \to B$ is an **adjoint pair** $(f : A \to B,\ g : B \to A)$ with $\mathrm{id}_A \le g \circ f$ and $f \circ g \le \mathrm{id}_B$ — each arrow carries its own approximate inverse, and either component determines the other. A pair with $g \circ f = \mathrm{id}$ is a **retract**. On $\mathbf{LA}(\mathcal{C})$ the exponential becomes an honest covariant functor: $F(B) = [B \to A]$ sends the pair $(f, g)$ to the pair $([g, A], [f, A])$, using $g$ in the contravariant slot and $f$ in the covariant one. The main theorem then supplies the fixed point. > **Theorem (Smyth–Plotkin).** Let $\mathcal{C}$ be a Smyth–Plotkin category > whose hom-posets have least upper bounds of countable increasing chains. Then > the colimit in $\mathcal{C}$ of a countable retract chain in > $\mathbf{LA}(\mathcal{C})$ is also its colimit in $\mathbf{LA}(\mathcal{C})$, > and dually for coretract chains in $\mathbf{RA}(\mathcal{C})$.[^bw-spthm] The construction of the model runs the initial-algebra chain in this enriched setting. Start with an object $A \ne 1$ with $A \cong A \times A$ and a retract pair $A \to [A \to A]$; iterate $F$: $$ A \to F(A) \to F^2(A) \to \cdots \to F^n(A) \to \cdots $$ Let $B$ be the colimit. Because $[-, A]$ converts the colimit chain into a limit chain and back, $F$ preserves the colimit, so $F(B) \cong B$ — that is, $B \cong [B \to A]$, and a short calculation upgrades this to $$ B \;\cong\; B \times B \;\cong\; [B \to B]. $$ The concrete instance takes $\mathcal{C}$ to be the category of $\omega$-complete partial orders and countable-sup-preserving maps, which is cartesian closed. For $A$, take a countable power of any nontrivial CPO $A_0$ with a bottom element (a countable power satisfies $A \cong A \times A$ by splitting a sequence into its even- and odd-indexed halves); the retract pair sends an element to the constant function at it, and a function to its value at $\bot$. The result is a **Scott domain** $D$ with $D \cong D \times D \cong [D \to D]$: a genuine model of self-application, constructed as a fixed point of a functor by the same chain that built the natural numbers.[^bw-cpo] The same fixed-point chain, enriched over posets, builds the Scott domains on which the [cartesian closed categories](/category-theory/cartesian-closed-lambda/cartesian-closed-categories) interpret the untyped lambda calculus. [^bw-intro]: **Barr & Wells**, _Category Theory for Computing Science_, Ch. 14 introduction — the chapter's topics "centered around the idea of the algebra for a functor": fixed points, triples, and the Smyth–Plotkin construction of Scott domains. [^bw-naive]: **Barr & Wells**, §14.1.2 — why the naive definitions fail for $R(S) = 1 + S$: strict fixedness depends on the implementation of sums, and fixedness up to isomorphism admits every infinite set with no least one. [^bw-lfp]: **Barr & Wells**, §14.1.3–14.1.5 — $R$-algebras, the category $(R : \mathcal{A})$, fixed points as algebras whose structure map is an isomorphism, and least fixed points as initial objects. [^bw-lambek]: **Barr & Wells**, §14.1.7, Theorem (Lambek 1970) — if $(A, a)$ is initial in $(R : \mathcal{A})$ then $a$ is an isomorphism; the displayed two-square proof. [^bw-unique]: **Barr & Wells**, §14.1.8 — initial algebras have no proper subobjects, and are determined uniquely up to unique isomorphism. [^bw-nno]: **Barr & Wells**, §14.1.8 and Exercise 1 — $(0; s) : 1 + \mathbb{N} \to \mathbb{N}$ is an initial algebra, with the unique homomorphism defined by $h(0) = f(\ast)$, $h(n+1) = f(h(n))$. [^bw-finitary]: **Barr & Wells**, §14.1.9 — conditions FF-1 and FF-2 defining finitary functors on $\mathbf{Set}$; "everything is determined by what happens on finite subsets." [^bw-colimit]: **Barr & Wells**, §14.1.11, Theorem — the colimit $Z$ of the chain $\emptyset \to R\emptyset \to R^2\emptyset \to \cdots$ carries an initial $R$-algebra structure when $R$ is finitary; §14.1.12 computes the chain for $1 + S$. [^bw-poly]: **Barr & Wells**, §14.2.7 — polynomial endofunctors: the least class containing constants and the identity, closed under finite products and sums. [^bw-locos]: **Barr & Wells**, §14.2.6–14.2.8 — locally recursive categories and locoses; Proposition: in a locos every polynomial functor's algebra category has free objects; the binary-tree example $T(X) = D + X \times D \times X$. [^bw-recursive]: **Barr & Wells**, §14.2.2–14.2.4 — $A$-actions, recursive categories, the universal property of $\mathrm{rec}(A, B)$, and $\mathrm{rec}(A, B) \cong A^\ast \times B$ in $\mathbf{Set}$; Exercise 2: $\mathrm{rec}(1,1)$ is a natural numbers object. [^bw-decidable]: **Barr & Wells**, §14.2.9, Theorem (Cockett) — in a locos with a generating collection of decidable objects, every object is decidable. [^bw-machine]: **Barr & Wells**, §14.2.10–14.2.11 — input processes, $R$-dynamics, dynamorphisms, machines, and the recovery of classical state-transition machines from the functor $A \times ({-})$ on $\mathbf{Set}$. [^bw-scott]: **Barr & Wells**, §14.5.1 — the difficulty: $D \mapsto [D \to D]$ is not a functor, and the Smyth–Plotkin trick resolves it. [^bw-spdef]: **Barr & Wells**, §14.5.2–14.5.4 — Smyth–Plotkin categories SP-1 through SP-7, the categories $\mathbf{LA}(\mathcal{C})$ and $\mathbf{RA}(\mathcal{C})$ of adjoint pairs, retracts and coretracts. [^bw-spthm]: **Barr & Wells**, §14.5.5, Theorem — colimits of countable retract chains in $\mathbf{LA}(\mathcal{C})$ are computed in $\mathcal{C}$, with the dual statement for $\mathbf{RA}(\mathcal{C})$. [^bw-cpo]: **Barr & Wells**, §14.5.6–14.5.7 — the iteration $A \to F(A) \to F^2(A) \to \cdots$ with $F(B) = [B \to A]$, its colimit $B$ satisfying $B \cong B \times B \cong [B \to B]$, realized in the cartesian closed category of $\omega$-CPOs.