Introduction

In the previous post, we investigated free monads, i.e. those whose monad algebras are the same as algebras of some functor. In general, however, not all monads are free, not even in Haskell! Nevertheless, monad algebras can often be regarded as algebras of some functor, satisfying certain “algebraic laws”.

In the first post of the series, we looked at the list monad \(L\). We observed that monad algebras of \(L\) can be regarded as monoids, which is to say they are algebras of the functor \(F\) given by \(F X = 1 + X²\), subject to unit and associativity laws.

The list example is interesting, because it suggests a strong connection between monads and algebraic structures. Can we always regard algebraic structures (such as groups, rings, vector spaces, etc…) as the algebras of some monad?

In this post, we will try to generalise this example to other monads by developing a categorical definition of algebraic theory based on monads and monad algebras.

Algebraic theories

The theory of monoids is a particular instance of a general pattern that occurs over and over in mathematics. We have a set of operations, each with a specified arity, and a set of laws that these operations are required to satisfy. The laws all have the form of equations with universally quantified variables.

For monoids, we have two operations: a unit \(e\), which is a nullary operation (i.e. a constant), and multiplication \(·\), a binary operation (written infix). The laws should be very familiar: \[ \begin{aligned} e · x & = x \\ x · e & = x \\ x · (y · z) & = (x · y) · z \end{aligned} \] where every free variable is implicitly considered to be universally quantified.

As we observed in the first post of this series, the functor \(F\) corresponding to the algebraic theory of monoids is given by \(F X = 1 + X²\). Algebras of \(F\) are sets equipped with the operations of a monoid, but there is no requirement that they satisfy the laws.

Since \(F\) is polynomial, it has an algebraically free monad \(F^*\), so \(F^* X\) is in particular an \(F\)-algebra. If we focus on the first law above, we see that it just consists of a pair of terms in \(F^* X\), parameterised over some unspecified element \(x : X\). This can be expressed as a natural transformation: \[ X → F^*X × F^* X \] The same holds for the second law, while the third can be regarded as a function: \[ X³ → F^*X × F^*X \]

We can assemble those three functions into a single datum, consisting of a pair of natural transformations: \[ X + X + X³ ⇉ F^* X \]

If we set \(G X = X + X + X³\), we have that the laws can be summed up concisely by giving a pair of natural transformations: \[ G ⇉ F^*, \] which, since algebraically free monads are free, is the same as a parallel pair of monad morphisms: \[ l, r : G^* ⇉ F^*, \] and this is something that we can easily generalise. Namely, we say that an algebraic theory is a parallel pair of morphisms of algebraically free monads.

Note that the terminology here is a bit fuzzy. Some authors might refer to the parallel pair above as a presentation of an algebraic theory. It ultimately depends on whether or not you want to consider theories with different syntactical presentations but identical models to be equal. With our definition, they would be considered different.

Models

To really motivate this definition, we now need to explain what the models of an algebraic theory are. This is quite easy if we just follow our derivation of the general definition from the example.

We know that a monoid is an \(F\)-algebra \(θ : F X → X\) that satisfies the monoid laws. Since \(F\)-algebras are the same as \(F^*\)-algebras, we can work with the corresponding \(F^*\)-algebra instead, which we denote by \(θ^* : F^*X → X\).

This algebra satisfies the laws exactly when the two natural transformations above become equal when composed with \(θ^*\), i.e. when \(θ^* ∘ l = θ^* ∘ r\).

We thus define the category of models of an algebraic theory \(l, r : G^* ⇉ F^*\) as the full subcategory of \(\mathsf{Alg}_F ≅ \mathsf{mAlg}_{F^*}\) consisting of all those monad algebras \(θ^* : F^* X → X\) such that \(θ^* ∘ l = θ^* ∘ r\).

Now, we know that, in the case of monoids, this subcategory is monadic over \(\mathsf{Set}\), but is this true in general?

We begin by defining the notion of a free model for some algebraic theory. In the monoid example, we used the list monad to build a monoid out of any set, and then proceeded to prove that this construction gives the left adjoint of the forgetful functor \(\mathsf{Alg}_F → \mathsf{Set}\). This is of course the first step towards proving monadicity.

In general, there does not seem to be a way to generalise this construction directly. We pulled the list monad out of a hat, and showed that it was exactly the monad that we were looking for. We did not derive it using the functor \(F\) in a systematic way that we could replicate in the general case.

Fortunately, there is another way to produce the free monoid over a set \(X\). We start with the free \(F\)-algebra \(F^* X\), then quotient it according to the laws. Intuitively, we define an equivalence relation that relates two elements \(t₁\) and \(t₂\) whenever there is a law that requires them to be equal.

The straightforward way to formalise this intuition is to take the equivalence relation generated by such pairs \((t₁, t₂)\), then take the corresponding quotient. A more conceptual approach is to say that \(T X\) is obtained as a coequaliser: \[ G^* X ⇉ F^* X → T X. \]

In the monoid example, \(F^* X\) is the set of all trees with leaves labelled by elements of \(X\). If we regard a tree as a parenthesised string of elements of \(X\), then the equivalence relation on \(F^*\) given by the coequaliser above corresponds to identifying strings with the same underlying list of elements but possibly different parenthesizations. Therefore, \(T X\) is clearly isomorphic to the list monad.

Conclusion

More generally, we can take any algebraic theory, which we defined as a parallel pair of monad morphisms between free monads \(F^*\) and \(G^*\), and take the coequaliser in the category of (finitary) monads.

With some reasonable assumptions on the functors \(F\) and \(G\), we can show that this coequaliser always exists, and that the algebras of the resulting monad are exactly the models of the algebraic theory we started with.

Further reading

This concludes my series on the underlying theory of free monads and their relation with universal algebra.

Here is a list of resources where you can learn more about this topic:

• Michael Barr and Charles Wells, Toposes, Triples and Theories

  “Triple” is the old term for monads. Chapter 3 is about the monadicity theorem and some of the material that I covered in this series.

• Saunders Mac Lane, Categories for the Working Mathematician

  Chapter 6 is about monads and their algebras.

• Steve Awodey, Category Theory

  The last chapter explains the relationship between initial algebras and monadic functors.

• Francis Borceux, Handbook of Categorical Algebra

  A very comprehensive resource, with detailed proofs.