Monads and comonads are important constructions from category theory which find widespread application in computer science and other related disciplines. Distributive laws allow these constructions to interact compositionally. Such laws are not guaranteed to exist, and even when they do, finding them can be a difficult task. Inspired by recent results which establish conditions under which no distributive laws can exist between pairs of monads, we present a family of no-go theorems for the existence of distributive laws of a comonad over a monad. We begin by showing that in the category of sets every container has a unique Kleisli law over the non-empty powerset monad. We then show that this Kleisli law only extends to a comonad-monad distributive law if the comonad is a coreader comonad. Consequently, every other directed container does not distribute over the powerset monad. Next, we generalise our results to a large class of monads, which we call uniform choice monads. Examples of monads in this class include any multiset or distribution monad parameterised by a suitable semiring. Finally, we extend our results to the category of relational structures where we show that several game comonads, recently introduced in the context of finite model theory, fail to distribute over variants of the powerset and distribution monads, which are used to capture relaxations of the constraint satisfaction problem. Overall, our no-go results cover a diverse range of (co)monads that are of interest in many areas of mathematics and computer science, such as probability theory, programming languages, and finite model theory.

@inproceedings{KaramlouS24,
  title = {No Go Theorems: Directed Containers That Do Not Distribute Over Distribution Monads},
  author = {Amin Karamlou and Nihil Shah},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662137}
}