Distributive law between monads

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 : T(X) := \sum_{n \ge 1} X^{n} : S(X) := X+1 , (here addition denotes disjoint union), with unit maps given by: : \eta^{T}_{X} : X \to T(X) : \eta^T_X(x) := x \in X^1 : \eta^S_X : X \to S(X) : \eta^S_X(x) := x \in X . The multiplication map \mu^S_X : X+2 \to X+1 sends both elements of 2 to that of 1, but the multiplication on T is a bit more tricky to describe. First, note that an arbitrary element of T(X) is just a finite (nonempty) string of elements of X. The multiplication map T^2(X) \to T(X) should therefore take a string of words on X to one word. We choose \mu^T_X(list) to be the concatenation of all (finitely many) words in list. What does a distributive law l : TS \to ST mean here? It takes a word on the set X+1 to either a word on X, or the disjoint point in 1. We choose the map that interprets the unit element e \in 1 as the empty word; explicitly: : l(w) = w-e, where w-e is the word derived from w by removing all instances of e, unless w is all e's, in which case it's defined to be e \in 1. The idea, in short, is this: if we view words on X as formal products of elements (i.e., the free semigroup operation), then l encodes that the freely added element e can be incorporated into the semigroup as a unit element (thereby making the structure into a monoid). Let us check that all the diagrams in the definition commute. • \mu^S_{T(X)} \circ S(l_X) \circ l_{S(X)} = l_X \circ T(\mu^S_X) :: LHS: w \mapsto (w-e') \mapsto (w-e'-e) \mapsto (w-e'-e) :: RHS: w \mapsto w[e/e'] \mapsto (w[e/e']-e) , e,e' being the elements of each copy of 1 in X+1+1, and where w[e/e'] denotes the word w with every instance of e' replaced by e. • l_X \circ T(\eta^S_X) = \eta^S_{T(X)} :: LHS: w \mapsto w \mapsto w-e :: RHS: w \mapsto w , and note that for w \in T(X) we have w-e = w, as required. • S(\mu^T_X) \circ l_{T(X)} \circ T(l_X) = l_X \circ \mu^T_{S(X)} :: LHS: w \mapsto w[(v-e)/v] \mapsto w[(v-e)/v]-e \mapsto concat(w[(v-e)/v]-e) :: RHS: w \mapsto concat(w) \mapsto concat(w)-e , where: concat(w) is the concatenation of all words in w, i.e. the multiplication on T; and w[(v-e)/v] is the result of replacing every word v in w with (v-e). • l_X \circ \eta^T_{S(X)} = S(\eta^T_X) :: LHS: (x \in X \ or \ e \in 1) \mapsto (x \ or \ e) \mapsto (x \ or \ e) - e :: RHS: (x \ or \ e) \mapsto (x \ or \ e) . In summary, the four commutation requirements encode the following ideas: • "Deleting" elements w-e' behaves like replacing them with the identity, w[e/e']. • Any word w on X doesn't contain the element e, so w-e = w. In other words, X+1 truly is a disjoint union. • In a list of words w = (v_1,...,v_n), removing any instance of e in v_i, removing any remaining "empty word" v_i = e, and concatenating the resulting list, yields the same result as first concatenating v_1v_2...v_n then removing all instances of e. • x-e = x, as already covered in 2; and e-e = e, meaning we should interpret e 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 G,M:\bold{Set} \to \bold{Set} which send a set X to (the underlying set of) 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 GM and MG give the free ring functor. We can now use the fact that the free ring admits a distributive law MG \to GM to show that it's also a monad. The distributive law of G over M means exactly that a product of sums (i.e. an element of M(G(X)) ) can be identified with a sum of products (an element of G(M(X)) ). Note that we say G(X) , the additive group, distributes over M(X) , the multiplicative monoid - contrary to the usual convention; see the next section. == Terminology ==

The original description by Beck calls l: TS \to ST a distributive law of S over T. However, some authors prefer the reverse terminology, where l 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 \prod \sum \to \sum \prod (see Examples). 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 T=S, the distributive law map reduces to K:T^2 \Rightarrow T^2, and one may impose some additional conditions. K is called a BD-law on T if: : (D) K is a distributive law, and : (B) it satisfies the Yang-Baxter equation: :: K_{T(X)} \circ T(K_X) \circ K_{T(X)} = T(K_X) \circ K_{T(X)} \circ T(K_X) :: (as maps T^3(X) \to T^3(X)). A BD-law is a BCD-law if the multiplication on T is "K-commutative", meaning that : (C) \mu^T_X \circ K_X = \mu^T_X :: (as maps T^2(X) \to T(X)). Condition (B) is called a Yang-Baxter equation because it literally is the Yang-Baxter equation defined on monoid objects, when T:\bold{C} \to \bold{C} is viewed as a monoid in the category of endofunctors on \bold{C}. Entwining For P an algebra and C a coalgebra over a shared field k, an entwining between them is a linear map \psi:C \otimes P \to P \otimes C satisfying analogous conditions to those that would be required, were \psi a distributive law. Specifically, the commutation diagram CCP \to PC that would be induced by a hypothetical multiplication CC \to C is replaced with one for C \otimes P \to P \otimes C \otimes C induced by the comultiplication C \to C \otimes C; likewise, the triangle diagram P \to PC is replaced with one of type C \otimes P \to P \otimes k, induced by the counit. == See also ==