Distributive law between monads
In category theory, an abstract branch of mathematics, distributive laws between monads are a way to express abstractly that two algebraic structures distribute one over the other.
Suppose that and are two monads on a category C. In general, there is no natural monad structure on the composite functor ST. However, there is a natural monad structure on the functor ST if there is a distributive law of the monad S over the monad T.
Formally, a distributive law of the monad S over the monad T is a natural transformation
such that the diagrams
commute.
This law induces a composite monad ST with
- as multiplication:,
- as unit:.
Examples
Monoids
Informally, one might say that the free monoid on a set is given by "the free semigroup, plus an identity element". We can formalise this intuition, using the fact that both the free semigroup and the "free element" functors are monads. Explicitly, consider the monads, with unit maps given by:
The multiplication map sends both elements of 2 to that of 1, but the multiplication on is a bit more tricky to describe. First, note that an arbitrary element of is just a finite string of elements of. The multiplication map should therefore take a string of words on to one word. We choose to be the concatenation of all words in.
What does a distributive law mean here? It takes a word on the set to either a word on, or the disjoint point in. We choose the map that interprets the unit element as the empty word; explicitly:
where is the word derived from by removing all instances of, unless is all 's, in which case it's defined to be. The idea, in short, is this: if we view words on as formal products of elements, then encodes that the freely added element can be incorporated into the semigroup as a unit element. Let us check that all the diagrams in the definition commute.
being the elements of each copy of in, and where denotes the word with every instance of replaced by.
and note that for we have, as required.
where: is the concatenation of all words in, i.e. the multiplication on ; and is the result of replacing every word in with.
In summary, the four commutation requirements encode the following ideas:
- "Deleting" elements behaves like replacing them with the identity,.
- Any word on doesn't contain the element, so. In other words, truly is a disjoint union.
- In a list of words, removing any instance of in, removing any remaining "empty word", and concatenating the resulting list, yields the same result as first concatenating then removing all instances of.
- , as already covered in 2; and, meaning we should interpret as the empty word.
Rings
This is the original example given by Beck, and is the motivation for the term "distributive law". Consider the two monads which send a set to the free commutative group and the free monoid on it, respectively. We shall regard the formal group operation as addition, and that of the monoid as multiplication. In this case, both composites and give the free ring functor. We can now use the fact that the free ring admits a distributive law to show that it's also a monad.The distributive law of G over M means exactly that a product of sums can be identified with a sum of products. Note that we say, the additive group, distributes over, the multiplicative monoid - contrary to the usual convention; see the next section.
Terminology
The original description by Beck calls a distributive law of S over T. However, some authors prefer the reverse terminology, where is instead said to be a distributive law of T over S; this is because, arguably, the latter convention corresponds more closely to the usual distributive law between multiplication and addition - multiplication is typically said to distribute over addition, by which one means that a product of sums can be rewritten as a sum of products . Nevertheless, both terminologies are in use in different sources, and the original is what this article uses.Related notions
BD-law
In the case where, the distributive law map reduces to, and one may impose some additional conditions. is called a BD-law on if:A BD-law is a BCD-law if the multiplication on is "-commutative", meaning that
Condition is called a Yang-Baxter equation because it literally is the Yang-Baxter equation defined on monoid objects, when is viewed as a monoid in the category of endofunctors on.