Exploring the boundaries of monad tensorability on Set

DOI10.2168/LMCS-9(3:22)2013MaRDI QIDQ2848367zbMATH OpenFDO

Authors Nathan Bowler, Paul Blain Levy, Lutz Schröder, S. S. Goncharov

Publication date 26 September 2013

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.2128

zbMATH Keywords

tensor productsmonadsnondeterminismside effects

Mathematics Subject Classification ID

Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads (18C15) Semantics in the theory of computing (68Q55)

Abstract: We study a composition operation on monads, equivalently presented as large equational theories. Specifically, we discuss the existence of tensors, which are combinations of theories that impose mutual commutation of the operations from the component theories. As such, they extend the sum of two theories, which is just their unrestrained combination. Tensors of theories arise in several contexts; in particular, in the semantics of programming languages, the monad transformer for global state is given by a tensor. We present two main results: we show that the tensor of two monads need not in general exist by presenting two counterexamples, one of them involving finite powerset (i.e. the theory of join semilattices); this solves a somewhat long-standing open problem, and contrasts with recent results that had ruled out previously expected counterexamples. On the other hand, we show that tensors with bounded powerset monads do exist from countable powerset upwards.

Recommendations

• A counterexample to tensorability of effects
• Monads and tensor products
• Tensors of comodels and models for operational semantics
• Tensors, monads and actions
• Combining effects: sum and tensor

Cited in

(7)

• On toposes, algebraic theories, semi-abelian categories and compact Hausdorff spaces
• Initial algebras and final coalgebras consisting of nondeterministic finite trace strategies
• Connected monads weakly preserve products
• Coproducts of monads on Set
• Sum and tensor of quantitative effects
• A counterexample to tensorability of effects
• Monads and tensor products

Describes a project that uses

Uses Software

• Haskell

This page was built for publication: Exploring the boundaries of monad tensorability on Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848367)