Now we have seen monads on 2-categories and bicategories, we are in a position to introduce some new ideas.

We have encountered various notions of monads so far, including:

These are all special cases of monads in a bicategory. This time, we are going to see a genuine generalisation. To do so, we follow a well-worn categorical trail, and adopt a functorial perspective on a familiar object, the monads themselves. This will give us yet another way of describing monads, and a suitable starting point for generalisation. The resulting graded monads are a powerful tool for modelling resource usage in a monadic setting.

A 2-Functorial Perspective

In ordinary category theory, we often consider the points in a category as morphisms from the terminal object. For example, in $\mathsf{Set}$ , the elements of a set $X$ bijectively correspond to functions of type $\{ \star \} \rightarrow X$ with domain the terminal object.

To think about the points of a 2-category, we need to introduce 2-functors. A strict 2-functor $\mathbf{F} : \mathbf{A} \rightarrow \mathbf{B}$ consists of:

A map on 0-cells, $\mathcal{C} \;\mapsto\; \mathbf{F}(\mathcal{C})$ .
A map on 1-cells, $F : \mathcal{C} \rightarrow \mathcal{D} \;\mapsto\; \mathbf{F}(F) : \mathbf{F}(\mathcal{C}) \rightarrow \mathbf{F}(\mathcal{D})$ .
A map on 2-cells, $\alpha : F \Rightarrow G \;\mapsto\; \mathbf{F}(\alpha) : \mathbf{F}(F) \Rightarrow \mathbf{F}(G)$ .

These maps preserve identities

$\mathbf{F}(\mathsf{Id}_{\mathcal{C}}) = \mathsf{Id}_{\mathbf{F}(\mathcal{C})} \qquad \mathbf{F}(\mathsf{id}_F) = \mathsf{id}_{\mathbf{F}(F)}$

and composition

$\mathbf{F}(G \circ F) = \mathbf{F}(G) \circ \mathbf{F}(F) \qquad \mathbf{F}(\beta \cdot \alpha) = \mathbf{F}(\beta) \cdot \mathbf{F}(\alpha)$

in the obvious way.

Put another way, a strict 2-category is simply a $\mathsf{Cat}$ -enriched category, and strict 2-functors are then $\mathsf{Cat}$ -enriched functors.

The terminal 2-category $1$ is the category with one 0, 1 and 2-cell. Explicitly, we have:

A 0-cell $\star$ .
An identity 1-cell $\mathsf{Id}_\star : \star \rightarrow \star$ .
An identity 2-cell $\mathsf{id}_{\mathsf{Id}_\star} : \mathsf{Id}_\star \rightarrow \mathsf{Id}_\star$ .

With these definitions in place, we can consider the (strict) points of a 2-category $\mathbf{C}$ . These are 2-functors:

$\mathbf{P} : 1 \rightarrow \mathbf{C}$

Such a functor can map $\star$ to any 0-cell it chooses. As both the identity cells must be preserved, this is the only freedom in choosing a particular $\mathbf{P}$ . Therefore we can identity strict points of a 2-category with its 0-cells. So far, so boring.

As we learned last time, it is mathematically natural to relax the strict setting to one where structure is only preserved up to isomorphism. To do so, we consider strong 2-functors (often called pseudofunctors or simply 2-functors). These have the same mappings as before, but now we have isomorphism 2-cells:

$\mathsf{Id} \overset{\cong}{\Rightarrow} \mathbf{F}(\mathsf{Id})$ .
$\mathbf{F}(G) \circ \mathbf{F}(F) \overset{\cong}{\Rightarrow} \mathbf{F}(G \circ F)$ .

As usual, these isomorphisms must satisfy some coherence equations, ensuring they are suitably compatible with each other. We will skip spelling these out explicitly.

Now consider strong 2-functors $\mathbf{P} : 1 \rightarrow \mathbf{C}$ . As the identity 2-cell must still be preserved, these consist of:

A 0-cell $\mathbf{P}(\star)$ .
A 1-cell $\mathbf{P}(\mathsf{Id})$ .
An isomorphism 2-cell $\mathsf{Id} \overset{\cong}{\Rightarrow} \mathbf{P}(\mathsf{Id})$ .
An isomorphism 2-cell $\mathbf{P}(\mathsf{Id}) \circ \mathbf{P}(\mathsf{Id}) \overset{\cong}{\Rightarrow} \mathbf{P}(\mathsf{Id})$ .

Possibly this is starting to look slightly familiar. A good choice of notation will hopefully clarify things further. Lets write

$\mathcal{C} = \mathbf{P}(\star) \qquad \mathbb{T} = \mathbf{P}(\mathsf{id})$

and name the two invertible 2-cells $\eta : \mathsf{Id} \overset{\cong}{\Rightarrow} \mathbb{T}$ and $\mu : \mathbb{T} \circ \mathbb{T} \overset{\cong}{\Rightarrow} \mathbb{T}$ . With this terminology, specifying a strong 2-functor $1 \rightarrow \mathbf{C}$ consists of:

A 0-cell $\mathcal{C}$ .
A 1-cell $\mathbb{T}$ .
An isomorphism 2-cell $\eta : \mathsf{Id} \overset{\cong}{\Rightarrow} \mathbb{T}$ .
An isomorphism 2-cell $\mu : \mathbb{T} \circ \mathbb{T} \overset{\cong}{\Rightarrow} \mathbb{T}$ .

This looks suspiciously like the definition of a monad on the 0-cell $\mathcal{C}$ in the 2-category $\mathbf{C}$ . In fact, the coherence conditions for this strong 2-functor exactly require that $\eta$ and $\mu$ satisfy the unit and multiplication axioms of a monad.

There is one remaining oddity to address, that $\eta$ and $\mu$ are isomorphisms, which is too strong to capture most monads. We need to weaken the conditions on our 2-functors still further. Fortunately, another standard categorical notion fits the bill. A lax 2-functor has the same data as a strong 2-functor, but we drop the isomorphism requirement for the 2-cells:

$\mathsf{Id} \Rightarrow \mathbf{F}(\mathsf{Id})$ .
$\mathbf{F}(G) \circ \mathbf{F}(F) \Rightarrow \mathbf{F}(G \circ F)$ .

Notice that now these 2-cells are not required to be invertible, their direction matters. We could equally consider oplax 2-functors, in which these 2-cells go in the other direction. The lax setting is the right one for our needs. We can make the standard observation:

A monad is the same thing as a lax 2-functor from the terminal category.

We have concentrated on strict 2-categories to avoid bookkeeping yet more isomorphisms, but this observation remains true if we move to the bicategorical setting.

Time to Generalise

The point of moving to a functorial perspective is that we have a natural launching point for generalisation. We identified monads in the 2-category $\mathbf{C}$ with lax 2-functors $1 \rightarrow \mathbf{C}$ . The obvious next step is to consider domains other than the terminal 2-category.

As a first step, we adjust our perspective on the terminal category slightly. Any monoid can be seen as a 1-object category, with morphisms corresponding to elements of the monoid, and composition and identities given by the monoid multiplication and unit respectively. Given any category $\mathcal{C}$ , we can view it as a 2-category, with the 0 and 1 cells given by the objects and morphisms of $\mathcal{C}$ , and the only 2-cells being the necessary identities. We can then build the terminal category as follows:

Consider the terminal monoid. This is the monoid with just a unit element.
View this as an ordinary category.
View the resulting category as a 2-category.

Obviously, we could perform these simple changes of perspective with any monoid $(M, \times, 1)$ . This yields the notion of graded monad. A graded monad on a 0-cell $\mathcal{C}$ , graded by $M$ consists of:

A family of 1-cells $\mathbb{T}_m : \mathcal{C} \rightarrow \mathcal{C}$ , indexed by the elements of $M$ .
A unit 2-cell $\eta : \mathsf{Id} \Rightarrow \mathbb{T}_1$ .
Multiplication 2-cells $\mu_{m,n} : \mathbb{T}_m \circ \mathbb{T}_n \Rightarrow \mathbb{T}_{m \times n}$ .

These satisfy some generalisations of the unit and multiplication axioms, compatible with the monoid indexing.

Example: We can consider functors $\mathbb{L}_n$ sending a set $X$ to the set of lists of elements of $X$ of exactly length $n$ . There is an obvious mapping:

$\eta_X : X \rightarrow \mathbb{L}_1(X)$

sending each element of $x$ to the singleton list $[x]$ . There are also multiplication morphisms:

$\mu_{m,n,X} : \mathbb{L}_m(\mathbb{L}_n(X)) \rightarrow \mathbb{L}_{m \times n}$

given by concatenation. For example:

$[[1,2],[3,4],[5,6]] \mapsto [1,2,3,4,5,6]$

Together, this data constitutes a graded monad, graded by the natural numbers under multiplication $(\mathbb{N}, \times,1)$ . We shall refer to this as the exact list graded monad.

This example gives a general sense of the nature of graded monads, particularly in computer science. The grading allows us to track some quantitative data, allowing to model resources appropriate to the effects in our application. We mention another perhaps slightly surprising degenerate example:

Example: Every 1-cell $F : \mathcal{C} \rightarrow \mathcal{C}$ induces a $(\mathbb{N},+,0)$ graded monad $\mathbb{F}$ on $\mathcal{C}$ , with

$\mathbb{F}_n = \overbrace{F \circ \ldots \circ F}^{n \text{ times}}$

So in particular, $\mathbb{F}_0 = \mathsf{Id}$ . The unit and multiplications are identity 2-cells.

The exact list example is a bit inflexible, as list lengths are fixed completely. To loosen this up, we introduce a new mathematical object. A preordered monoid is a monoid $(M,\times,1)$ with a preorder on $M$ such that the monoid multiplication is monotone.

Example: The natural numbers under multiplication form a partially ordered monoid under the usual ordering on natural numbers, as:

$m_1 \leq m_2 \;\wedge\; n_1 \leq n_2 \;\Rightarrow\; m_1 \times n_1 \leq m_2 \times n_2$

Similarly to ordinary monoids, preordered monoid can be viewed as (thin) 2-categories, with 2-cells between 1-cells $m,n$ whenever $m \leq n$ . We can then generalize further, to monads graded by a preordered monoid. These are the same as monoid graded monads, with the addition that if $m \leq n$ there is a 2-cell $\mathbb{T}_m \Rightarrow \mathbb{T}_n$ . As usual, these 2-cells must satisfying some compatibility equations, which we will skip over.

Example: There is a second family of list functors $\mathbb{L}^{\leq}_n$ , with the elements of $\mathbb{L}^{\leq}_n(X)$ consisting of lists of elements of $X$ of length at most $n$ . The unit and multiplication maps are given by singletons and concatenation, as in the previous example. If $m \leq n$ , there is a natural transformation:

$\mathbb{L}^{\leq}_m \Rightarrow \mathbb{L}^{\leq}_n$

promoting lists of shorter length to the longer context. These constitute a $\mathbb{N}, \times, 1, \leq)$ -graded monad, the bounded list graded monad.

We can go further, and in the extreme consider monads graded by any 2-category we like.

Conclusion

Graded monads can be seen as a resource aware generalisation of monads, with natural applications in areas such as computer science. For example, there are non-trivial graded state, writer and maybe monads. There is a lot more to explore here, for example:

Developing the mathematics further, for example suitable Kleisli and Eilenberg-Moore constructions.
Discussing applications of graded monads.

As ordinary monads are already a rich topic, unsurprisingly this is more than we can hope to cover properly in a single post. We may return to this subject again later.

This post owes a great deal to exposition in papers and talk slides by Tarmo Uustalu. I would recommended the slides from “Grading monads, comonads, distributive laws” as a good starting point for further reading.

Acknowledgements: Thanks to Ralph Sarkis for picking up a confusing typo in one of the examples.

Graded Monads

A 2-Functorial Perspective

Time to Generalise

Conclusion

Leave a Reply Cancel reply

A 2-Functorial Perspective

Time to Generalise

Conclusion

Share this:

Like this:

Related

Leave a Reply Cancel reply