Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: how are monads used?

David Egolf (Sep 21 2023 at 17:26):

Over the last few days, the concept of a monad has (finally) started making some sense to me! It feels like this opens up a huge amount of new things that I can learn about now, which is exciting.

By the way, the resources that made things start to intuitively click for me were:

• the introduction to monads in the context of probability monads in sections 1.1 of Paolo Perrone's thesis
• the crash course on monads and their algebras in section 2.4 of "Higher-Dimensional Categories", by Eugenia Cheng and Aaron Lauda.

At this point, I'm curious to learn what people use monads for, at a very high level! Here are some of the examples I've seen so far:

• We can use monads to talk about relationships between "iterated versions" of some kind of construction. The example I've read about here is that we can use monads to talk about probability distributions of probability distributions. The monad endofunctor $P$ sends an object $X$ to an object $PX$ describing probability distributions on $X$. Interestingly, the natural transformation $\mu: PP \to P$ with components $\mu_X: PPX \to PX$ sends each "probability distribution of probability distributions" to a single probability distribution, I think intuitively obtained by taking a probability-weighted average.
• We can use monads to convert objects into new objects that contain formal combinations of the parts of the original object. Then (at least sometimes) we can define an algebra for this monad that takes these formal combinations and returns parts of the original object. For example, I think there is a monad with endofunctor $T: \mathsf{Set} \to \mathsf{Set}$ that sends a set to the underlying set of the free monoid on that set. For example, $T\{a,b,c\}$ is a set that contains elements like $abbc$ and $babc$. Then a (structured enough) function $T\{a,b,c\} \to \{a,b,c\}$ is like a "multiplication rule" that takes in ordered tuples of elements from $\{a,b,c\}$ and returns an element from $\{a,b,c\}$. As another cool example, we can send a directed graph $G$ to the underlying graph of the free category induced by $G$. Intuitively, this augments $G$ so that it has a directed edge for every tuple of "composable directed edges".
• We can use monads to augment objects by adding in some constant additional data to each object. For example, in the maybe monad our endofunctor $(-)_*: \mathsf{Set} \to \mathsf{Set}$ adds an additional point to each set. So a set $S$ gets augmented to the set $S \coprod \{*\}$. I would guess that we can generalize this by taking coproducts with any fixed object.
• Once we have defined a monad with endofunctor $T$, we can consider morphisms of the form $f:X \to TY$ (called "Kleisli morphisms"), which map from one of our original objects to one of our fancier objects that we've formed by using our monad endofunctor. These let us consider "hybrid" relationships between objects at different "tiers" of application of $T$. For example, if $T: \mathsf{Set} \to \mathsf{Set}$ is the powerset endofunctor, then a function $f: X \to TY$ maps each element of $X$ to some subset of $Y$. Or if $T$ sends each set to the set of probability distributions on that set, then a function $f: X \to TY$ associates to each element of $X$ a probability distribution on $Y$. Apparently, we can form a new category with our original objects, but where the morphisms are these fancier Kleisli morphisms.

Broadly, what are some other ways in which people use monads?

Ryan Wisnesky (Sep 21 2023 at 17:43):

To make burritos! https://emorehouse.wescreates.wesleyan.edu/silliness/burrito_monads.pdf

Patrick Nicodemus (Sep 21 2023 at 17:52):

Monads are used in homological algebra because they contain the necessary data to carry out the "bar construction."

As a first approximation, you can think of homological algebra as being an approach to algebra which allows us to embed ordinary algebra of groups, rings and modules into the broader universe of topological rings, groups and modules. Sometimes you can then replace your complicated group with a topological group which is simpler in some regards.

More concretely, say you have an Abelian group $G$ which has lots of torsion in it which makes it hard to study. Homological algebra suggests trying to replace $G$ with a similar "topological group" (a simplicial complex with a group structure) $G'$ which is equivalent to $G$ in some respects but its group complexity is spread out and stratified through the dimensions of $G'$. So $G'$ has vertices, edges, faces and so on, its vertices form a group $G'_0$, its edges form a group $G'_1$, its faces form a group $G_2'$, and so on, and these operations are all compatible with each other. The important thing is that each of the individual groups $G_0',G_1',G_2'$ should all be relatively simple and better behaved/easy to understand than $G$. For example they should all be free Abelian groups. Thus in some sense we're trading off algebraic complexity for the geometric complexity of having a space spread out across multiple dimensions.

Monads can be used in an algorithm called the bar construction which associates to each algebraic object a "simplicial complex" of algebras which are free in each dimension. They are fundamental to homological algebra and many basic concepts of homological algebra can be understood in terms of monads.

David Egolf (Sep 21 2023 at 18:27):

Ryan Wisnesky said:

To make burritos! https://emorehouse.wescreates.wesleyan.edu/silliness/burrito_monads.pdf

That was a delightful read, and surprisingly helpful for providing some intuition e.g. for the concept of a strong monad!

David Egolf (Sep 21 2023 at 18:59):

Patrick Nicodemus said:

More concretely, say you have an Abelian group $G$ which has lots of torsion in it which makes it hard to study. Homological algebra suggests trying to replace $G$ with a similar "topological group" (a simplicial complex with a group structure) $G'$ which is equivalent to $G$ in some respects but its group complexity is spread out and stratified through the dimensions of $G'$.

Thus in some sense we're trading off algebraic complexity for the geometric complexity of having a space spread out across multiple dimensions.

Monads can be used in an algorithm called the bar construction which associates to each algebraic object a "simplicial complex" of algebras which are free in each dimension.

That's fascinating! In very broad terms, I guess this example shows that a monad can be used to "distribute" the complexity of an object of interest, across multiple simpler things.

I've been having fun looking at the very start of some books on homological algebra recently (e.g. I've been working on trying to understand the concept of a singular p-simplex and the boundary operator the last few days). Now that I know this very cool "bar construction" exists, that gives me some more motivation to keep learning things in this direction!

Patrick Nicodemus (Sep 21 2023 at 19:06):

Yes, the singular p-simplex is an example of what i'm talking about here. There is something called the "cone monad" on topological spaces, which associates to each topological space $X$ the cone $C(X)$ = $(1 \amalg (X\times [0,1]))/\sim$, where $1$ is a singleton space, and $\sim$ is the smallest equivalence relation on the space such that $(x,0)\sim 1$ for all $x,x'\in X$. I will let you work out what the multiplication and unit natural transformations are.

If you apply this to the empty space $n$ times in a row, you get the $n$ simplex. So a singular $p$-simplex in a topological space $X$ is constructed by applying the monad $C$ to the empty space $p$ times and then homming it into $X$.

Patrick Nicodemus (Sep 21 2023 at 19:07):

Simplicial methods in topology and homological algebra are very closely tied to monads or monoids in the general sense of monoidal category theory. Anywhere you see one, you are likely to see the other nearby.

Patrick Nicodemus (Sep 21 2023 at 19:10):

The boundary operator is also constructed from the unit natural transformation of the monad $C$.

Patrick Nicodemus (Sep 21 2023 at 19:10):

(by precomposing with it)

Chris Grossack (they/them) (Sep 22 2023 at 04:08):

To every adjunction $L \dashv R$, the composite $RL$ is a monad! Indeed, in case of algebraic structures, like groups, the free-forgetful adunction $UF : \mathsf{Set} \to \mathsf{Set}$ is exactly the monad describing the algebraic gadget which you've already mentioned. Now, why does it matter that adjunctions give rise to monads?

Chris Grossack (they/them) (Sep 22 2023 at 04:09):

Say you have a category $\mathcal{C}$ and a functor $R : \mathcal{C} \to \mathcal{D}$. A very natural question is to try and understand the image of $R$. Well in nice cases, $R$ admits a left adjoint $L \dashv R$, and this gives us something to work with!

Indeed, every object $Rc \in \mathcal{D}$ in the image of $R$ is automatically an algebra for the monad $$RL : \mathcal{D} \to \mathcal{D}$! (Can you see why? As a hint, consider the counit $\epsilon_c : LRc \to c$). So if we're trying to understand the image of $R$ we know that we can restrict attention to the $RL$-algebras in $\mathcal{D}$!

Chris Grossack (they/them) (Sep 22 2023 at 04:12):

This is already great, but we can do more! Indeed, every $Rc$ admits the structure of an $RL$-algebra, and so we can look at the category $\mathcal{D}^{RL}$ of $RL$-algebras in $\mathcal{D}$. We know that $\mathcal{C}$ has an adjunction $L \dashv R$ over $\mathcal{D}$, and the category $\mathcal{D}^{RL}$ also has a free-forgetful adjunction $F \dashv U$ over $\mathcal{D}$. Moreover, we've just said that $R : \mathcal{C} \to \mathcal{D}$ factors through $\mathcal{D}^{RL}$, and now we have more structure (the structure of $RL$-algebras) to help us understand the image of $R$.

Chris Grossack (they/them) (Sep 22 2023 at 04:15):

There are general theorems which tell us when this lifted functor $R : \mathcal{C} \to \mathcal{D}^{RL}$ is fully faithful (in which case $R$ is called a descent morphism) or in the best case when $R$ is an equivalence (in which case we call it effective descent). These monadicity theorems are extremely important, since they let us understand the (potentially complicated) category $\mathcal{C}$ in terms of its image in the (potentially simpler) category $\mathcal{D}$ (as long as we only look at the $RL$-structured objects in $\mathcal{D}$).

Chris Grossack (they/them) (Sep 22 2023 at 04:19):

(also as an aside, adjunctions are incredibly useful, and in some sense monads allow us to detect adjunctions. Indeed, we know that the composite $RL$ will always be a monad. In fact the converse is also true -- every monad is of the form $RL$ for some adjunction!

The kleisli category and the eilenberg-moore category give us two such "factorizations" for our monad! It turns out we have a category worth of factorizations, and the kleisli category is initial among the factorizations, while the eilenberg-moore category is terminal!)

Ralph Sarkis (Sep 22 2023 at 05:30):

In case the category $\mathbf C$ is posetal (i.e. it comes from a partially ordered set), a monad on $\mathbf C$ is a closure operator (a monotone, extensive and idempotent function). One could make a list of how closure operators are used just as long as what's above.

John Baez (Sep 22 2023 at 08:47):

All great answers! And nobody has even talked much about how monads are used in computer languages like Haskell... although I imagine that famous "burrito" explanation is aimed at programmers. (I haven't actually read it, just heard people talk about it!)

John Baez (Sep 22 2023 at 08:52):

I noticed that @David Egolf mentioned the Kleisli category of a monad. He should really get to know its partner in crime, the Eilenberg-Moore category. That's what I like best about monads: a monad on a category $\mathsf{C}$ is a way of describing a kind of algebraic gadget that has an underlying object living in $\mathsf{C}$, and the category of those algebraic gadgets is the Eilenberg-Moore category of that monad.

John Baez (Sep 22 2023 at 08:52):

For example there's a monad on $\mathsf{Set}$ called "the monad for groups", and the Eilenberg-Moore category of that monad is the category of groups.

John Baez (Sep 22 2023 at 08:53):

The Kleisli category of that monad is the category of free groups, and that's how it always works.

John Baez (Sep 22 2023 at 08:54):

I try to call the Eilenberg-Moore category of a monad the category of "algebras" of that monad, because 1) that's what it is, and 2) the phrase "Eilenberg-Moore" is long, uninformative, and initially quite intimidating.

John Baez (Sep 22 2023 at 08:55):

I try to call the Kleisli category the category of "free algebras" of the monad.

David Egolf (Sep 23 2023 at 00:00):

Patrick Nicodemus said:

Yes, the singular p-simplex is an example of what i'm talking about here. There is something called the "cone monad" on topological spaces...

If you apply this to the empty space $n$ times in a row, you get the $n$ simplex. So a singular $p$-simplex in a topological space $X$ is constructed by applying the monad $C$ to the empty space $p$ times and then homming it into $X$.

Thanks for introducing me to this "cone monad"! The idea of repeatedly applying the endofunctor of a monad to some particular object to get a sequence of objects is quite interesting. While doing some reading to better understand your answer, I ran across these notes (from a lecture given by John Baez, taken by Derek Wise). From those notes, I found the two images below to be very interesting to compare, and I think they relate closely to the idea of repeatedly applying the endofunctor of a monad:

repeatedly apply "round trip" of an adjunction

special morphisms between parts of a simplex

Comparing these two images in the context of the cone endofunctor, I wonder if the cone monad not only generates simplexes of increasing dimension (by repeatedly applying the cone endofunctor to the empty space), but potentially also provides the face and degeneracy maps relating these simplexes. The cone monad would (potentially) provide these maps in terms of certain parts of the unit and counit of some adjunction that induces the cone monad.

David Egolf (Sep 23 2023 at 00:10):

Looking again at the first image above, it seems like we can get a lot of objects $d, LRd, LRLRd, \dots$ and morphisms between these by starting with two ingredients:

1. an object $d$ in a category $D$
2. an adjunction $L: C \to D$, $R: D \to C$, where $L$ is left adjoint to $R$

It intuitively seems like these objects and morphisms could be used to generate a category that would contain a lot of information about $d$ (in the form of relationships between $d$ and objects generated using $d$ and an adjunction). Maybe this could be a useful trick if one ever wishes to "zoom in" on objects in a category, and view those objects as categories in their own right.

Perhaps a related idea could also be interesting, where one repeatedly applies the endofunctor of a monad and attempts to generate a category.

John Baez (Sep 23 2023 at 09:32):

David Egolf said:

Looking again at the first image above, it seems like we can get a lot of objects $d, LRd, LRLRd, \dots$ and morphisms between these by starting with two ingredients:

1. an object $d$ in a category $D$
2. an adjunction $L: C \to D$, $R: D \to C$, where $L$ is left adjoint to $R$

It intuitively seems like these objects and morphisms could be used to generate a category that would contain a lot of information about $d$ (in the form of relationships between $d$ and objects generated using $d$ and an adjunction).

Congratulations, you've reinvented an important idea! It's best to start by doing the 'abstract' case where you ignore the specific object $d$ and even your specific choice of adjunction $L, R$, and just think about the so-called 'walking' or 'free-floating' adjunction, devoid of any specific details.

John Baez (Sep 23 2023 at 09:34):

The walking adjunction is a 2-category $\mathbf{Adj}$ with two objects $C$ and $D$, two morphisms $L: C \to D$ and $R: D \to C$, and two 2-morphisms $\iota: 1_C \to RL, \epsilon: LR \to 1_D$ obeying the usual equations that the unit and counit of an adjunction obey.

John Baez (Sep 23 2023 at 09:36):

Then, any specific adjunction is a 2-functor $F: \mathbf{Adj} \to \mathbf{Cat}$.

John Baez (Sep 23 2023 at 09:36):

This maps the abstract objects $C$ and $D$ to specific categories, $L$ and $R$ to specific adjoint functors, etc.

John Baez (Sep 23 2023 at 09:37):

The general structure of adjunctions, and all the things you can do with them, is more conveniently studied in the walking adjunction, freed from the clutter of specific details.

John Baez (Sep 23 2023 at 09:38):

Then you can apply that knowledge to specific cases, like the category you're building. (You'll notice that while you were just acting as if you're talking about a specific adjunction, you're not telling us what it is, so you might as well be working abstractly.)

John Baez (Sep 23 2023 at 09:42):

I think the Spring 2007 seminar notes you were reading give a gentle introduction to a lot of these ideas and how they're used in math.

John Baez (Sep 23 2023 at 09:42):

But I may have sidestepped discussion of the walking adjunction $\mathbf{Adj}$.

John Baez (Sep 23 2023 at 09:45):

For an introduction to that - and a lot of the same material as in the Spring 2007 notes, viewed from a different angle - try these other seminar notes:

• Category Theory: Fall 2018 notes.

John Baez (Sep 23 2023 at 09:47):

Weeks 4-7 lead up to a treatment of the walking adjunction! Then I go on and use it to study the bar construction.

John Baez (Sep 23 2023 at 09:49):

You can see morphisms in the category you're talking about in pictures like
this:

John Baez (Sep 23 2023 at 09:50):

but in the "walking" case, not any concrete case. (Also, this particular picture focuses on what you can do with an object $c \in C$, not your $d \in D$. They're both equally interesting!)

Patrick Nicodemus (Sep 23 2023 at 13:37):

@David Egolf at this point it's useful to start synthesizing your comments with what Chris pointed out, that adjunctions give rise to monads. For any adjunction (L, R), RL is a monad, and you can choose the unit of the monad to be the unit $\iota : 1\to RL$ of the adjunction, and the multiplication $\mu : RLRL\to RL$ would be the natural transformation $R\varepsilon L$.
Dually, $LR$ is a comonad, with counit $\varepsilon$ given by the counit of the adjunction, and comultiplication $\delta$ given by $L\iota R$.
In the notes by Derek Wise you posted, all the important morphisms in those pictures are built out of not just the unit and counit of the adjunction but more specifically the maps $\varepsilon$, $L\iota R$, and by repeated application of the functor $LR$. For this reason I claim that the picture could be also written, after a change of notation, using only the symbols $\varepsilon$, $\delta=L\iota R$, and $G=LR$. The theorem "every adjunction can be used to construct simplicial objects" can be broken down into two parts as "every adjunction gives rise to a comonad, and every comonad can be used to construct simplicial objects".

Patrick Nicodemus (Sep 23 2023 at 13:41):

So your question "is there an adjunction which can be used to produce the face and degeneracy maps between simplices?" The answer is yes, and the other answers explaining how you can use the Kleisli category and Eilenberg-Moore category to build adjunctions from monads are a hint to show how to get there. But those face and degeneracy operators between simplices can be constructed directly from the unit and multiplication of the cone monad without using this monad <=> adjunction translation.

David Egolf (Sep 24 2023 at 05:22):

I wanted to thank everyone for their responses! This has been a lot of fun so far. I'm still working through each answer roughly in order, so it's going to take me a while to properly read the most recent comments.

David Egolf (Sep 24 2023 at 21:11):

Chris Grossack (they/them) said:

Say you have a category $\mathcal{C}$ and a functor $R : \mathcal{C} \to \mathcal{D}$. A very natural question is to try and understand the image of $R$. Well in nice cases, $R$ admits a left adjoint $L \dashv R$, and this gives us something to work with!

Indeed, every object $Rc \in \mathcal{D}$ in the image of $R$ is automatically an algebra for the monad $RL : \mathcal{D} \to \mathcal{D}$! (Can you see why? As a hint, consider the counit $\epsilon_c : LRc \to c$). So if we're trying to understand the image of $R$ we know that we can restrict attention to the $RL$-algebras in $\mathcal{D}$!

(I added a missing "$" to the above).

Thanks for your interesting comment! I am currently working on understanding this part: "every object $Rc \in \mathcal{D}$ in the image of $R$ is automatically an algebra for the monad $RL : \mathcal{D} \to \mathcal{D}$".

To define an algebra, we need two things:

• an object $A$
• a morphism $TA \to A$, where $T$ is our monad endofunctor

In our case, the monad endofunctor is $RL$. And our object for our algebra is $Rc$.
So, we are looking for a morphism from $(RL)Rc$ to $Rc$. Using the provided hint, we consider the component of the counit at $c$, namely $\epsilon_c: LRc \to c$. Since $R$ is a functor, we can apply it to the morphism $\epsilon_c$ to obtain $R(\epsilon_c): R(LRc) \to Rc$. So, I am guessing that we get an algebra for each object in the image of $R: \mathcal{C} \to \mathcal{D}$ as follows:

• our object is an object in the image of $R$, namely $Rc$
• our morphism is $R(\epsilon_c): RLRc \to Rc$, where $\epsilon_c$ is the component at $c$ of the counit for the adjunction $L \dashv R$

However, if this is to actually be an algebra, $Rc$ and $R(\epsilon_c):(RL)(Rc) \to Rc$ need to satisfy a couple additional conditions. Namely, the "unit" and "composition" diagrams need to commute. This is the point where I start feeling a bit out of my depth, and like I need to work some exercises with these concepts.

(For example, it would probably be good for me to figure out exactly how an adjunction $L \dashv R$ induces a monad. The monad endofunctor is $RL$, but to define a monad also requires specifying a unit natural transformation and a multiplication natural transformation.)

Chris Grossack (they/them) (Sep 24 2023 at 22:38):

David Egolf said:

So, I am guessing that we get an algebra for each object in the image of $R: \mathcal{C} \to \mathcal{D}$ as follows:

• our object is an object in the image of $R$, namely $Rc$
• our morphism is $R(\epsilon_c): RLRc \to Rc$, where $\epsilon_c$ is the component at $c$ of the counit for the adjunction $L \dashv R$

That's exactly right!

However, if this is to actually be an algebra, $Rc$ and $R(\epsilon_c):(RL)(Rc) \to Rc$ need to satisfy a couple additional conditions. Namely, the "unit" and "composition" diagrams need to commute. This is the point where I start feeling a bit out of my depth, and like I need to work some exercises with these concepts.

(For example, it would probably be good for me to figure out exactly how an adjunction $L \dashv R$ induces a monad. The monad endofunctor is $RL$, but to define a monad also requires specifying a unit natural transformation and a multiplication natural transformation.)

These sound like excellent exercises! The unit of the monad $\eta : 1 \Rightarrow RL$ should sound very similar to the unit of the adjunction $L \dashv R$, so you should get that one quickly. The multiplication should be $\mu : RLRL \Rightarrow RL$, and you'll want to reuse an idea from your solution to the previous exercise (about an algebra structure on $Rc$). The real exercise, though, will be checking that $\mu$ is associative and compatible with $\eta$. While you're at it, I recommend thinking about exactly what the arrows you're building (and the diagrams you're chasing) mean in the case of simple free/forgetful adjunctions for groups and vector spaces. If you have any other favorite adjunctions (and if you don't, check out these questions: 1, 2) it's worth working out more of these examples to keep building intuition ^_^