Algebras for a Monad

A monad $\mathbb{T}=(T,\eta ,\mu )$ on $\mathcal{A}$ was built to be the trace of an adjunction, but the definition never mentions one. Every monad does arise from an adjunction, and the construction that proves it also identifies the structure a monad describes: its algebras, objects equipped with a map $TA\to A$ that evaluates $T$-structure. The category they form, due to Eilenberg and Moore, carries a free–forgetful adjunction inducing exactly $\mathbb{T}$.¹

For the list monad an algebra is a set with a way of multiplying out any finite list of its elements, subject to consistency laws that make it a monoid. Monads in this sense present universal algebra through arrows.

Algebras and their axioms

The two axioms mirror the two monad laws, one level down.

• Unit axiom. An element inserted into $TA$ as a trivial structure by ${\eta }_A$ must evaluate to itself. For the list monad: evaluating the singleton list $[a]$ returns $a$.
• Associativity axiom. Given a doubly-nested structure in $T^{2}A$, the two ways of evaluating it — flatten first with ${\mu }_A$, or evaluate the inner layer first with $Ta$ — must agree.

Barr & Wells distinguish an algebra for the endofunctor $T$ (any pair $(A,a)$ with $a:TA\to A$, no axioms) from an algebra for the monad$\mathbb{T}$, which is an endofunctor algebra satisfying the two laws above.² The unconstrained version has its own theory, taken up in algebras for an endofunctor; here the laws tie evaluation to the monad's unit and multiplication.

Composition and identities are inherited from $\mathcal{A}$, so the $\mathbb{T}$-algebras and their morphisms form a category.

Algebras of the list monad are monoids

Let $\mathbb{T}$ be the list monad on $\mathbf{Set}$: $TA=A^{\ast }$, unit $a\mapsto [a]$, multiplication = concatenation. An algebra is a set $A$ with a map $\alpha :A^{\ast }\to A$ evaluating every finite list to an element. Define a binary operation and a constant by

The algebra axioms force $(A,\cdot ,e)$ to be a monoid, and conversely every monoid gives an algebra by $n$-fold multiplication.³

• Unit axiom gives $\alpha ([x])=x$: singleton lists evaluate trivially.
• Associativity axiom applied to the nested list $[[x,y],[z]]$ gives $(x\cdot y)\cdot z=\alpha ([x,y,z])$, and applied to $[[x],[y,z]]$ gives $x\cdot (y\cdot z)=\alpha ([x,y,z])$. Both products equal the flat evaluation, hence each other.
• Unit element. The same axiom on $[[],[x]]$ gives $e\cdot x=\alpha ([x])=x$, and symmetrically $x\cdot e=x$.

Algebra morphisms are exactly monoid homomorphisms: commuting with $\alpha$ on two-element lists is preserving the product, and on the empty list is preserving the unit. So ${\mathbf{Set}}^{\mathbb{T}}\simeq \mathbf{Mon}$.

The pattern generalizes far beyond lists. A theorem of Linton states that every equationally defined category of one-sorted algebraic structures — groups, rings, modules over a fixed ring, lattices — is equivalent to the Eilenberg–Moore category of some monad on $\mathbf{Set}$; the converse holds too if infinitary operations are permitted.⁴ Monads on $\mathbf{Set}$ and algebraic theories are two presentations of the same subject.

The maybe row is worth checking by hand: a structure map $A+1\to A$ satisfying the unit law is the identity on $A$ plus a choice of basepoint (the image of the extra point), and the associativity law is automatic. An algebra is a set with a distinguished element, and morphisms preserve it.

The writer row is the same computation for the representation monad $TA=M\times A$ of a monoid $M$. A structure map $\alpha :M\times A\to A$ is a binary operation $m\cdot a=\alpha (m,a)$. The unit axiom demands $1_M\cdot a=a$, since ${\eta }_A(a)=(1_M,a)$. For the associativity axiom, chase an element $(m_1,m_2,a)\in M\times M\times A=T^{2}A$ around the square: the route through $T\alpha$ gives $m_1\cdot (m_2\cdot a)$, and the route through ${\mu }_A$ gives $(m_1{m}_2)\cdot a$. The two axioms reproduce the two laws of a monoid action, so the algebras are $M$-sets and their morphisms are the equivariant maps — recovering by pure diagram chasing the category that originally induced the monad.

The free–forgetful adjunction

The Eilenberg–Moore category resolves the monad into an adjunction.

• Forgetful functor $U:{\mathcal{A}}^{\mathbb{T}}\to \mathcal{A}$ sends $(A,a)\mapsto A$ and an algebra morphism to itself as an arrow of $\mathcal{A}$.
• Free functor $F:\mathcal{A}\to {\mathcal{A}}^{\mathbb{T}}$ sends $A\mapsto (TA,{\mu }_A)$ and $f\mapsto Tf$.

The pair $(TA,{\mu }_A)$ is the free algebra on $A$: its carrier is $TA$ and its structure map is the monad multiplication. The algebra axioms for it restate the associativity and unit laws of the monad itself, so no new verification is needed: the monad laws are the statement that free algebras are algebras.

The unit of the adjunction is $\eta$ itself. The counit at an algebra $(A,a)$ is the structure map $a$, viewed as an algebra morphism $(TA,{\mu }_A)\to (A,a)$ — the associativity axiom is what makes $a$ such a morphism. Composing, $UF=T$ and $U\epsilon F=\mu$, so the induced monad is the one we started with. Every monad therefore arises from at least one adjunction.

The comparison functor

The Eilenberg–Moore adjunction is not the only one inducing $\mathbb{T}$; the Kleisli construction gives another, and concrete free–forgetful adjunctions (say, $\mathbf{Set}\rightleftarrows \mathbf{Mon}$ itself) give more. The Eilenberg–Moore category is universal among them from above: every inducing adjunction maps into it.

The structure map $G^{\prime }{\epsilon }_B^{\prime }:T{G}^{\prime }B=G^{\prime }{F}^{\prime }{G}^{\prime }B\to G^{\prime }B$ evaluates by the counit; its algebra axioms follow from the triangle identities and naturality. The comparison functor measures how close $\mathcal{B}$ is to being the category of algebras.

Monadicity is the precise sense in which a category is algebraic over a base. The forgetful functors from $\mathbf{Mon}$, $\mathbf{Grp}$, and $R\text{-}\mathbf{Mod}$ to $\mathbf{Set}$ are monadic — that is the content of Linton's theorem read through the comparison functor. The forgetful functor $\mathbf{Top}\to \mathbf{Set}$ has a left adjoint (the discrete-space functor) but is not monadic: its induced monad is the identity, whose algebras are just sets, and $\mathbf{Top}\not\simeq \mathbf{Set}$. A topology is structure but not algebraic structure, and monadicity detects the difference.

Splitting an adjunction through its algebras

The factorization theorems recast the relationship between a monad and its sources. Given any adjunction $F^{\prime }⊣G^{\prime }$ inducing $\mathbb{T}$:

• the monad $\mathbb{T}=(G^{\prime }{F}^{\prime },\eta ,G^{\prime }{\epsilon }^{\prime }{F}^{\prime })$ lives on $\mathcal{A}$ and encodes the round trip;
• the Eilenberg–Moore category ${\mathcal{A}}^{\mathbb{T}}$ reconstructs from $\mathbb{T}$ alone a canonical codomain, the largest one in a precise sense;
• the comparison functor $\Phi$ places the original $\mathcal{B}$ inside it.

Barr & Wells note a cultural split over this construction: in mathematics the Eilenberg–Moore category has been the more important of the two factorizations, while in computer science the Kleisli category dominates.⁶ The mathematical uses run through monadicity: proving a category is algebraic transfers limits, colimits, and exactness properties wholesale from the base. The computing uses run through free algebras and substitution, and the Kleisli category is the category of those free algebras.