Monad
Meow! I have decided you're now going to learn some category theory. In this blog post, I'll explain what a monad is. I hope any of this makes any sense.
Let's start with the definition:
Definition. A monad is a monoid in the category of endofunctors. β
When reading this definition, you might notice two things: (1) there are a lot of new terms ("monoid", "category", "endofunctor"), and (2) this definition is very short. I will explain what all these terms in the definition mean in the rest of this blog-post, in the following order:
(Set-)monoid;
Category;
(Endo)functor;
Natural transformation;
Monoidal category;
Monoid over a monoidal category;
Monad.
Monoid
Definition. A monoid is a pair (M,β) with a set M and a binary operation β on M satisfying the following:
There is an element e of M for which, for all x in M, e β x = x β e = x;
For all x,y,z in M, (x β y) β z = x β (y β z). β
A binary operation on a set M is a way of combining any two elements of M into a new element of M. Examples of binary operations are addition and multiplication of real numbers. The binary in "binary operation" refers to the fact we combine two elements, and the operation in "binary operation" refers to the fact that we stay in the same set M after combining. If β is a binary operation on a set M, and x and y are elements of that set M, we usually write x β y to denote the result of applying β to the elements x and y (this notation is called infix notation, as the binary operation β is placed in between its arguments). A bit more abstract example of a binary operation is this one I just made up:
x β y = 2x+3y
Here, x and y are real numbers, so β is a binary operation on the set of reals.
We see that, in the definition, a monoid must satisfy two properties: there must be a neutral element e, so that combining any element x with e does not affect that element, and the binary operation must be associative, meaning that the order in which we compute x β y β z doesn't matter (it must give the same result if we compute x β y first or if we compute y β z first). We can see that the reals with addition and the reals with multiplication are monoids.
Example. (β,+) is a monoid. It has a neutral element 0 so that, for x in β, we have 0+x = x and x+0 = x. Further, for any three real numbers x, y and z, we have (x+y)+z = x+(y+z). β
Example. (β,Β·) is a monoid. It has a neutral element 1: for x in β, we have 1 Β· x = x Β· 1 = x. And, for any three real numbers x, y and z, we have (x Β· y) Β· z = x Β· (y Β· z). β
Example. (β,β) is not a monoid. It is not associative, as (4 β 3) β 2 = (2Β·4 + 3Β·3) β 2 = 17 β 2 = 2Β·17 + 3Β·2 = 40, but 4 β (3 β 2) = 4 β (2Β·3 + 3Β·2) = 4 β 12 = 2Β·4 + 3Β·12 = 44, and 40 β 44. β
As another example, consider the set of all words consisting of the symbols A and B. Here, a word is any string of the given symbols, including strings such as AABABAAAA and BBBBBBBBBBBBBBBBB. This set is denoted {A,B}* where the star * is Kleene's star. We define || on these words to be concatenation of words. So, for example, AAB || BBAB = AABBBAB. Then, ({A,B}*,||) is a monoid. The empty word is the neutral element for this monoid, as concatenating any word with nothing gives back the same word. We usually write Ξ΅ for the empty word, as we're not able to see literally nothing. So, for example, AABA || Ξ΅ = AABA. The operation || is also associative, as the ordering in which we concatenate strings doesn't matter: ABABB || B || BBA = ABABBBBBA, no matter if we compute ABABB || B first or B || BBA first. However, concatenation is not commutative.
Definition. An operation β on a set X is commutative iff, for all x and y in X, x β y = y β x. β
For example, for the strings AAB and BAB, we have AAB || BAB = AABBAB, but BAB || AAB = BABAAB, which are different words. The other examples of monoids we have seen so far ((β,+) and (β,Β·)) do have a commutative operation.
One last example of a monoid is the monoid of functions on {β ,β‘}. A function f from X to Y takes an element a of X and maps it to an element f(a) of Y, and we call a function f from X to the same set X a function on X. So, there are four functions on {β ,β‘}:
β β¦ β , β‘ β¦ β ;
β β¦ β , β‘ β¦ β‘;
β β¦ β‘, β‘ β¦ β ;
β β¦ β‘, β‘ β¦ β‘.
Here, β¦ is the mapsto symbol. So, the first function maps both suits to spades, and the third swaps the suits around. Let's call these functions [β ], 1, Β¬ and [β‘] respectively (for "constant spade", "identity", "negation", "constant heart"). We define a composition operation β on this set of functions as follows: for functions g and f, we define g β f by (g β f)(x) = x. We can see that, with this operation,
[β ] β x = [β ];
[β‘] β x = [β‘];
1 β x = x β 1 = x;
Β¬ β [β ] = [β‘] and Β¬ β [β‘] = [β ];
Β¬ β Β¬ = 1.
So, this operation has identity element 1 (which maps a suit to itself). We can also see that this operation is associative, as ((h β g) β f)(x) = h(g(f(x))) = (h β (g β f))(x). So, our last two examples of monoids are:
Example. The monoid of words ({A,B}*,||). β
Example. The monoid of functions ({[β ],1,Β¬,[β‘]},β). β
Category
Definition. A category π has the following data:
A collection of objects Ob(π);
For any two objects A and B, a collection of arrows π(A,B);
For any arrow f in π(A,B) and any arrow g in π(B,C), an arrow g β f in π(A,C) called the composition of f and g;
For every object A, an arrow 1_A in π(A,A) called the identity arrow on A;
For any three arrows f, g and h, in π(A,B), π(B,C) and π(C,D) respectively, we have (h β g) β f = h β (g β f);
For any arrow f in π(A,B), we have 1_B β f = f β 1_A = f. β
We write A β π for A is an object in π. We write f: A -> B for f is an arrow in π(A,B), we call f an arrow from A to B, we call A the domain of f and B the codomain of f. We sometimes write Hom(A,B) or Hom_π(A,B) for the collection of arrows from A to B. The composition g β f is read "g follows f". The identity arrow 1_A is sometimes denoted as id_A. Arrows are sometimes referred to as morphisms or homomorphisms.
The prime example of a category is the category of sets.
Example. In the category Set, objects are sets. For sets A and B, Hom(A,B) is the collection of functions from A to B. For functions f: A -> B and g: B -> C, we define the composition g β f by (g β f)(a) = g(f(a)). β
There are also some examples of categories from algebra and topology that are similar to Set. Don't worry if any of these examples are too unfamiliar.
Example. Grp. Objects are groups, arrows are group homomorphisms. β
Example. Ring. Objects are rings, arrows are ring homomorphisms. β
Example. Ab. Objects are Abelian groups, arrows are group homomorphisms. β
Example. Top. Objects are topological spaces, arrows are continuous maps. β
Example. Let R be a ring. R-Mod is a category where objects are R-modules, and an arrow f: M -> N is a function that respects the module structure. β
Example. Top_open. Objects are topological spaces, arrows are open continuous maps. β
We can see that the identity function, defined by id_A (a) = a, is the identity arrow on a set A: id_B β f = f β id_A = f, for f: A -> B.
You might notice the definition of a category, apart from the collection of objects Ob(π), is similar to the definition of a monoid. In fact, every monoid is a category with one object.
Example. Let (M,β) be a monoid. Then, we define a category M by Ob(M) = {*}, M(*,*) = M and, for x,y in M(*,*), we define the composition x β y in the category M to be the operation x β y in the monoid M. β
The last example of a monoid in the previous chapter was the set of functions on {β ,β‘}, which is the set Hom({β ,β‘},{β ,β‘}) with composition in the category Set. Any category π can give us a lot of examples of monoids similar to this one.
Definition. In a category π, an endomorphism is a morphism f: A -> A with the same domain as codomain. We write Endo(A) = Hom(A,A) for the monoid of endomorphisms on A, with composition as operation. β
Example. Let π be a category. We define a category π^op by Ob(π^op) = Ob(π), π^op(A,B) = π(B,A) and the composition f β g in π^op is defined as the composition g β f in π. The category π^op is called the opposite category of π, which is the category π "with the arrows reversed". β
Example. Let π and π be categories. We define a category π Γ π. Objects in π Γ π are pairs (C,D) of an object C in π and an object D in π. A morphism from (C,D) to (C',D') is a pair of morphisms (f,g) with f: C -> C' in π and g: D -> D' in π. Composition of morphisms is defined by (h,j) β (f,g) = (h β f, j β g). The category π Γ π is called the product category of π and π. β
Here are some examples of finite categories:
Example. The category β has two objects A and B, and four arrows id_A: A -> A, id_B: B -> B, f: A -> B and g: A -> B. Composition of arrows is uniquely determined by the definition of a category. β
Example. The category 3 has three objects 0, 1 and 2 and six arrows (0,0): 0 -> 0, (0,1): 0 -> 1, (0,2): 0 -> 2, (1,1): 1 -> 1, (1,2): 1 -> 2 and (2,2): 2 -> 2. Composition is given by (b,c) β (a,b) = (a,c). The identity arrows are id_a = (a,a). β
Example. The category β‘ has four objects A, B, C and D and nine arrows, of which the non-identity arrows are f: A -> B, g: A -> C, f': C -> D, g': B -> D and h: A -> D. We have f' β g = g' β f = h. β
Besides endomorphisms, there are other kinds of special arrows in a category. I'll list some of them here:
Definition. An arrow f: A -> B is a:
Monomorphism iff, for all objects C and all arrows g,h: C -> A, if f β g = f β h, then g = h;
Epimorphism iff, for all objects C and all arrows g,h: B -> C, if g β f = h β f, then g = h;
Isomorphism iff there is an arrow g: B -> A for which g β f = 1_A and f β g = 1_B. β
In the last case, the arrow g: B -> A is unique and is called the inverse arrow of f. It is denoted fβ»ΒΉ. In Set, mono-, epi- and isomorphisms are injections, surjections and bijections respectively.
Functor
Definition. Let π and π be categories. A (covariant) functor F from π to π has the following data:
For each object A in π, an object F(A) in π;
For each arrow f: A -> B in π, an arrow F(f): F(A) -> F(B) in π;
For arrows f: A -> B and g: B -> C in π, we have F(g β f) = F(g) β F(f);
For each object A in π, we have F(1_A) = 1_F(A). β
Example. The list functor list: Set -> Set maps a set X to the set list(X) of finite lists of elements of X. It maps a function f: X -> Y to a function list(f): list(X) -> list(Y) that maps the list (xβ,...,xβ) of elements in X to the list (f(xβ),...,f(xβ)) of elements in Y. β
Example. Given categories π and π and an object X of π, we can define the constant functor const_X: π -> π by const_X(A) = X and const_X(f) = 1_X. β
A contravariant functor from a category π to a category π is a functor from π^op to π.
Example. The powerset functor P: Set^op -> Set maps a set A to its powerset P(A), i.e. its set of subsets. It maps a function f: A -> B in Set (i.e. an arrow f: B -> A in Set^op) to the function P(f): P(B) -> P(A) defined by P(f)(X) = {x in A | f(x) in B}. β
Example. A functor F: 3 -> π corresponds to a composable pair of arrows in π. Here, a composable pair is a pair (f,g) of arrows s.t. the domain of g is the codomain of f (i.e. f: A -> B and g: B -> C for some A,B,C). Given a functor F: 3 -> π, we can find the composable pair by (F((0,1)),F((1,2))), and given a composable pair (f,g) with f: A -> B and g: B -> C, we can define F by setting F(0) = A, F(1) = B, F(2) = C, F((0,1)) = f, F((1,2)) = g, and then F((0,2)) must be the composition g β f. β
Example. A functor F: β -> π corresponds to a pair of parallel arrows in π. Here, arrows f,g are parallel iff they have the same domain and codomain as eachother, i.e. f: A -> B and g: A -> B for some A and B. Sometimes, we write f,g: A β B to denote f and g are parallel. β
Example. Given a category π, the identity functor 1_π: π -> π is defined by 1(A) = A and 1(f) = f. β
Example. For functors F: π β π and G: π β β°, we their composition G β F is a functor defined by by (G β F)(A) = G(F(A)) and (G β F)(f) = G(F(f)). β
As you might notice, for any two (small) categories π and π, there is a set of functors from π to π, there is an identity fuctor 1_π: π -> π on any category any we can compose two functors into a new functor. So, the collection of small categories and functors between them forms a category:
Definition. We define the category Cat. Objects of Cat are small categories, i.e. categories π for which Ob(π) and π(A,B) are sets. Arrows in Cat are functors and composition is functor composition. β
An endofunctor is an endomorphism in the category of categories. I.e. an endofunctor is a functor F: π -> π from a category to itself.
The category Cat has more data than just objects and arrows: it also has arrows between (parallel) arrows, making it into a 2-category. We'll see what these arrows between arrows are in the next chapter.
Natural Transformation
Definition. Given categories π and π and parallel functors F,G: π β π, a natural transformation Ξ± from F to G has the following data:
For each object A of π, an arrow Ξ±_A: F(A) -> G(A) in π;
For each arrow f: A -> B in π, we have Ξ±_B β F(f) = G(f) β Ξ±_A. β
The second bullet point is called the naturallity condition.
Example. We define a natural transformation Ξ±: 1 -> list. For each set A, Ξ±_A is a function from 1(A), which is just A, to list(A), the set of lists of elements of A. For x in A, we set Ξ±_A(x) = (x,x) to be the list of x repeated twice. We can verify this is natural: for a function f: A -> B, we have that Ξ±_B(f(x)) = list(f)(Ξ±_A(x)) = (f(x),f(x)). β
Example. We define Ξ±: P -> P on the powerset functor. For each set A, Ξ±_A is a function from P(A) to P(A). For a subset X of A, we set Ξ±_A(X) to be the complement A \ X of X in A, i.e. the set of all elements of A that are not in X. For a function f: A -> B (an arrow f: B -> A in Set^op), we see that Ξ±_A(P(f)(X)) = A \ fβ»ΒΉ(X) and P(f)(Ξ±_B(X)) = fβ»ΒΉ(B \ X). As A \ fβ»ΒΉ(X) = fβ»ΒΉ(B \ X), this transformation is natural. β
Functors and natural transformations between functors form a category, as defined below.
Definition. For categories π and π, we define the category of functors [π,π]. Objects in [π,π] are functors F: π β π. For functors F,G β [π,π], arrows from F to G are natural transformations Ξ±: F -> G. For natural transformations Ξ±: F -> G and Ξ²: G -> H, we define their composition Ξ² β Ξ± by (Ξ² β Ξ±)_A = Ξ²_A β Ξ±_A for objects A in π. β
The identity natural transformation is given by id_F: F -> F, (id_F)_A = id_F(A).
A natural isomorphism is an isomorphism in the category of functors [π,π]. A natural transformation Ξ±: F -> G is a natural isomorphism iff each Ξ±_A is an isomorphism, in which case the inverse is given by (Ξ±β»ΒΉ)_A = (Ξ±_A)β»ΒΉ.
We can compose two natural transformations between a triple of parallel functors, but we can also whisker natural transformations with functors:
Definition. Let π, π and β° be categories. Let F,G: π β π and H,J: π β β° be functors. Let Ξ±: F -> G and Ξ²: H -> J be natural transformations. We define natural transformations HΞ±: π -> β° and Ξ²F: π -> β°. For an object A in π, set (HΞ±)_A = H(Ξ±_A) and set (Ξ²F)_A = Ξ²_(F(A)). β
Composing a natural transformation and a functor into a new natural transformation like HΞ± or Ξ²F is called whiskering.
Monoidal Category
Definition. A monoidal category has the following data:
A category π;
A functor β: π Γ π -> π, where we write A β B for β(A,B) and f β g for β(f,g);
An object I β π;
An associativity law Ξ± where, for objects A,B,C in π, we have an isomorphism Ξ±_(A,B,C): (A β B) β C -> A β (B β C) (i.e. Ξ± is a natural isomorphism between functors π Γ π Γ π -> π, one defined by F(A,B,C) = (A β B) β C and F(f,g,h) = (f β g) β h, and the other defined by G(A,B,C) = A β (B β C) and G(f,g,h) = f β (g β h);
A left-unit law Ξ» (a natural isomorphism) where, for an object A in π, we have an isomorphism Ξ»_A: I β A -> A;
A right-unit law Ο (a natural isomorphism) where, for an object A in π, we have an isomorphism Ο_A: A β I -> A;
For objects A,B β π, we have (1_A β Ξ»_B) β Ξ±_(A,I,B) = Ο_A β 1_B;
For objects A,B,C,D β π, we have Ξ±_(A,B,CβD) β Ξ±_(AβB,C,D) = (1_A β Ξ±_(B,C,D)) β Ξ±_(A,BβC,D) β (Ξ±_(A,B,C) β 1_D). β
The last bullet point is called the pentagonator. The last two points might have been hard to follow, so here are some diagrams:
I hope these diagrams help.
We usually write a monoidal category as (π,β,I). The laws (associativity and units) are similar to the conditions for a set with binary operation to be a monoid as in the first chapter. However, we now also have the two commutative diagrams above (the lower one being the pentagonator), requiring that these laws satisfy something like higher coherence conditions. This makes the cateogory π along with the bifunctor (functor from a product of two categories) β and the object I a monoid up to natural isomorphisms. The laws Ξ±,Ξ»,Ο don't require for objects such as (A β B) β C and A β (B β C) to be literally equal, only to be isomorphic in a natural way.
We refer to the bifunctor β as the tensor product of the monoidal category.
Example. The category Set of sets can be extended to a monoidal category by letting A β B be the Cartesian product of A and B, i.e. the set of pairs (a,b) for a in A and b in B. We let f β g map (a,b) to (f(a),f(b)). We set I to be the singleton set {*}. Ξ±_(A,B,C) maps ((a,b),c) to (a,(b,c)). Ξ»_A maps (*,a) to a and Ο_A maps (a,*) to a. We write this monoidal category as (Set,Γ,1). β
Example. The category Top of topological spaces can be extended to a monoidal category in a similar way. A β B is the product space of A and B. The rest of the definitions are the same as for Set. We write this monoidal category as (Top,Γ,1). β
Example. The category Set of sets can be extended to a monoidal category a different way. We set A β B to be the disjoint union A β B of A and B, i.e. the set of (0,a) and (1,b) for a in A and b in B. For f: A -> C and g: B -> D, we define f β g: A β B -> C β D by setting (f β g)(0,a) = f(a) and (f β g)(1,b) = g(b). We set I to be the empty set {}. Ξ±_(A,B,C) maps (0,(0,a)) to (0,a), (0,(1,b)) to (1,(0,b)) and (1,c) to (1,(1,c)). Ξ»_A maps (1,a) to a and Ο_A maps (0,a) to a. We write this monoidal category as (Set,β,β ). β
The example that is important to us now is the monoidal category of endofunctors:
Example. The category [π,π] of endofunctors on a category π can be extended to a monoidal category by letting F β G to be the composition F β G of F and G. We set I to be the identity functor 1: π -> π. For natural transformations Ξ²: F -> H and Ξ³: G -> J, we define Ξ² β Ξ³: F β G -> H β J by (Ξ² β Ξ³)_A = Ξ²_A β Ξ³_A. The laws Ξ±,Ξ»,Ο are simply the identity, i.e. Ξ±_(F,G,H) = 1_(F β G β H), and Ξ»_F = Ο_F = 1_F. We write this monoidal category as ([π,π],β,1). β
Monoid over a Monoidal Category
Definition. Let (π,β,I) be a monoidal category. A monoid over (π,β,I) has the following data:
An object M in π;
An arrow m: M β M -> M;
An arrow e: I -> M;
We have m β (1_M β m) β Ξ±_(M,M,M) = m β (m β 1_M);
We have m β (e β 1_M) = Ξ»_M;
We have m β (1_M β e) = Ο_M. β
Here is another diagram to help:
It's more off-center this time.
We usually write the data of a monoid as (M,m,e).
Example. A monoid over (Set,Γ,1) is a monoid as in the first chapter. The arrow m: M Γ M -> M is the operation β, and the arrow e: 1 -> M specifies a neutral element e(*) of M. The diagrams above represent associativity of m and neutrality of e with respect to m respectively. β
Example. A monoid over (Top,Γ,1) is a monoid as in the first chapter, where the operation is continuous. β
Example. A monoid over (Set,β,β ) is uniquely determined by its set M. The function e: β -> M is the empty function and, by neutrality of e, m: M β M -> M maps both (0,a) and (1,a) to a. β
The example we're interested in are monoids over the category of endofunctors.
Definition. A monad over a category π is a monoid (T,ΞΌ,Ξ·) in the monoidal category ([π,π],β,1) of endofunctors with composition. β
In this category, the laws are simply all identity, so the diagrams for associativity and neutrality simplify a lot:
Here, I wrote T^n for the n-fold composition of T with itself, i.e. TΒ² = T β T and TΒ³ = T β T β T. On the left is associativity of the multiplication ΞΌ: TΒ² -> T, and on the right is neutrality of Ξ·. The equal sign in the right diagram represents the identity arrow from T to T. The maps ΞΌT, TΞΌ, Ξ·T and TΞ· are defined by whiskering as explained in the chapter Natural Transformation. Whiskering a natural transformation Ξ± with T is the result of applying the tensor product of ([π,π],β,1) to the natural transformation Ξ± and the identity natural transformation 1_T.
These two diagrams commuting is equivalent to the following two diagrams commuting for each object A of π:
These diagrams are simply the result of putting A everywhere.
ΞΌ is called multiplication and Ξ· is called unit of the monad.
The rest of this blog post focusses on monads over Set. To write it all out, a monad over Set has the following data and conditions:
For every set A, there is a set T(A);
For every function f: A -> B, there is a function T(f): T(A) -> T(B);
For every set A, there are functions Ξ·_A: A -> T(A) and ΞΌ_A: T(T(A)) -> T(A);
For every function f: A -> B, we have Ξ·_B(f(x)) = T(f)(Ξ·_A(x)) and ΞΌ_B(T(T(f))(y)) = T(f)(ΞΌ_A(y)) for x in A and y in T(T(A));
For every set A, ΞΌ_A(ΞΌ_T(A) (x)) = ΞΌ_A(T(ΞΌ_A)(x)) for x in T(T(T(A)));
For every set A, ΞΌ_A(Ξ·_T(A) (x)) = ΞΌ_A(T(Ξ·_A)(x)) = x for x in T(A).
Example. list is a monad with functor list: Set -> Set, unit Ξ·_A(x) = (x) and multiplication ΞΌ_A(((x_11,...,x_1nβ),...,(x_m1,...,x_mnβ))) = (x_11,...,x_1nβ,...,x_m1,...,x_mnβ). β
Verifying the example above is indeed a monad is left to the reader.
Algebra
Definition. Let (T,ΞΌ,Ξ·) be a monad over π. A T-algebra is a pair (X,f) with an object X in π and an arrow f: T(X) -> X so that f β Ξ·_X = 1_X and f β T(f) = f β ΞΌ_X. β
X is called the carrier and f is called the action of the algebra.
Example. A list-algebra is a monoid. β
I'm eepy now. Goodbye! Maybe I'll make a post on T-algebras later.
