No-go theorems for distributive laws: directed containers vs. uniform sampling

Abstract: Monads model effectful computation, comonads model folding with a context. Given a comonad W and a monad M, when can two computations WA -> MB and WB -> MC be composed? Power and Watanabe demonstrate that the existence of a mixed distributive law WM -> MW gives a sufficient condition for obtaining a biKleisli category where such morphisms can be composed. In this talk, I will demonstrate that, for a wide class of (co)monads on the category of sets, such laws do not exist. I first show that, on the category of sets, there is no mixed distributive law of the non-empty list comonad over the powerset monad. We then generalise the comonad demonstrating that a directed container W has a distributive law over the powerset monad M if and only if W is a coreader comonad. Finally, we generalise this no-go theorem to all monads over the category of sets which have a meaningful notion of "uniform sampling". If I have time, I will also go over transfer theorems which enable lifting these no-go theorems over Set to related (co)monads on a different category.

This talk is derived from my previous joint work with Amin Karamlou appearing in LICS 2024 (https://doi.org/10.1145/3661814.3662137).

computer science theoryMathematics

Audience: researchers in the topic

University of Birmingham theoretical computer science seminar

Series comments: Meeting ID: 818 7333 5084 ~ Password: 217