nLab
graded monad

Contents

Contents

Idea

By analogy with graded algebra, a \mathcal{M}-graded monad in a category 𝒞\mathcal{C} for a monoidal category, (,,I)(\mathcal{M}, \otimes, I), is a lax monoidal functor, (,,I)([𝒞,𝒞],,id 𝒞)(\mathcal{M}, \otimes, I) \to ([\mathcal{C}, \mathcal{C}], \circ, id_{\mathcal{C}}). This generalizes the concept of monad which may be consider as graded by 1\mathbf{1}, the terminal category. This definition may be rephrased in terms of a lax action of \mathcal{M} on 𝒞\mathcal{C}.

Equivalently, a \mathcal{M}-graded monad is a lax 2-functor from the delooping (or “suspension”) of \mathcal{M}, BCat\mathbf{B} \mathcal{M} \to Cat. Just as monads may be defined in any 2-category, KK, this suggests that we may generalize graded monads to lax 2-functors BK\mathbf{B} \mathcal{M} \to K.

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,,e)(M, \otimes, e). Then for some given category, CC, we have a family of endofunctors, T mT_m, indexed by elements of MM, with maps μ m,n,X:T m(T nX)T mnX\mu_{m, n, X}: T_m(T_n X) \to T_{m \otimes n} X and η X:XT eX\eta_{X}: X \to T_{e} X, for m,nm, n in MM and XX in CC. For instance, there is a (,×,1)(\mathbb{N}, \times, 1)-graded monad on sets where T nT_n returns lists of length nn 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 1\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 B[Set,Set]\mathbf{B} \mathbb{N} \to [Set,Set] described above results in the usual list monad on SetSet, given by a lax monoidal functor 1[Set,Set]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 mnm n can be decomposed uniquely into a list of length mm of lists of length nn, so that the multiplication T mT nXT mnXT_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).

References

  • 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 and Paolo Perrone, A Criterion for Kan Extensions of Lax Monoidal Functors, (arXiv:1809.10481).

  • Tobias Fritz and 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)

Last revised on August 8, 2019 at 12:01:30. See the history of this page for a list of all contributions to it.