nLab graded monad

Idea

By analogy with graded algebra, an $\mathcal{M}$-graded monad in a category $\mathcal{C}$ for a monoidal category, $(\mathcal{M}, \otimes, I)$, is a lax monoidal functor from $\mathcal{M}$ to the endo-functor category of $\mathcal{C}$ (that whose monoid objects are monads on $\mathcal{C}$):

$$(\mathcal{M}, \otimes, I) \longrightarrow ([\mathcal{C}, \mathcal{C}], \circ, id_{\mathcal{C}}) \,.$$

This generalizes the concept of a plain monad on $\mathcal{C}$, which is recovered as the special case of grading by the terminal monoidal category $1$.

Equivalently, an $\mathcal{M}$-grading is a lax action of $\mathcal{M}$ on $\mathcal{C}$, which in turn is equivalently a lax 2-functor to Cat from the delooping of $\mathcal{M}$, i.e.: $\mathbf{B} \mathcal{M} \to Cat$.

Just as monads may be defined in any 2-category $K$ (besides the case $K =$Cat), this suggests that we may generalize graded monads to lax 2-functors $\mathbf{B} \mathcal{M} \to K$.

A further generalization is to category-valued monads, lax functors from any category to $Cat$ (OrchWadEad), and then to 2-category-valued monads from any 2-category.

Graded monads are also known as parametric monads. The grading idea may also be applied to comonads.

Examples

1. The grading may arise from a monoid $(M, \otimes, e)$. Then for some given category, $C$, we have a family of endofunctors, $T_m$, indexed by elements of $M$, with maps $\mu_{m, n, X}: T_m(T_n X) \to T_{m \otimes n} X$ and $\eta_{X}: X \to T_{e} X$, for $m, n$ in $M$ and $X$ in $C$. For instance, there is a $(\mathbb{N}, \times, 1)$-graded monad on sets where $T_n$ returns lists of length $n$ of elements of a set.

2. In computer science, monads model effects and comonads coeffects. Grading can therefore allow further annotation of these. For instance, there are graded versions of the reader monad, state monad and writer comonad (OrchPet).

3. Any graded modality, such as found in bounded linear logic.

4. For graded monads relevant for probability theory see (Perrone).

5. Given the strict action of a monoidal category, $\mathcal{M}$ on a category $\mathcal{B}$, and an adjunction

then $\mathcal{A}$ inherits a lax action of $\mathcal{M}$ and is hence a graded monad. Every lax action can be generated from a strict action in this way. Initial and terminal such resolutions of a lax action then generalize the $\mathcal{M} \cong 1$ situation in which is a monad is resolved into adjunctions with the Kleisli and Eilenberg-Moore categories (FKM 16).

Uses

Graded monads can be used to construct ordinary monads by left Kan extension in the 2-category of monoidal categories, lax monoidal functors, and monoidal transformations. There are known criteria for when this Kan extension exists; see (Fritz & Perrone 18, Theorem 2.1), as well as the references in there on algebraic Kan extensions.

For example, taking the left Kan extension of the graded list monad $\mathbf{B} \mathbb{N} \to [Set,Set]$ described above results in the usual list monad on $Set$, given by a lax monoidal functor $1 \to [Set,Set]$. Based on a similar construction on the category of complete metric spaces, (Fritz & Perrone 17) have contructed a monad of Radon probability measures without any appeal to measure theory; the intuitive idea being that a probability measure can be thought of as an idealized version of a finite sample, and spaces of finite samples make up a graded monad. Forgetting the grading by taking the above Kan extension then produces the Kantorovich monad, containing all Radon probability measures of finite first moment. This construction reduces certain problems in measure-theoretic probability to purely combinatorial problems.

A useful feature of such constructions is that the multiplication of the graded monad is often a strong monoidal functor in practice. For the graded list monad, this is because a list of length $m n$ can be decomposed uniquely into a list of length $m$ of lists of length $n$, so that the multiplication $T_m T_n X \longrightarrow T_{m n} X$ is an isomorphism. For the probability monad mentioned in the previous paragraph, the analogous phenomenon occurs as well, and this can be exploited e.g. in order to prove a disintegration theorem for finite first moment Radon probability measures on complete metric spaces (Perrone, Theorem 2.6.9).

Related concepts

• graded modality
• monad
• actegory

References

• A. L. Smirnov, Graded monads and rings of polynomials, Journal of Mathematical Sciences 151.3 (2008): 3032-3051.

• Soichiro Fujii, Shin-ya Katsumata, and Paul-André Melliès, Towards a Formal Theory of Graded Monads, (pdf)

• Soichiro Fujii, A 2-Categorical Study of Graded and Indexed Monads, (arXiv:1904.08083)

• Ulrich Dorsch, Stefan Milius and Lutz Schröder, Graded Monads and Graded Logics for the Linear Time – Branching Time Spectrum, (arXiv:1812.01317)

• Paolo Perrone, Categorical Probability and Stochastic Dominance in Metric Spaces, (thesis)

• Tobias Fritz, Paolo Perrone, A Criterion for Kan Extensions of Lax Monoidal Functors, (arXiv:1809.10481).

• Tobias Fritz, Paolo Perrone, A Probability Monad as the Colimit of Spaces of Finite Samples, (arXiv:1712.05363).

• Dominic Orchard, Tomas Petricek, Embedding effect systems in Haskell, (pdf)

• Dominic Orchard, Philip Wadler, Harley Eades, Unifying graded and parameterised monads, (arXiv:2001.10274)

Graded monads are shown to be examples of enriched relative monads in:

• Dylan McDermott, Tarmo Uustalu. Flexibly graded monads and graded algebras, in: Mathematics of Program Construction MPC 2022, Lecture Notes in Computer Science 13544, Springer (2022) [doi:10.1007/978-3-031-16912-0_4]