8. Monads

Mikołaj Bojańczyk

zajęcia / courses

So far, we had monoids (and semigroups), as well as an algebraic structure for $\omega$ -words. In the future, we will also study algebraic structures for other kinds of words, e.g. words indexed by countable total orders, or maybe even arbitrary total orders. Before presenting those structures, we will introduce some general theory, which will allow us to skip some of the standard symbol-pushing that is common to all algebras. This general theory is monads. The idea is that the notion of finite nonempty words is one monad, while the notion of $\infty$ -words is another monad.

Definition. A monad, consists of the following ingredients:

• for each set $X$ , a new set $\monad X$ , called the structures over $X$ .
• for each function $f : X \to Y$ , a new function $\monad f : \monad X \to \monad Y$ , called the lifting of $f$ .
• for each set $X$ , a flattening operation $\flatt X : \monad \monad X \to \monad X$ .
• for each set $X$ , a unit operation $\unit X : X \to \monad X$ .

These ingredients are subject to axioms called “functor”, “natural” and “monoid” that will be discussed below. $\Box$

The above definition is actually a special case of the general definition of monads. Monads can be applied to any category, while the above definition is only given for the category of sets. However, since in this lecture we only use monads in the category of sets, we only give the special case of the definition.

Example. The monad of nonempty finite words is defined as follows. The structures over $X$ are $X^+$ , i.e. the nonempty finite words over $X$ . The lifting $f^+(w)$ is obtained by applying $f$ to each letter of $w$ . The flattening operation is the natural one which takes a word of words into a single word, e.g. the flattening of $(aba)(aa)(b)$ is $abaaab$ . The unit operation maps a letter to a single letter word consisting of this letter. $\Box$

We now begin discussing the axioms of a monad. When reading the axioms below, it is a good idea to check that they are satisfied by the monad of nonempty words in the example above.

Functor axioms. The first group of axioms is that the first two ingredients of a monad are a functor in the sense of category theory. This means lifting is preserves the identity and composition of functions. Preserving identity means that if we lift the identity function on $X$ , the result is the identity function on $\monad X$ . Preserving composition means that for every functions $f : X \to Y$ and $g : Y \to Z$ , the following diagram commutes

$\xymatrix @R=2pc { \monad X \ar[r]^{\monad f} \ar[dr]_{\monad (g \circ f)} & \monad Y \ar[d]^{\monad g} \\& \monad Z }$

Natural axioms. The second group of axioms is that for every function $f X \to Y$ , the following diagrams commute. This means that flattening and unit are what category theorists call natural transformations.

$\vcenter{\xymatrix @R=2pc { X \ar[r]^{f} \ar[d]_{\unit X} & Y \ar[d]^{\unit Y} \\ \monad X \ar[r]_{\monad f}& \monad Y }} \qquad \vcenter{\xymatrix @R=2pc { \monad \monad X \ar[r]^{\monad \monad f} \ar[d]_{\flatt X} & \monad \monad Y \ar[d]^{\flatt Y} \\ \monad X \ar[r]_{\monad f}& \monad Y }}$

Monoid axioms. The first monoid axiom says, essentially, that applying the unit to a structure (i.e. an element of $\monad X$ ) and flattening has no effect. The expression “applying the unit to a structure” is ambiguous in the sense that it has two different interpretations, and both interpretations are dealt with in the axiom, which says that the following diagram commutes for every set $X$ :

$\vcenter{\xymatrix @R=2pc { \monad X \ar[dr]^{\mathrm{id}_X} \ar[r]^{\unit {\monad X}} \ar[d]_{\monad \unit X} & \monad \monad X \ar[d]^{\flatt X} \\ \monad \monad X \ar[r]_{ \unit X }& \monad X }}$

The second monoid axiom is the most important one. It says that if we start with a structure of structures of structures, and we flatten it twice, then we get the same result regardless of which order of flattening we employ. The appropriate commuting diagram is given below.

$\vcenter{\xymatrix @R=2pc @C=3pc {\monad \monad \monad X \ar[r]^{\flatt{ \monad X}} \ar[d]_{\monad{ \flatt X}} & \monad \monad X \ar[d]^{\flatt X} \\ \monad \monad X \ar[r]_{ \flatt X}& \monad X }}$

This completes the axioms of a monad, and therefore also the definition of a monad.

Eilenberg-Moore algebras. In this lecture, the point of monads is that each monad comes with a natural notion of algebra, called its Eilenberg-Moore algebra. For example, in the monad of nonempty finite words, Eilenberg-Moore algebras will be semigroups, in the monad of possibly empty finite words (with the obvious definition), the Eilenberg-Moore algebras will be monoids.

Definition. An Eilenberg-Moore algebra for a monad $\monad$ is defined to be a pair of:
• a set $A$ , called the universe of the algebra, and
• a multiplication operation $\mult : \monad A \to A$
such that $\multnoarg \circ \unit A$ is the identity on $A$ , and which is associative in the sense that the following diagram commutes

$\vcenter{\xymatrix @R=2pc @C=3pc { \monad \monad A \ar[r]^{\flatt A} \ar[d]_{\monad \multnoarg} & \monad A \ar[d]^{\multnoarg} \\ \monad A \ar[r]_{\multnoarg} & A }}$

$\Box$

Instead of Eilenberg-Moore algebra for a monad $\monad$ , we will write $\monad$ -algebra. We denote $\monad$ -algebras by blackboard letters $\alg$ , and use the convention that the universe of $\alg$ (respectively $\balg$ ) is written by a non-boldface letter $A$ (respectively $B$ ), while its multiplication operation is denoted by $\mult \alg$ (respectively $\mult \balg$ ). In the special case of the monad of possibly finite words, an Eilenberg-Moore algebra is the same thing as a monoid, in the sense of Definition 2 here. Likewise, semigroups are Eilenberg-Moore algebras for the monad of nonempty finite words.

Homomorphisms. A homomorphism of $\monad$ -algebras $\alg$ and $\balg$ is a function $h : A \to B$ between their universes which is consistent with the multiplication operation in the sense that the following diagram commutes

$\begin{align*} \vcenter{\xymatrix @R=1pc @C=3pc { \monad A \ar[r]^{\monad h} \ar[d]_{ \mult_\alg} & \monad B \ar[d]^{\mult_\balg} \\ A \ar[r]_{h} & B }} \end{align*}$

Free algebra. For a set $X$ , define its free $\monad$ -algebra as follows: the universe is $\monad X$ , while the multiplication operation is flattening. The two monoid axioms of a monad imply that this is indeed a $\monad$ -algebra. By abuse of notation, we denote the free $\monad$ -algebra by $\monad X$ . For example, in the special case of the monad of nonempty finite words, the free algebra is $X^+$ . The reason for the name free is given in the following lemma.

Free Algebra Lemma. If $\alg$ is a $\monad$ -algebra and $\Sigma$ is a set, then for every function $f$ from $\Sigma$ to the universe of $\alg$ there is a unique homomorphism of $\monad$ -algebras $h : \monad \Sigma \to \alg$ which extends it in the sense that the following diagram commutes

$\xymatrix{ \Sigma \ar[dr]_{f} \ar[r]^{\unit \Sigma} & \monad \Sigma \ar[d]^h \\ & \alg}$

$\Box$

Proof. Let us first show that if the homomorphism $h$ exists, then it is unique. Suppose that $h$ is a homomorphism which extends $f$ in the sense of the diagram above. Consider the following diagram:

$\xymatrix@C=4pc{ & \monad \Sigma \ar[ddl]_{\monad f} \ar[ddr]^{\ident \Sigma} \ar[dd]_{\monad \unit \Sigma}\\ \\ \monad A \ar[dr]_{\mult \alg} & \monad \monad \Sigma \ar[l]_{\monad h} \ar[r]^{\flatt \Sigma} & \monad \Sigma \ar[dl]_{h} \\ & A}$

The left triangular face commutes by applying the functor $\monad$ to the diagram in the statement of the lemma which says that $h$ extends $f$ . (Applying a functor preserves commuting diagrams.) The right triangular face commutes by the first monoid axiom of a monad. The lower face commutes by the assumption that $h$ is a homomorphism. Therefore, the perimeter of the diagram says that $h$ must be equal to $\monad f$ followed by multiplication in $\alg$ . We now show that $h$ defined this way really is a homomorphism.

Being a homomorphism is that the perimeter of the following diagram commutes.

$\begin{align*} \xymatrix@C=4pc{ \monad \monad \Sigma \ar[ddd]_{\flatt \Sigma} \ar[rr]^{\monad h} \ar[dr]_{\monad \monad f} & & \monad A \ar[ddd]^{\mult \alg}\\ & \monad \monad A \ar[ur]_{\monad \mult \alg} \ar[d]_{\flatt A} \\ & \monad A \ar[dr]^{\mult \alg} \\ \monad \Sigma \ar[rr]_{h} \ar[ur]^{\monad f} & & A}\end{align*}$

The lower triangular face is simply the definition of $h$ , while the upper triangular face is the definition of $h$ with the functor $\monad$ applied to it. The left trapezoid face is the second of the “natural axioms”, while the right trapezoid face is the associativity of multiplication in $\alg$ . $\Box$

COMMENTS

Nikolay

June 11, 2020

Thanks. This material is extremely helpful. If I am not mistaken in the commutatitve diagram of the monoid axioms of monad there should be id_{TX} rather than id_{X}. (Each Set has its own identity morphism)

Jürgen Koslowski, koslowj@tu-bs.de

June 26, 2018

Very nice course notes indeed! Just a minor suggestion: in your definition of monad, please replace the term "lifting" by "extension". These terms have a technical meaning in category theory, where extensions happen along the domain, while liftings happen along the codomain, see, e.g., https://ncatlab.org/nlab/show/Kan+extension. Reversing this convention is bound to cause confusion at some point. Sincerely yours,

zajęcia / courses

8. Monads

Leave a Reply