Distributive Laws of Monadic Containers
Chris Purdy, Stefania Damato · 2025
Read Distributive Laws of Monadic Containers by Chris Purdy, Stefania Damato (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-17191.txt.
Introduction
Chris Purdy and Stefania Damato settle in 2025 when two composable data types can be combined into one. In their setting, a container describes a data type by its shapes and positions. Some containers carry a monad structure, a standard pattern for sequencing computations, but two such containers usually refuse to compose.
A distributive law is the extra rule that lets two monads merge. The authors characterize exactly which laws exist between monadic containers. They also handle the mixed cases with the dual, comonad side, completing a small zoo of characterizations. Most of the theory was proven inside the Cubical Agda proof assistant, so the results are machine-checked.
Catalog record
| CREATOR | Chris Purdy, Stefania Damato |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 84 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-17191
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributive Laws of Monadic Containers Chris Purdy, Stefania Damato Abstract Containers are used to carve out a class of strictly positive data types in terms of shapes and positions. They can be interpreted via a fully-faithful functor into endofunctors on \ul Set \ul{\textbf{\text{Set}}} . Monadic containers are those containers whose interpretation as a \ul Set \ul{\textbf{\text{Set}}} functor carries a monad structure. The category of containers is closed under container composition and is a monoidal category, whereas monadic containers do not in general compose. In this paper, we develop a characterisation of distributive laws of monadic containers. Distributive laws were introduced as a sufficient condition for the composition of the underlying functors of two monads to also carry a monad structure. Our development parallels Ahman and Uustalu’s characterisation of distributive laws of directed containers, i.e. containers whose \ul Set \ul{\textbf{\text{Set}}} functor interpretation carries a comonad structure. Furthermore, by combining our work with theirs, we construct characterisations of mixed distributive laws (i.e. of directed containers over monadic containers and vice versa), thereby completing the ‘zoo’ of container characterisations of (co)monads and their distributive laws. We have found these characterisations amenable to development of existence and uniqueness proofs of distributive laws, particularly in the mechanised setting of Cubical Agda, in which most of the theory of this paper has been formalised. Royal Holloway University of London, [email protected] of Nottingham, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10010124.10010131.10010137¡/concept_id¿ ¡concept_desc¿Theory of computation Categorical semantics¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10010124.10010125.10010130¡/concept_id¿ ¡concept_desc¿Theory of computation Type structures¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ The authors would like to thank Thorsten Altenkirch, Dan Marsden, Stiéphen Pradal, and Reuben Rowe for helpful discussions on this work, and Tom de Jong for his guidance and for inspiring our use of the \formalised symbol for formalised statements. ccs Theory of computation Categorical semantics ccs Theory of computation Type structures keywords distributive laws, monadic containers, monads, dependent types, cubical agda † † runningauthor: C. Purdy and S. Damato † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom 1 Introduction Containers, introduced by Abbott et al. [ 3 ] , give an algebraic presentation of a wide class of strictly positive data types. Often, reasoning about strictly positive data types in terms of their container representation is simpler than their functorial representation – for example, transformations between container functors constructed from container morphisms are automatically natural. Monads have received a lot of attention in functional programming [ 18 ] and denotational semantics for their ability to model a wide range of programmatic side-effects [ 25 ] . In practice, it is rare for side-effects to appear individually – developing a way of composing monads is useful for situations where multiple effects are interleaved. In general, however, the composition of two monads need not result in another monad. Distributive laws [ 11 ] were developed as a sufficient condition for such a composition to form a monad, thereby ensuring that the corresponding side-effects are interleaved in a coherent way. Constructing distributive laws is known to be quite difficult due to the complexities involved in checking their axioms, besides the fact that some monads, even if they are composable, do not admit a distributive law in the first place [ 30 , Remark 4.19] . As a result, various work has been done on different approaches for constructing distributive laws [ 23 , 24 ] , and for identifying cases where there are none [ 30 , 20 ] . In this paper, we develop a characterisation of distributive laws of monadic containers [ 27 ] , i.e. containers whose interpretation carries a monad structure, with the goal of providing an algebraic way of reasoning about distributive laws between strictly positive data types. We build on similar characterisations in the literature; Ahman, Chapman, and Uustalu develop directed containers [ 5 ] , i.e. containers whose interpretation carries a comonad structure, and the first and last authors provide a characterisation of their distributive laws [ 6 ] . Uustalu also develops monadic containers [ 27 ] , but to our knowledge, no work has been done on characterising their distributive laws. Our work parallels the development in [ 6 ] for monadic containers and therefore closes this gap. Furthermore, by combining our work with [ 6 ] , we construct characterisations of mixed distributive laws (i.e. of directed containers over monadic containers and vice versa), thereby completing the ‘zoo’ of container characterisations of (co)monads and their distributive laws. Formalisation We have formalised our characterisations and those in [ 5 , 6 ] using Cubical Agda [ 28 ] . The statements in this paper that we have formalised are annotated by a \formalised symbol, which is a clickable link to the corresponding formalised statement. The code can be found at https://github.com/chrisjpurdy/distr-laws-of-monadic-containers and an HTML rendered version can be found at https://stefaniatadama.com/distr-law-mnd-cont-html/ . Since our representation of distributive laws involves a list of highly dependent equalities, it lends itself well to formalisation in a proof assistant such as Cubical Agda. The formalisation includes monadic and directed container examples, distributive law examples, and proofs of uniqueness of certain concrete distributive laws. Setting of our work & Notation We work in cubical type theory [ 14 , 28 ] but our work holds in any intensional Martin-Löf type theory by assuming extensionality principles that are provable in cubical type theory, namely function extensionality (in particular, we do not use univalence). Throughout the paper, we use several type-theoretic notations made explicit below. • We use \sum_{a:A}B\,a for dependent sums and \prod_{a:A}B\,a for dependent products, their non-dependent counterparts represented as A\times B and A\to B respectively. A+B denotes the sum type of A and B . The notation (a,b) refers to an element of a product type, \lambda x.f\,x an element of a function type, and \mathsf{inl}\,a and \mathsf{inr}\,b elements of a sum. \pi_{1} and \pi_{2} are the first and second projections out of a product type. • The symbol \coloneqq refers to definitional equality, specifically used when first defining something, = refers to propositional equality, and \cong refers to isomorphism of types. • The empty type is denoted by \bot and the unit type by \top with element \star . \mathsf{Fin}\;n is the type of finite sets of size n . • The category whose objects are (small) sets and whose morphisms are functions is denoted by \ul Set , while \mathsf{Set} denotes the universe of homotopy-sets (h-sets), or 0-types. • The category of endofunctors on \ul Set is denoted by [\ul{\textbf{Set}},\ul{\textbf{Set}}] . • A few times we mention that an equality ‘holds up to’ another equality, by which we mean that we have a heterogenous equality, or a path ‘lying over’ another path. For more details on this, see [ 26 , Section 2.3] . Organisation of the paper The paper is organised as follows. After mentioning some related work in section 2 , we briefly review containers and monadic containers in section 3 . In section 4 , we characterise