On the Non−Compositionality of Monads via Distributive Laws

Abstract

Monads are a useful tool in both computer science and mathematics: they model computational behaviour, describe data structures, and give access to Kleisli and Eilenberg-Moore categories. To utilise multiple monads simultaneously, monads can sometimes be composed to form composite monads. Distributive laws ensure that such composite monads capture the full behaviour of both their components, creating a lifting of the component monads to the appropriate Kleisli or Eilenberg-Moore categories. However, for a given pair of monads there does not necessarily exist adistributive law to compose them.

This thesis presents a new method to prove so called no-go theorems: theorems that identify cases in which a distributive law cannot exist. The method, which uses an algebraic perspective on monads, has unique advantages over the more usual categorical approaches. The most important advantage is that it produces no-go theorems that identify large classes of monads that do not compose via distributive laws, where previously only a few specific counterexamples were known.

Among the many examples in this thesis, there are several that answer open questions from the literature, and some that identify previously unnoticed mistakes in the literature. Our no-go theorems will hopefully prevent these type of mistakes from happening in future.