Monads and Distributive Laws in Substructural Contexts (Extended Version)

Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, Ichiro Hasuo · 2026

Read Monads and Distributive Laws in Substructural Contexts (Extended Version) by Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, Ichiro Hasuo (2026) 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-2605-13533.txt.

Introduction

Soichiro Fujii and three colleagues present a categorical account of monads and distributive laws in substructural contexts. They model substructural varying contexts with Tronin's verbal categories W, in a uniform way. They define W-operadic monads, set via the rules in W, and W-commutative monads, invariant under those rules. They give a standard way to build a distributive law ST to TS on Set, valid when S is W-operadic and T is W-commutative. That covers many known and new laws.

Catalog record

CREATORSoichiro Fujii, Yun Chen Tsai, Yoàv Montacute, Ichiro Hasuo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE163820
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13533

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Monads and Distributive Laws in Substructural Contexts (Extended Version) Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, Ichiro Hasuo Abstract We present a categorical theory of monads and distributive laws in substructural contexts . In the study of distributive laws, the roles of (the absence of) structural rules for variable contexts have been recognized; our theory formalizes these substructural situations using Tronin’s verbal categories 𝐖 \mathbf{W} , in a uniform and presentation-independent manner. We introduce the classes of 𝐖 \mathbf{W} -operadic monads (those defined via the structural rules in 𝐖 \mathbf{W} ) and of 𝐖 \mathbf{W} -commutative monads (those invariant under the structural rules in 𝐖 \mathbf{W} ). We give a canonical construction of a distributive law S ​ T → T ​ S ST\to TS of monads on 𝐒𝐞𝐭 \mathbf{Set} ; it is applicable when S S is 𝐖 \mathbf{W} -operadic and T T is 𝐖 \mathbf{W} -commutative (under mild conditions). This accounts for many known and new distributive laws. Even when S S fails to be 𝐖 \mathbf{W} -operadic, we can refine S S and force 𝐖 \mathbf{W} -operadicity; this captures Varacca and Winskel’s construction of indexed valuations. National Institute of Informatics, Tokyo, [email protected]://orcid.org/0000-0002-4109-3472 National Institute of Informatics, Tokyo, Japan and SOKENDAI (The Graduate University for Advanced Studies), Kanagawa, [email protected]://orcid.org/0009-0003-7705-9609 National Institute of Informatics, Tokyo, [email protected]://orcid.org/0000-0001-9814-7323Supported by ACT-X, Grant No. JPMJAX24CR, JST, Japan. National Institute of Informatics, Tokyo, Japan and SOKENDAI (The Graduate University for Advanced Studies), Kanagawa, Japan and Imiron Co., Ltd., Tokyo, [email protected]://orcid.org/0000-0002-8300-4650 We thank the anonymous referees of [ 14 ] for their helpful comments. \crefname theoremThm.Thms \crefname section§§§ \crefname definitionDef.Defs \crefname notationNotationNotations \crefname exampleEx.Exs \crefname remarkRem.Rems \crefname problemProblemProblems \crefname equation \crefname constructionConstructionConstructions \crefname corollaryCor.Cors \crefname propositionProp.Props \crefname lemmaLem.Lems \crefname appendixAppendixAppendices \crefname claimClaimClaims \crefname figureFig.Figs ccs Theory of computation Categorical semantics ccs Theory of computation Probabilistic computation ccs Theory of computation Program semantics keywords Monad, distributive law, operad, category theory, effect † † runningauthor: S. Fujii, Y. C. Tsai, Y. Montacute, and I. Hasuo † † copyright: Soichiro Fujii, Yun Chen Tsai, Yoàv Montacute, and Ichiro Hasuo † † relatedversion: This paper is the extended version of [ 14 ] . † † funding: All authors are supported by ASPIRE Grant No. JPMJAP2301, JST, Japan. † † editors: Claudia Faggian and Joost-Pieter Katoen † † event-title: 41st Annual Symposium on Logic in Computer Science (LICS 2026) † † event-shorttitle: LICS 2026 † † event-acronym: LICS † † year: 2026 † † event-date: July 20–23, 2026 † † event-location: Lisbon, Portugal † † series-volume: 380 † † articleno: 76 1 Introduction Monads In program semantics and, more generally, in system behavior modeling, the categorical notion of monad has been successfully used as a uniform interface to various computational effects . Examples of effects include non-functional side effects in functional programming [ 49 ] , additional behavioral layers for reactive systems such as (possibilistic or probabilistic) nondeterminism [ 2 , 21 ] , and so on. The mathematical theory of monads—together with a closely related theory of universal algebra —not only offers unified foundations for effects, but also enables novel programming principles such as effect handlers [ 54 ] . Distributive laws In this context, distributive laws between monads have attracted attention. Originally a mathematical construct [ 3 ] , distributive laws enable us to combine effects . Specifically, given monads S and T on the category \mathbf{Set} of sets (in this paper, we focus on monads on \mathbf{Set} ), a distributive law \delta\colon ST\to TS of S over T equips the composite TS with a monad structure, with the consequence that unified monadic frameworks for programming, static analysis, verification, etc. accommodate the coexistence of two different layers of effects modeled by S and T . The question of obtaining a distributive law has intrigued many theoreticians, too. This was initiated by Plotkin’s observation that there is no distributive law DP\to PD of the (finitely supported) probability distribution monad D over the powerset monad P (see [ 68 ] ). This observation sparked much work: both on the positive side (obtaining distributive laws [ 11 , 52 , 17 ] ) and the negative side (proving “no-go” theorems [ 29 , 71 ] ). Two approaches: weak distributive laws and refinement On the positive side, towards obtaining a distributive law, there have mainly been two technical approaches. The first “weak distributive law” approach, when a distributive law ST\to TS does not exist, finds it sufficient to have a weak distributive law \delta\colon ST\to TS . Here “weak” means \delta ’s compatibility with the unit \eta^{S} of S is dropped. A weak distributive law \delta induces a combination of S and T , but this time it is not given simply by the composite TS . Roughly speaking, this approach modifies T : concretely, for S=D and T=P , the combination essentially replaces T=P with the convex powerset monad over the Eilenberg–Moore category \mathbf{Set}^{D} [ 15 , 17 , 4 , 1 , 62 ] . The second “refinement” approach modifies S instead. It finds a reason for the failure of a distributive law \delta\colon ST\to TS in equations in (an equational presentation of) S , and thus proposes to use a refinement \widehat{S} of S —obtained by dropping the problematic equations—in place of S . This approach is initiated in [ 68 ] for specific monads (variations of D and P —see \cref subsec:IV-revisited). Generalization of this approach is sought in [ 11 , 52 ] . We follow this line of work. Categorical theory of substructural contexts for monads and distributive laws In this paper, we introduce a general framework for the aforementioned “refinement” approach to distributive laws, centered around the idea of substructural contexts . Our categorical framework uses verbal categories [ 64 ] for modeling substructural contexts. The relevance of structural rules (exchange, weakening, and contraction) to algebraic theories (and thus monads) is widely acknowledged, explicitly or implicitly [ 10 , 20 , 37 ] . In particular, [ 11 , 52 , 44 ] study the roles of structural rules in distributive laws. Our framework here offers a unifying categorical picture parametrized by a verbal category \mathbf{W} . We sketch our theory in the coming paragraphs. Substructural contexts and verbal categories ( \cref sec:notions-of-operad) Restricting structural rules— exchange (E), weakening (W), and contraction (C)—in variable contexts is a common tool in logic. In the categorical study of algebraic theories, operads, and binding syntax, it is common to model the application of structural rules with 1) morphisms of \mathbf{F} , the category of finite ordinals and functions between them [ 13 ] , and 2) their string diagram presentation [ 10 , 37 ] . For example, the context transformation from x_{0},x_{1},x_{2}\vdash p(x_{0},x_{1},x_{2}) to x_{0},x_{1},x_{2},x_{3}\vdash p(x_{1},x_{3},x_{1}) —obtained with E, W, and C for a term p —is represented by the function \alpha\colon 3\to 4 with \alpha(0)=\alpha(2)=1 and \alpha(1)=3 ; the corresponding string diagram (in which we have \alpha(i)=j iff i on the right is connected to j on the left) is depicted on the left of ( 1 ) below. 0 1 2 3 0 1 2 (1) The structural rules E, W, and C correspond to the three “parts” of the string diagram as

Read the complete text