Theory and Applications of Categories, Vol. 18, No. 7, 2007, pp. 172–208.

MONAD COMPOSITIONS I: GENERAL CONSTRUCTIONS AND RECURSIVE DISTRIBUTIVE LAWS

ERNIE MANES AND PHILIP MULRY

ABSTRACT. New techniques for constructing a distributive law of a monad over another are studied using submonads, quotient monads, product monads, recursively-defined distributive laws, and linear equations. Sequel papers will consider distributive laws in closed categories and will construct monad approximations for compositions which fail to be a monad.

1. Introduction

Is the free group generated by a free Boolean algebra a free algebra of yet a third type? In categorical language, the generalized question is “do monads compose?” It is known that a further element of structure called a distributive law classifies the composition of two monads just as additional structure is necessary to take the semidirect product of two groups. In [5], it was shown that a wide class of monad compositions are classified by distributive laws. While many papers about distributive laws have appeared in the interim including [1, 16, 25], less attention has been paid to general techniques for producing examples of these laws. Recent use of monads to model certain data types by functional programmers offers a new opportunity to uncover distributive laws as well as provide an interpretation of monad composition as a data structure whose elements are of another data structure.

Monads have found many applications over their forty year history: simplicial resolutions for sheaf cohomology, algebras over a monad (generalized universal algebra), the Kleisli category of a monad (frameworks for programming language semantics) and as data types in functional programming. See [22] for a survey with an extensive bibliography.

The classical duality theories such as Pontrjagin duality and Stone duality greatly enrich their subjects, particularly in situations where structure is better understood on one side. For example, the topological product of compact Hausdorff totally disconnected spaces is more familiar than the coproduct of Boolean algebras. There is a well known duality theory for monads as well, since the category of monads in a category C and monad maps is contravariantly equivalent to the category of monadic functors and forgetful functors over C. See Remark 2.4.4 below.

Received by the editors 2005-11-21 and, in revised form, 2007-03-14.

Transmitted by Walter Tholen. Published on 2007-04-12.

2000 Mathematics Subject Classification: 18C15, 18C20.

Key words and phrases: distributive law, linear equation.

\begin{matrix}c \\ ◯ \end{matrix} Ernie Manes and Philip Mulry, 2007. Permission to copy for private use granted.

We assume that the reader is familiar with elementary category theory, including basic definitions and facts about monads (some of which are reviewed in this paper). The category of sets and total functions will be denoted Set. See [19, Theorem VI.7.1, Page 147] for Beck’s monadicity theorem: a functor U is monadic if and only if it has a left adjoint and satisfies Beck’s coequalizer condition. An equationally definable class of algebras is monadic over Set if and only if the underlying set functor has a left adjoint, and this always happens if the operations are finitary.

In [5], Beck showed that if H, K are monads in the same category with functor parts H, K, then certain monads with functor part KH are classified by what he called distributive laws, which are natural transformations HK → KH subject to four axioms. The terminology is motivated by an example: the free ring is constructed from the free abelian group and the free monoid by a distributive law which expresses the usual distributivity of multiplication over addition (see Example 2.4.5 below). As Beck showed, distributive laws are also classified by functorial liftings of one monad to the category of algebras of the other.

General functorial liftings were introduced by [2, 7, 20, 26, 32]. More recently, the second author, in [28], developed a comprehensive parallel theory of liftings to the Kleisli category which had only previously been hinted at in [3, 26]. Distributive laws, it turns out, induce both types of liftings and can be characterized in terms of these liftings.

Section 2 and Section 3 set down some new results about distributive laws generally, while also providing a general introduction to past results. Section 4 establishes a class of recursive distributive laws for commutative monads over polynomial functors as well as the use of quotient distributive laws of these which are obtained by dividing out by linear equations. Finally, Section 5 applies the theory to lists and trees.

With regard to uncited basic facts and examples, the authors do not claim originality.

2. Preliminaries

To provide a clear framework for this paper and its sequels, we carefully review basic facts about monads and distributive laws and establish notations.

2.1. Monads.

2.1.1. Definition. A monad H = (H, μ, η) on category C is a triple consisting of an endofunctor H and two natural transformations η : id_{C} → H and μ : H^{2} → H satisfying

μ(Hη) = id_{H} = μ(ηH)  (1)
μ(Hμ) = μ(μH)  (2)

Alternatively ([20, Exercise 12, page 32]), a monad can be defined as H = (H, (–)^{#}, η) where H : Obj(C) → Obj(C), η assigns a morphism η_{A} : A → HA to each object A, and the extension operation (–)^{#} assigns to each α : A → HB a morphism α^{#} : HA → HB subject to the following three axioms for α : A → HB, β : B → HC.

α^{#}η_{A} = α  (3)
(η_{A})^{#} = id_{HA}  (4)
(β^{#}α)^{#} = β^{#}α^{#}  (5)

The first version gives the second if

α^{#} = HA ⟶^{Hα} HHB ⟶^{μ_{B}} HB  (6)

The second gives the first as follows where one defines

f^{♢} = (A ⟶^{f} B ⟶^{η_{B}} HB)  (7)
Hf = (f^{♢})^{#}  (8)
μ_{A} = (id_{HA})^{#}  (9)

Monads are plentiful as they can be generated by adjunctions as proved by Huber in [11].

2.1.2. Definition. If C has I-indexed products, then for every every I-indexed family T_{i} = (T_{i}, μ_{i}, η_{i}) of monads in C, define the cartesian product monad T = (T, μ, η) by

T X = ∏ T_{i}X
pr_{j} η_{X} = η_{j X}
pr_{j} (X ⟶^{[α_{i}]} T Y)^{#} = T X ⟶^{pr_{j}} T X_{j} ⟶^{α_{j}^{#}} T Y_{j}
pr_{j} (T T X ⟶^{μ_{X}} T X) = T T X ⟶^{pr_{i} pr_{i}} T_{i}T_{i}X ⟶^{μ_{i}} T_{i}X

Proof is routine.

2.1.3. Remark. For monad H = (H, μ, η), the definition of an (Eilenberg-Moore) Halgebra, (A, ξ), and the corresponding category CH of algebras is well known [8]. As first observed by [3, Definition 1, page 185], an equivalent definition is given by the axiom ξη_{A} = id_{A} and the following implication for α, β : C → HA

ξα = ξβ ⇒ ξα^{#} = ξβ^{#}  (10)

which we will explain in the next paragraph.

Such ξ is called the structure map of (A, ξ). A functor U : A → C is monadic if there exists a monad H in C and an isomorphism of categories Φ : A → CH with UHΦ = U where UH : CH → C is the underlying functor. U^{H} has a left adjoint A ↦ (HA, μ_{A}). If f : A → B and if (B, θ) is an H-algebra, the unique H-homomorphism f^{#} : (HA, μ_{A}) → (B, θ) with f^{#}η_{A} = f is given by

f^{#} = HA ⟶^{Hf} HB ⟶^{θ} B  (11)

(For f^{#} : (T A, μ_{A}) → (T B, μ_{B}), the two notions of (·)^{#} are easily seen to agree).

To see why (10) and ξη_{A} = id_{A} are equivalent to the H-algebra axioms (which are ξη_{A} = id_{A}, ξμ_{X} = ξ(Hξ)), if the implication holds then then ξid_{A} = (ξη_{A})ξ = ξ(η_{A}ξ) ⇒ ξ(T ξ) = ξ(ξ^{♢})^{#} = ξ(η_{A}ξ)^{#} = ξ(id_{T A})^{#} = ξμ_{A}. Conversely, if (A, ξ) is an H-algebra, ξα^{#} : (HC, μ_{C}) → (HA, μ_{A}) is the unique H-homomorphism extending ξα whence (10) holds.

Our next definition originates with [13].

2.1.4. Definition. Let H be a monad in C. The Kleisli category of H is the category C_{H} with the same objects as C and with morphisms C_{H}(A, B) = C(A, HB). The identity morphisms are η_{A} : A → HA and composition is given by

(B ⟶^{β} HC) ∘ (A ⟶^{α} HB) = A ⟶^{α} HB ⟶^{β^{#}} HC  (12)

2.1.5. Example. The list monad L = (L, μ, η) in Set is important in functional programming and we describe it in notations which are standard in computer science. LA is the set of all lists of elements of A, η_{A}(x) = [x] is the coercion function and α^{#}[x_{1}, …, x_{n}] = α(x_{1})+ + ⋯ + +α(x_{n}) (+ + = concatenation). The algebras for the monad are monoids and μ_{A} is commonly referred to as flatten.

2.1.6. Example. The power set monad in Set is P = (P, μ, η) with P X = 2^{X}, η_{X} x = {x}, μ_{X}(A) = {x : ∃ x ∈ A ∈ A}, and α^{#}A = ⋃_{a∈A} αa. Set_{P} is the category of

sets and relations and SetP is the category of complete semilattices. Detailed proofs are given in [20, Examples 3.5, 5.15].

2.1.7. Example. A trivial example of a monad in C is the identity monad id = (id, id, id). It is obvious that C_{id} ≅ C ≅ Cid. If C has binary powers X × X we may form the product monad R = id×id of Definition 2.1.2. For reasons we shall now explain, R is the rectangular bands monad.

When C = Set we have for α, β : X → Y, RX = X×X, η_{X}x = (x, x), (α, β)^{#}(x_{1}, x_{2}) = (αx_{1}, βx_{2}), and μ_{X}(a, b; c, d) = (a, d). Here we have abbreviated ((a, b), (c, d)) as (a, b; c, d). Now a rectangular band is a semigroup satisfying the equation xyx = x. If X is a rectangular band with multiplication ξ : X × X → X, then (X, ξ) is an R-algebra as follows. ξ η_{X}x = ξ(x, x) = x, noting that x^{2} = xx^{3} = xx^{2}x = x. Thus ξ η_{X} = id. For f : X → Y, Rf = (η_{Y} f)^{#} = f × f. Thus ξ(Rξ)(x, y; a, b) = ξ(ξ(x, y), ξ(a, b)) = xyab = (xbx)yab = xb(xya)b = xb = ξμ_{X}(x, y; a, b) which is the other algebra axiom. Conversely, if (X, ξ) is an R-algebra, then xy = ξ(x, y) is a rectangular band as follows.

(xy)z = ξ(ξ(x, y), ξ(z, z)) = ξμ_{X}(x, y; z, z) = ξ(x, z) = xz

Similarly, x(yz) = xz. In particular, xyx = xx = x. The reader may easily check that the R-algebra maps between rectangular bands are precisely the semigroup homomorphisms. For a general category with binary powers, it is an easy exercise to express the rectangular band equations by commutative diagrams and once again the resulting category of rectangular bands is the algebras over the monad id × id.

2.1.8. Example. Let S be a fixed set of states. The functor (–) × S is left adjoint to functor (–)^{S} and so defines a monad M = (M, ν, ρ) in Set where MA = (A × S)^{S}. Utilized in programming language semantics, this monad has been called both the sideeffects monad and state transformers monad [27, 31] where the unit and counit are well known: η(a) = λs.(a, s) and μ(T) = λs.let(t_{1}, s_{1}) = T s in t_{1}(s_{1}).

We provide a more neutral description of this monad (which we call the state monad) that will prove useful later in Example 4.2.18. A typical element of MA is (f, t) with f : S → A, t : S → S. For a ∈ A write â : S → A for the function constantly a and define η_{A}(a) = (â, id). We introduce the alternate notation ⟨ψ, x⟩ as a synonym for the evaluation ψx = ψ(x) of the function ψ on the argument x. For α : A → (B × S)^{S} define α^{#}((f, t)) = λs .⟨α(fs), ts⟩.

2.2. Liftings. Fix monads H = (H, η, μ) and K = (K, ρ, ν) on categories C and D respectively. Let F be a functor F : C → D. The notion of the lifting of a functor F exists for both Kleisli and Eilenberg-Moore categories as we now explore.

2.2.1. Definition. As shown in the diagram below, a functor F^{⋆} : CH → DK is an Eilenberg-Moore lifting or algebra lifting of F if the left square commutes, and a functor \overline{F} : C_{H} → D_{K} is a Kleisli lifting of F if the right square commutes.

[figure: C; D; F; CH; DK; F^{⋆}; UH; UK; C; D; F; C_{H}; D_{K}; \overline{F}; i_{H}; i_{K}]

Many authors would generally call an F^{⋆} a lifting and an \overline{F} an extension. We give some reasons why calling both a lifting seems preferable. First, liftings and extensions are categorically dual but algebra lifts and Kleisli lifts are not categorically dual; secondly, the term extension is already used to denote a monad operation so using this word differently would add confusion; thirdly, both algebra and Kleisli lifts are classified by natural transformations as specified in the next theorem, and it is useful to call these lifting transformations rather than needing two separate terms; fourthly, in what is arguably the most mainstream use of the word “lifting”, the homotopy lifting property, the lifting map is both a lifting and an extension; finally, the term Kleisli lift already appears in [28, 29]. The following results classify both types of lifting. The proofs are routine, if tedious, diagram chases. Details can be found in [2, 12, 28].

2.2.2. Theorem. Eilenberg-Moore liftings F^{⋆} : CH → DK are in bijective correspondence with natural transformations σ : KF → F H, and Kleisli liftings \overline{F} : C_{H} → D_{K} are in bijective correspondence with natural transformations λ : F H → KF satisfying

[figure: F; KF; ρF; F η; F H; σ; F HH; F μ; KKF; νF; (F^{⋆}A); (F^{⋆}B); KF H; Kσ; σH; F; F H; F η; ρF; KF; λ; KKF; νF; F HH; F μ; (\overline{F} A); (\overline{F} B); KF H; λH; Kλ]

The bijective correspondences between F^{⋆} and σ and between \overline{F} and λ are given by

F^{⋆}(A, ξ) = (F A, KF A ⟶^{σ_{A}} F HA ⟶^{F ξ} F A)  (13)
σ_{A} = KF A ⟶^{KF η_{A}} KF HA ⟶^{γ_{A}} F HA  (14)
\overline{F} A = F A, \overline{F} (A ⟶^{α} HB) = F A ⟶^{F α} F HB ⟶^{λ_{B}} KF B  (15)
λ_{A} = \overline{F} (id_{HA})  (16)

where F^{⋆}(HA, μ_{A}) = (F HA, KF HA ⟶^{γ_{A}} F HA). □

2.2.3. Definition. An important special case of the preceding theorem occurs for C = D and with F the identity functor. In that case, id^{⋆} : CH → CK is a functor over C, an “algebraic forgetful functor”, and it is classified by a monad map σ : K → H (note the reversal of direction).

Diagrams (F^{⋆}A), (F^{⋆}B) above reduce to (MMA), (MMB) respectively.

[figure: id; K; ρ; η; H; σ; HH; μ; KK; ν; σσ; (MMA); (MMB); KB; HB; σ_{B}; KA; HA; σ_{A}; α^{#}; (σ_{B}α)^{##}; (MM #)]

It is not hard to see that an assignment A ↦ σ_{A} : KA → HA (not assumed a priori to be natural) is a monad map if and only if it satisfies (MM A) and (MM #) (where we use two versions of # to distinguish between the extension operations of the two monads).

Similarly monad maps can equivalently be characterized via Kleisli liftings. We leave the details to the reader.

Monads and monad maps form a category and the cartesian product monad in Definition 2.1.2 is indeed a product in this category. Details can be found in [30].

2.2.4. Definition. If H = (H, μ, η) is a monad in C and for each X there is a given monic j_{X} : H_{0}X → HX, then we say that H_{0} is a submonad of H if η_{X} = η_{0X} j_{X}

factors through j_{X} and if, for all α : A → H_{0}B, H_{0}A ⟶^{j_{A}} HA ⟶^{(j_{B} α)^{#}} HB = α^{##}j_{B}

factors through j_{B}. Setting μ_{0X} = id_{H_{0}X}^{##}, H_{0} = (H_{0}, μ_{0}, η_{0}) is a monad with j : H_{0} → H a monad map.

2.2.5. Example. The power set monad P of Example 2.1.6 has many natural submonads, e.g. finite subsets, non-empty subsets and non-empty finite subsets [20]. Likewise, any intersection of submonads is a submonad in any category with appropriate intersections of subobjects.

It is possible to characterize Kleisli liftings without iterating any of the three functors, as we next see. A corresponding result for general algebra lifts is not known at this time, even though we succeeded for the special case of monad maps.

2.2.6. Proposition. Kleisli liftings \overline{F} : C_{H} → D_{K} are in bijective correspondence with families λ_{A} : F HA → HF A satisfying (\overline{F} A) above and (\overline{F} #) for α : A → HB, and

γ = F A ⟶^{F α} F HB ⟶^{λ_{B}} KF B

[figure: KF A; KF B; γ^{##}; F HA; F HB; F α^{#}; λ_{A}; λ_{B}] (\overline{F} #)

where α^{#} is the extension operation of H and γ^{##} is the extension operation of K.

Proof. The correspondences are just those of (15) and (16). We show that naturality, (\overline{F} A) and (\overline{F} B) are equivalent to (\overline{F} A) and (\overline{F} #). First assume naturality and (\overline{F} B)

and show (\overline{F} #). γ^{##}λ_{A} = ν_{F B} (Kγ) λ_{A} (by 6) = F HA ⟶^{λ_{A}} KF A ⟶^{KF α} KF HB ⟶^{Kλ_{B}}

KKF B ⟶^{ν_{F B}} KF B = ν_{F B} (Kλ_{B}) λ_{HB}(F Hα) (λ natural) = λ_{B} (F μ_{B})(F Hα) (by (\overline{F} B))

= λ_{B} (F α^{#})

Conversely, (\overline{F} A) and (\overline{F} #) imply naturality and (\overline{F} B) as follows. Given f : A → B,

Hf = (A ⟶^{f} B ⟶^{η_{B}} HB)^{#}, so λ_{B} (F Hf) = λ_{B} F ((η_{B}f)^{#}) = (F A ⟶^{F f} F B ⟶^{F η_{B}}

F HB ⟶^{λ_{B}} KF B)^{##} λ_{A} (by \overline{F} #)) = (F A ⟶^{F f} F B ⟶^{ρ_{F B}} KF B)^{##} λ_{A}(by (\overline{F} A)) =

(KF f) λ_{A} shows naturality. If α = id_{HB}, α^{#} = μ_{B} and γ = λ_{B}, so (\overline{F} #) is exactly (\overline{F} B). □

The natural transformations that arise via functor liftings can be applied to arbitrary monads and functors. We denote such natural transformations as lifting transformations. Many examples of lifting transformations can be found in [28, 29]. A very special case of a lifting transformation is a distributive law which will be introduced shortly.

2.3. Monad Map Lemmas. We state three basic lemmas that will prove useful in the study of the category of distributive laws to be defined shortly. We work in a category C.

2.3.1. Lemma. Let σ : (H′, μ′, η′) → (H, μ, η), τ : (K′, ν′, ρ′) → (K, ν, ρ) be monad maps. Then the following five diagrams commute.

[figure: id; K′H′; ρ′η′; ρη; KH; τσ; K′H′; KH; τσ; K′K′H′H′; KKHH; ττσσ; ν′μ′; νμ; H′; K′H′; ρ′H′; ρσ; KH; τσ; (τσ A); (τσ C); (τσ B)]

[figure: K′; K′H′; K′η′; τη; KH; τσ; K′H′K′H′; KHKH; τστσ; K′H′; KH; τσ; K′η′ρ′H′; KηρH; (τσ D); (τσ E)]

Proof. The proofs are straightforward diagram chases exploiting the monad properties of σ and ρ. □

2.3.2. Lemma. Let σ : Q → R be a natural transformation. Let η : id → Q, μ : QQ → Q, ρ : id → R, ν : RR → R be maps (not assumed to be natural transformations) satisfying

[figure: id; Q; η; ρ; R; σ; RR; ν; QQ; μ; σσ]

Then the following hold:

1. If σ has monic components (that is, each σ_{A} is monic) and (R, ν, ρ) is a monad then (Q, μ, η) is a monad.

2. If σ and Qσ have epic components and (Q, μ, η) is a monad then (R, ν, ρ) is a monad.

Proof. We’ll prove the second statement. The first is similar and easier. Referring to the diagram below, (A,A’) are given. For (B), (Rν)(σσσ) = (Rν)(σRR)(Qσσ) = (σR)(Qν)(Qσσ) = (σR)(Qσ)(Qμ) = (σσ)(Qμ) by the functoriality of Q and (A). (B’) commutes if either μ or ν are natural as follows. If μ is natural, then (νR)(σσσ) = (νR)(σσR)(QQσ) = (σR)(μR)(QQσ) = (σR)(Qσ)(μQ) = (σσ)(μQ) whereas, if ν is natural, (νR)(σσσ) = (νR)(RRσ)(σσQ) = (Rσ)(νQ)(σσQ) = (Rσ)(σQ)(μQ) = (σσ)(μQ).

This diagram shows that under the hypotheses of (1.), μ(Qμ) = μ(μQ) whereas, under the hypotheses of (2.) (which guarantee σσσ has epic components) that ν(Rν) = ν(νR). An entirely similar diagram (but much less complicated proof) relates the naturality of μ and ν.

[figure: QQ; Q; μ; QQQ; QQ; Qμ; μQ; μ; RR; R; ν; RRR; RR; Rν; νR; ν; σσσ; σσ; σσ; σ; (A); (B); (B′); (A′)]

2.3.3. Lemma. Given monads (Q, μ, η), (Q′, μ′, η′), (R, ν, ρ), (R′, ν′, ρ′) and a commutative square

[figure: R′; R; β; Q′; Q; α; γ; σ]

in which γ, σ are monad maps and α, β are natural transformations, the following hold:

1. If β is a monad map and σ has monic components then α is a monad map.

2. If α is a monad map and if γγ has epic components (e.g. if γ and either of Q′γ, R′γ have epic components) then β is monad map.

Proof. The proof is left to the reader □

2.3.4. Lemma. If λ : (H, μ, η) → (K, ν, ρ) is a monad map then λ_{X} : (HX, μ_{X}) → (KX, ν_{X}λ_{KX}) is an H-homomorphism.

Proof. The induced forgetful functor CK → CH maps (KX, ν_{X}) to (KX, ν_{X}λ_{KX}), so the latter is an H-algebra. That λ_{X} is a homomorphism is then precisely (MM B). □

2.3.5. Lemma. Let λ : (H, μ, η) → (K, ν, ρ) be a monad map with monic components. Let ψ : (KX, ν_{X}λ_{KX}) → (KY, ν_{Y} λ_{KY}) be an H-homomorphism and suppose that there exists a fill-in φ as shown

[figure: KX; KY; ψ; HX; HY; φ; λ_{X}; λ_{Y}]

Then φ : (HX, μ_{X}) → (HY, μ_{Y}) is an H-homomorphism as well.

Proof. It is obvious that if a map followed by a monic homomorphism is a homomorphism then the map is itself a homomorphism. Now use the previous lemma. □

2.4. Distributive Laws. Beck [5] defined distributive laws in terms of the four diagrams (DL A), (DL B), (DL C), (DL D) below. As we’ve already noted, Kleisli liftings came later. We continue to fix monads H = (H, μ, η), K = (K, ν, ρ), but now in the same category C.

2.4.1. Definition. A distributive law of K over H is a natural transformation λ : HK → KH for which the following four diagrams commute.

[figure: H; HK; Hρ; HKK; Hν; KKH; νH; KH; λ; λK; KHK; Kλ; ρH; (DL A); (DL B); (Kleisli lift \overline{H}); K; HK; ηK; HHK; μK; KHH; Kμ; KH; λ; Hλ; HKH; λH; Kη; (DL C); (DL D); (Algebra lift K^{⋆})]

We emphasize that (DLA) = (\overline{F} A), (DLB) = (\overline{F} B) with F = H and that (DLC) = (F^{⋆} A), (DL D) = (F^{⋆} B) with F = K. Thus we have

2.4.2. Theorem. Given monads H and K on C, a natural transformation λ : HK → KH is a distributive law of K over H if and only if it classifies both a Kleisli lifting \overline{H} : C_{K} → C_{K} and an algebra lifting K^{⋆} : CH → CH. □

The next few results are due to [5] so no proofs are given.

2.4.3. Theorem. If λ : HK → KH is a distributive law of K over H then

K ∘_{λ} H = (KH, (νμ)(KλH), ρη)  (17)

is a monad in C whose algebras are isomorphic to the category of all (A, ξ, θ) with (A, ξ) a K-algebra and (A, θ) an H-algebra such that the following composite law holds:

[figure: HKA; KHA; λ_{A}; A; θ; HA; Hξ; Kθ; KA; ξ; (CL)]

Here, the morphisms f : (A, ξ, θ) → (A′, ξ′, θ′) are simultaneous H- and K-homomorphisms. The K ∘_{λ} H-structure map corresponding to (A, ξ, θ) is ξ(Kθ), whereas if (A, γ) is a K ∘_{λ} H-algebra, the corresponding composite structure (A, ξ, θ) is given by ξ = γ(Kη_{A}), θ = γ(ρ_{HA}). The passage λ ↦ K ∘_{λ} H is a bijection from the class of distributive laws of K over H to the class of natural transformations m : KHKH → KH with (KH, m, ρη) a monad for which ρH, Kη are monad maps and m(KηρH) = id_{KH}. The inverse bijection is given by

λ = HK ⟶^{ρHKη} KHKH ⟶^{m} KH  (18)
□

Since (Kθ)λ_{A} is the structure map of K^{⋆}(A, θ), the composite law simply asserts that

K^{⋆}(A, θ) ⟶^{ξ} (A, θ) is a H-homomorphism  (19)

2.4.4. Remark. In [18], Lüth and Ghani advocate monad coproduct as a useful way to combine monads in monad programming. Here, we very briefly discuss how coproducts relate to distributive laws.

By the duality between monads and their algebras, if the coproduct K + H exists in the category of monads in C and monad maps, its algebras must be CK ×_{C} CH, the category whose objects are all (X, ξ, θ) with (X, ξ) a K-algebra and (X, θ) an H-algebra, satisfying no further condition; the maps are simultaneous K- and H-homomorphisms. We discuss only C = Set; see [20, 22] for tools to generalize to other categories. If K + H exists, the equations (CL) show that if λ : HK → KH is a distributive law, its algebras form a variety of (K + H)-algebras so that every monad K ∘_{λ} H is a quotient of K + H ([20, Theorem 3.3.6]).

Even if λ is not a distributive law, the monad defined by (CL) exists as a quotient of K + H which is a better approximation of the composition than K + H itself. These matters will be considered in the sequel paper [24].

K + H does not always exist. For example, let P be the power set monad of Example 2.1.6 and let H be the monad whose algebras are (X, 0, 1, (·)′, ∧) with 0, 1 ∈ X, x′ a unary operation and x ∧ y a binary operation. Then complete Boolean algebras forms a variety of (P + H)-algebras which —if P + H exists— is monadic by [20, Theorem 3.3.6]. But by the theorems of [9, 10], free complete Boolean algebras do not exist, so P + H does not exist either.

On the other hand, if (Σ, E) and Σ′, E′) are bounded equational presentations (i.e. there exists a cardinal n such that Σ_{m} = ∅ = Σm^{′} for m ≥ n) then, by [20, Theorem 3.1.27], the corresponding categories of algebras are monadic by monads H, H′ and H + H′ exists with algebras presented by (Σ + Σ′, E + E′).

The next example led Beck to the term “distributive law”.

2.4.5. Example. The equational classes of abelian groups and monoids give rise, respectively, to monads K and L. KA is the free abelian group ⊕_{A}Z Z generated by A and L is the list monad of Example 2.1.5. Write an element of KA as an A-indexed sequence (m_{a} : a ∈ A) in Z Z (understood to be finitely nonzero) and write an element of LA as a list [a_{1}, …, a_{n}] of elements of A (n ≥ 0). Then a distributive law λ : LK → KL is defined by

λ_{A}[(m_{a_{1}}^{1}), …, (m_{a_{n}}^{n})] = ∑_{a_{1}} ⋯ ∑_{a_{n}} [m_{a_{1}}^{1}, …, m_{a_{n}}^{n}]

(i.e., a product of sums transforms to a sum of products, the usual distributivity of multiplication over addition). The resulting monad K ∘_{λ} L is that induced by the forgetful functor from rings with unit.

2.4.6. Example. Let C be any category and let G be an object. The category of G-pointed objects, G/C, is monadic over C providing that C has binary coproducts. In that case, if H is the resulting monad, for every monad K in C there is a canonical distributive law of K over H whose composite algebras are all (A, ξ, x) with (A, ξ) a K-algebra and (A, x) a G-pointed object. H is defined by HA = A + G, η_{A} = in_{1} : A → A + G, μ_{A} = 1 + [1, 1] : (A + G) + G ≅ A + (G + G) → A + G. λ_{A} : KA + G → K(A + G) has first coordinate Kin_{1} and second coordinate ρ_{A+G} in_{2}. The reader may easily provide all the details.

2.4.7. Example. The families monad is P^{2} = (P^{2}, m, e) where P^{2}X = P (P X) = 2^{2^{X}} is the set of families of subsets of X, e_{X}x = {{x}} and m : P^{4} → P^{2} is defined on families 𝒜 𝒜 whose elements Λ are sets whose elements are families A ∈ P^{2}X by

m_{X}(𝒜 𝒜) = { ⋃_{A∈Λ} S_{A} : Λ ∈ 𝒜 𝒜, (S_{A}) ∈ ∏_{A∈Λ} A}

Moreover, for φ : X → P^{2}Y,

φ^{#}(A) = {⋃_{x∈A} B_{x} : A ∈ A, B_{x} ∈ φx}

A complete proof that the above gives a monad appears in [22, pages 78-79]. If (P, μ, η) is the power set monad of Example 2.1.6, e = ηη : id → P^{2}. We leave to the reader the verification that P η and ηP are monad maps P → P^{2} (hint: use (MM #)) and that m(P eP) = id_{P^{2}}, so it follows from Theorem 2.4.3 that λ = m(ηP^{2}η) : P^{2} → P^{2} is a distributive law of P over itself. One calculates that

λ_{X}(A) = {{a_{A} : A ∈ A} : (a_{A}) ∈ ∏_{A∈A} A}

In an email communication, Steve Vickers pointed out to us that a verification of (DL B) or (DL D) would appear to involve the axiom of choice. Our approach via Theorem 2.4.3 avoids AC.

2.4.8. Example. Let P be the power set monad and let L be the list monad. Define a distributive law λ : LP → P L of P over L by λ_{X}[A_{1}, …, A_{n}] = {[a_{1}, …, a_{n}] : a_{i} ∈ A_{i}}. We leave it to the reader to check that λ satisfies the conditions of Definition 2.4.1. A composite algebra is (A, ⋁, ∗, e) with (A, ⋁) a complete sup-semilattice and (A, ∗, e) a monoid satisfying the composite law

(⋁ a_{i}) ∗ (⋁ b_{j}) = ⋁_{ij}(a_{i} ∗ b_{j})

These algebras are called quantales in the literature. The algebra lifting P^{⋆} maps the monoid (A, ∗, e) to the monoid (P A, ∗_{P} , {e}) where A ∗_{P} B = {a ∗ b : a ∈ A, b ∈ B}. The Kleisli lift \overline{L} maps the relation R : A → P B to the relation \overline{L}R : LA → P LB where [a_{1}, …, a_{n}] (\overline{L}R) [b_{1}, …, b_{m}] ⇔ m = n and (∀ i) a_{i} R b_{i}.

Continuing with general background from Beck’s paper, we have the following theorem.

2.4.9. Theorem. If λ : HK → KH is a distributive law, not only does K lift to K^{⋆} : CH → CH but, additionally, for each H-algebra (A, θ),

ρ_{A} : (A, θ) ⟶ K^{⋆}(A, θ)
ν_{A} : K^{⋆}K^{⋆}(A, θ) ⟶ K^{⋆}(A, θ)

are H-homomorphisms, so that the entire monad K lifts to a monad K^{⋆} in CH. The passage from distributive laws λ to lifted monads (K^{⋆}, ρ, ν) in CH is bijective. The algebras over the lifted monad are exactly the composite algebras of K ∘_{λ} H, but now with forgetful functor C^{K∘_{λ}H} → CK. □

The next result –no doubt known to some– seems not to be in print, so we include it here for completeness, leaving the details to the reader.

2.4.10. Proposition. The free composite algebra generated by A has K-structure ν_{HA} : KKHA → KHA, and H-structure (Kμ_{A})λ_{HA} : HKHA → KHA. Moreover, the map λ_{A} : (HKA, μ_{KA}) → (KHA, (Kμ_{A})λ_{HA}) is an H-homomorphism. □

3. The Category of Distributive Laws

In this section we work in a category C and consider a category whose objects are distributive laws of monads in C. We focus on situations that produce new distributive laws from old ones.

3.1. Preliminaries. The next two results can be found in [30].

3.1.1. Definition. Let H = (H, μ, η), H′ = (H′, μ′, η′), K = (K, ν, ρ), K′ = (K′, ν′, ρ′) be monads in C and let λ : HK → KH, λ′ : H′K′ → K′H′ be distributive laws. A morphism of distributive laws λ′ → λ is a pair (σ, τ) where σ : H′ → H, τ : K′ → K are monad maps such that the following square commutes.

[figure: HK; KH; λ; H′K′; K′H′; λ′; στ; τσ]

A category of distributive laws results with identities (id, id) and composition (σ_{1}, τ_{1})(σ, τ) = (σ_{1}σ, τ_{1}τ).

3.1.2. Theorem. If (σ, τ) : λ′ → λ is a morphism of distributive laws, τσ : K′ ∘_{λ′} H′ → K ∘_{λ} H is a monad map. The corresponding algebraic functor C^{K∘_{λ}H} → C^{K′∘_{λ′}H′} is described at the level of composite algebras by

(A, KA ⟶^{ξ} A, HA ⟶^{θ} A) ↦ (A, K′A ⟶^{τ_{A}} KA ⟶^{ξ} A, H′A ⟶^{σ_{A}} HA ⟶^{θ} A)

□

The next result is one of our principal tools for creating new distributive laws.

3.1.3. Theorem. Let H = (H, μ, η), H′ = (H′, μ′, η′), K = (K, ν, ρ), K′ = (K′, ν′, ρ′) be monads in C, let σ : H′ → H, τ : K′ → K be monad maps and let λ : HK → KH, λ′ : H′K′ → K′H′ be maps (that are not necessarily assumed to be natural transformations) such that the following square commutes.

[figure: HK; KH; λ; H′K′; K′H′; λ′; στ; τσ]

Then the following hold.

1. If λ is a distributive law of K over H and τσ has monic components, then λ′ is a distributive law of K′ over H′.

2. If λ′ is a distributive law of K′ over H′, if σ, τ have epic components, if either H or H′ preserves epics and if either K or K′ preserves epics, then λ is a distributive law of K over H.

Proof. The proof is left to the reader. □

3.2. Distributive Laws for Products.

3.2.1. Theorem. Let λ_{i} : HK_{i} → K_{i}H be distributive laws and let the pointwise product monad K = ∏ K_{i} exist as in Definition 2.1.2. Define λ by

[figure: HK_{i}; K_{i}H; λ_{i}; HK; KH; λ; Hpr_{i}; pr_{i}H]

Then λ is a distributive law.

Proof. Though not a formal corollary of Theorem 3.1.3 (1) (with σ = id, τ = pr_{i}), the same proof works since pr_{i} H is a jointly monic family. □

3.2.2. Example. Let C be a category with binary powers, let H = (H, μ, η) be any monad in C and let R = (R, ν, ρ) be the rectangular bands monad of Example 2.1.7. The unzip map unzip : HR → RH is defined as (Hpr_{1}, Hpr_{2}). (When H is the list monad, this is the usual unzip map).

As was first shown by [6] for Set, unzip is a distributive law of R over H. To show this in the current more general context, first observe that id : H id → id H is a distributive law (whose algebras are just C^{H}). The preceding theorem then gives a distributive law HR → RH which is routinely checked to be unzip. It is easily computed that R^{⋆}(A, ξ) is the product algebra (A, ξ) × (A, ξ) and that

\overline{H}(A ⟶^{(a,b)} B × B) = HA ⟶^{(Ha,Hb)} HB × HB

3.2.3. Theorem. Let λ_{i} : H_{i}K → KH_{i} be distributive laws and let the pointwise product H = ∏ H_{i} exist and be preserved by K. Then λ defined as

[figure: H_{i}K; KH_{i}; λ_{i}; HK; KH; λ; pr_{i}K; Kpr_{i}]

is a distributive law.

Proof. The proof is entirely similar to that of Theorem 3.2.1 and is left for the reader. □

3.3. Distributive Laws for Submonads. We study the consequences of Theorem 3.1.3 when σ, τ are submonads. To begin, we make an observation about monads of sets. Let f : X → Y be an injective function. For every functor K : Set → Set, Kf is monic if X ≠ ∅ or X = KX = ∅. If X = ∅, KX ≠ ∅ then Kf might not be monic. For example, let A have more than one element and consider the functor K∅ = A, KY = 1 if Y ≠ ∅. However, we have

3.3.1. Lemma. If (K, ν, ρ) is a monad in Set then K preserves monics.

Proof. Let f : ∅ → Y be the unique function. If K∅ ≠ ∅ let g : Y → K∅ be any function. Then K∅ ⟶^{Kf} KY ⟶^{g^{#}} K∅ is the unique K-homomorphism id_{K∅} so Kf is monic. □

Thus the condition that τσ have monic components in part (1) of Theorem 3.1.3 always holds in Set if σ, τ both have monic components, since τσ = (τH)(K′σ) and K′σ has monic components.

3.3.2. Example. Let K be the monad for abelian groups, let L be the list monad of Example 2.1.5 and let λ : LK → KL be the distributive law of Example 2.4.5 for which the K∘_{λ}L-algebras are rings with unit. Let K_{0} A = ⊕_{A} IN ⊂ ⊕_{A} Z Z = KA, so that τ : K_{0} → K is a submonad of K whose algebras are abelian monoids, as is easily calculated. Let σ : L^{+} → L be the submonad of non-empty lists, whose algebras are semigroups. When λ_{A} is applied to a nonempty product of non-negative sums, the resulting sum of products lies in K_{0} L^{+}A, giving rise to a fill-in λ′ : L^{+}K_{0} → K_{0}L^{+} which is a distributive law by the theorem.

We leave it to the reader to verify that the K_{0} ∘_{λ′} L^{+}-algebras are semirings (without unit). The axiom x0 = 0 = 0x is established by considering empty sums.

3.3.3. Example. Let λ : PP → PP be the distributive law of Example 2.4.7. Let σ : P_{0} → P be the submonad of finite subsets —it is a submonad because a finite union of finite sets is finite. Similarly, a countable union of countable sets is countable giving rise to the submonad τ : P_{ω} → P of countable subsets. If A is a finite family of countable subsets of X, λ_{X}(A) = {{a_{A} : A ∈ A} : (a_{A}) ∈ ∏_{A} A} is a countable family of finite sets, a finite product of countable sets being countable. The resulting fill-in λ′ : P_{0}P_{ω} → P_{ω}P_{0} is a distributive law by the theorem. It is routine to check that there is no fill-in P_{ω}P_{0} → P_{0}P_{ω}.

We turn now to corollaries of Theorem 3.1.3 that result when one of σ, τ is the identity and the other is a submonad.

3.3.4. Corollary. Let H = (H, μ, η), K = (K, ν, ρ) be monads in C and let σ : (H′, μ′, η′) → H be a submonad of H in such a way that Kσ has monic components. Let λ : HK → KH be a distributive law of K over H. If there exists a (necessarily unique) fill-in λ′ in the left diagram then λ′ is a distributive law of K over H′ and Kσ : K ∘_{λ′} H′ → K ∘_{λ} H is a submonad. In that case, if U : C^{H} → C^{H′} is the forgetful functor corresponding to σ, the right square commutes.

[figure: HK; KH; λ; H′K; KH′; λ′; σK; Kσ; C^{H}; C^{H′}; U; C^{H}; C^{H′}; U; K^{⋆}; K^{⋆}]

Proof. By part (1) of the theorem with τ = id, λ′ is a distributive law and Kσ is a submonad by Theorem 3.1.2. As U and both K^{⋆} are over C, we need only chase objects. For (A, ξ) an H-algebra we have K^{⋆}U(A, ξ) = K^{⋆}(A, ξ σ_{A}) = (KA, (Kξ)(Kσ_{A}) λ′_{A}) = (KA, (Kξ) λ_{A} σ_{KA}) = U(KA, (Kξ) λ_{A}) = UK^{⋆}(A, ξ) □

3.3.5. Example. In the context of Example 3.2.2, let σ : H′ → H be a submonad. Then (σ × σ) unzip = unzip (σR).

The previous corollary applies because, in any category with binary powers, f × f is monic when f is.

Before stating the next result, we observe that if ι : S → K is a submonad then the induced functor C_{S} → C_{K}, A ⟶^{α} SA ↦ A ⟶^{α} SB ⟶^{ι_{B}} KB, is a subcategory. This is obvious since ι_{B} is monic.

3.3.6. Corollary. Let λ : HK → KH be a distributive law of K over H and let τ : (K′, ν′, ρ′) → K be a submonad. Then there exists a fill-in λ′ (necessarily unique, not assumed to be natural a priori) as shown, if and only if \overline{H} maps C_{K′} into C_{K′}. In that case, λ′ is a distributive law of K′ over H and τH : K′ ∘_{λ′} H → K ∘_{λ} H is a submonad.

[figure: HK; KH; λ; HK′; K′H; λ′; Hτ; τH]

Proof. If the fill-in λ′ exists, it is a distributive law by (1) of the theorem with σ = id, and then τH is a submonad by Proposition 3.1.2. First assume that λ′ exists. For

α : A → K′B, define Ĥα = HA ⟶^{Hα} HK′B ⟶^{λ′_{B}} K′HB. As

\overline{H}(A ⟶^{α} K′B ⟶^{τ_{B}} KB) = HA ⟶^{Hα} HK′B ⟶^{Hτ_{B}} HKB ⟶^{λ_{B}} KHB

we have

τ_{HB}(Ĥα) = λ_{B} (Hτ_{B}) (Hα) = \overline{H}(τ_{B} α)

that is, \overline{H} maps C_{K′} into C_{K′} (via Ĥ). Conversely, assume Ĥ exists such that

[figure: C_{K}; C_{K}; \overline{H}; C_{K′}; C_{K′}; Ĥ]

commutes. As C_{K′} is a subcategory and \overline{H} is functorial, Ĥ must be functorial as well so Ĥ classifies a Kleisli lift with transformation λ′_{A} = Ĥ(id_{K′A}) following (16). We have

HK′A ⟶^{λ′_{A}} K′HA ⟶^{τ_{HA}} KHA = \overline{H}(K′A ⟶^{id} K′A ⟶^{τ_{A}} KA)
= HK′A ⟶^{Hτ_{A}} HKA ⟶^{λ_{A}} KHA

so that λ′ is the desired fill-in. □

3.3.7. Example. Let λ be the distributive law of Example 2.4.8. The non-empty subset monad P^{+} is clearly a submonad of P. The Kleisli lifting of that example takes total relations to total relations. Thus the lifting \overline{L} on Set_{P} factors through Set_{P^{+}}. By Corollary 3.3.6, there exists a distributive law λ′ : LP^{+} → P^{+}L and P^{+}L is a composite monad. Similarly, if P_{0} is the submonad of finite sets, then the lifting \overline{L} takes finite relations to finite relations generating a distributive law λ′ : LP_{0} → P_{0}L.

3.4. Distributive Laws for Quotients. In this section, we study the consequences of Theorem 3.1.3 (2). While little is known about the relation between algebras of a submonad in terms of the algebras of the ambient monad, monad quotients are better understood. For monads on sets, H, the algebras of a quotient form a variety of algebras of H (see [22]). The next lemma shows that over general categories we can at least expect a full subcategory of the original algebras.

3.4.1. Lemma. For the monads H = (H, μ, η), H′ = (H′, μ′, η′), let σ : H → H′ be a monad map which has epic components and with induced forgetful functor Ψ : C^{H′} → C^{H}. Then Ψ is a full subcategory. Moreover, if Hσ_{X} is epic for all X and ξ′ : H′X → X is such that (X, ξ′σ_{X}) is an H-algebra, then (X, ξ′) is an H′-algebra.

Proof. If (X, ξ′) is an H′-algebra, Ψ(X, ξ′) = (X, ξ′ σ_{X}). Ψ is injective on objects because σ_{X} is epic. If f : Ψ(X, ξ′) → Ψ(Y, θ′) is an H-homomorphism, fξ′σ_{X} = θ′σ_{Y} (Hf) = θ′(H′f)σ_{X} (as σ is natural) so that, as σ_{X} is epic, θ′(H′f) = fξ′ and f : (X, ξ′) → (Y, θ′) is an H′-homomorphism. Now assume that (X, ξ) is an H-algebra with ξ = ξ′σ_{X}. Then ξ′η′_{X} = ξ′σ_{X}η_{X} (σ monad map) = ξη_{X} = id_{X} is the first algebra law. For the second,

ξ′(H′ξ′)σ_{H′X}(Hσ_{X}) = ξ′σ_{X}(Hξ′)(Hσ_{X}) (σ natural)
= ξ(Hξ) = ξμ_{X} (H-algebra)
= ξ′σ_{X}μ_{X} = ξ′μ′_{X}(σσ)_{X} (σ monad map)
= ξ′μ′_{X}σ_{H′X}(Hσ_{X})

As σ_{H′X}(Hσ_{X}) is epic, ξ′(H′ξ′) = ξ′μ′_{X}, which is the second algebra law. □

The next result will be important in establishing Theorem 4.3.4 below. We note that if σ : H → H′ is a natural transformation which has epic components, if H preserves epics then H′ necessarily does, so we condense the hypothesis of (2) of Theorem 3.1.3 to H preserving epics. Of course, all endofunctors of Set preserve epics.

3.4.2. Corollary. Let H = (H, μ, η), K = (K, ν, ρ), H′ = (H′, μ′, η′) be monads in C and let σ : H → H′ be a monad map with epic components. Assume that H, K preserve epics. Let λ : HK → KH be a distributive law of K over H with corresponding algebra lift K^{⋆} : CH → CH. Then there exists a (necessarily unique, not a priori assumed natural) fill-in λ′

[figure: H′K; KH′; λ′; HK; KH; λ; σK; Kσ]

if and only if K^{⋆} maps C^{H′} into itself. In that case, λ′ : H′K → KH′ is a distributive law of K over H′.

Proof. If λ′ exists, it is a distributive law by the theorem with τ = id. Kσ is then a monad map by Proposition 3.1.2. If (A, θ′) is an H′-algebra, it is the H-algebra (A, θ′ σ_{A}). K^{⋆}(A, θ′ σ_{A}) is then the H-algebra (KA, (Kθ′)(Kσ_{A}) λ_{A}) = (KA, (Kθ′)λ′_{A} σ_{KA}) so that (KA, (Kθ′)λ′_{A}) is an H′-algebra by Lemma 3.4.1. Conversely, assume that K^{⋆} maps C^{H′} into itself. Note that σ_{X} : (HX, μ_{X}) → (H′X, μ′_{X}σ_{H′X}) is an H-homomorphism. Writing

K^{⋆}(HX, μ_{X}) = (KHX, HKHX ⟶^{γ_{X}} KHX)
K^{⋆}(H′X, μ′_{X}σ_{H′X}) = (KH′X, HKH′X ⟶^{γ̂_{X}} KH′X)

K^{⋆} maps σ_{X} to the H-homomorphism Kσ : (KHX, γ_{X}) → (KH′X, γ̂_{X}) with

γ̂_{X} = HKH′X ⟶^{σ_{KH′X}} H′KH′X ⟶^{γ′_{X}} KH′X

for a unique H′-algebra structure γ′_{X}. By (14),

λ = HK ⟶^{HKη} HKH ⟶^{γ} KH

This suggests that we define

λ′ = H′K ⟶^{H′Kη′} H′KH′ ⟶^{γ′} KH′

and we do. We can now verify the fill-in property.

(Kσ) λ = (Kσ) γ (HKη)
= γ̂ (HKσ)(HKη) (Kσ H-homomorphism)
= γ̂ (HKη′) (σ MM A)
= γ′ (σKH′)(HKη′)
= γ′ (H′Kη′)(σK) (σ natural)
= λ′ (σK)
□

3.4.3. Corollary. Let λ : HK → KH be a distributive law of K over H and let τ : K → K′ be a monad map with epic components. Assume that H and K′ preserve epics and that there exists a fill-in

[figure: HK′; K′H; λ′; HK; KH; λ; Hτ; τH]

Then λ′ is a distributive law of K′ over H.

Proof. By Theorem 3.1.3 (2). □

3.4.4. Example. An example of the previous corollary obtains if λ : LK → KL is the distributive law for rings of Example 2.4.5 and τ : K → P_{0} is the quotient obtained by mapping a finitely non-zero sequence to its set of non-zero indices; here, P_{0} is the finite subsets monad.

We leave it to the reader to verify that τ is a monad map and that there is a fillin LP_{0} → P_{0}L for which the free P_{0} ∘_{λ′} L-algebra P_{0}LX is the usual semiring of finite languages on X.

4. Recursively-defined distributive laws

The main goals of this section are Theorem 4.2.20 and Theorem 4.3.4 which establish a wide class of recursively-defined distributive laws for monads in Set.

4.1. Polynomial Functors and Σ-Algebras.

4.1.1. Definition. A (finitary) signature is a sequence of sets Σ = (Σ_{n} : n = 0, 1, 2, …), any of which may be empty. For such Σ, a Σ-algebra is (X, δ) where X is a set and δ assigns to ω ∈ Σ_{n} an n-ary operation δ_{ω} : X^{n} → X (if n = 0, δ_{ω} ∈ X is a constant). A Σ-homomorphism f : (X, δ) → (Y, ϵ) is a function f : X → Y such that ∀ω ∈ Σ_{n}, ϵ_{ω}(fx_{1}, …, fx_{n}) = f(δ_{ω}(x_{1}, …, x_{n})).

Evidently, Σ-algebras and their homomorphisms form a category.

4.1.2. Definition. Let C be any category and F : C → C an endofunctor. An F - algebra is (X, δ) where δ : F X → X. An F -algebra homomorphism f : (X, δ) → (Y, ϵ) is a morphism f : X → Y such that the following square commutes:

[figure: X; Y; f; F X; F Y; F f; δ; ϵ]

It is again clear that, with the composition and identities of C, that one gets a category which we denote by C^{F}. Notice that if (F, μ, η) is a monad then CF is a full subcategory of C^{F}.

We now represent a signature Σ by its “generating functor” F_{Σ} : Set → Set namely

F_{Σ}X = Σ_{0} + (Σ_{1} × X) + (Σ_{2} × X^{2}) + ⋯ + (Σ_{n} × X^{n}) + ⋯  (20)

where + is the coproduct (disjoint union), × is cartesian product and X^{k} is cartesian power, so that F_{Σ} is a functor. The functor F_{Σ} is called a polynomial functor in Set. Because of the the commutativity and associativity isomorphisms for cartesian product and the natural isomorphisms A × (B + C) ≅ A × B + A × C, any functor that can be constructed from identity functors by finite use of + and × is isomorphic to a polynomial functor.

It is obvious that Set^{F_{Σ}} is the category of Σ-algebras. We now define a monad F_{Σ}^{@} = (F_{Σ}^{@}, μ, η) with Set^{F_{Σ}^{@}} ≅ Set^{F_{Σ}} as follows. F_{Σ}^{@}X is defined as the least solution of the recursive equation

F_{Σ}^{@}X = X + F_{Σ}F_{Σ}^{@}X  (21)

Set η_{X} : X → F_{Σ}^{@}X to be the first coproduct injection. In the diagram below, there exists unique α^{#}, given α.

[figure: X; X + F_{Σ}F_{Σ}^{@}X; η_{X}; F_{Σ}F_{Σ}^{@}X; in_{2}; F_{Σ}F_{Σ}^{@}Y; in_{2}; F_{Σ}^{@}Y; α^{#}; F_{Σ}α^{#}; α]  (22)

To see this, observe that the two diagrams amount to the inductive definition

α^{#}(x) = α(x)
α^{#}(ω(t_{1}, …, t_{n})) = ω(α^{#}(t_{1}), …, α^{#}(t_{n}))

Replacing F_{Σ}^{@}Y with any F_{Σ}-algebra shows that (F_{Σ}^{@}X, in_{2}) is the free F_{Σ}-algebra generated by X and that F_{Σ}^{@} is just the monad induced by Huber’s theorem from the functor Set^{F_{Σ}} → Set and its left adjoint. This functor is then monadic by Beck’s monadicity theorem, so that Set^{F_{Σ}^{@}} is isomorphic over Set to Set^{F_{Σ}}[4]. Note that the fixed point equation in (21) is the familiar construction of the set of Σ-terms with variables in X from universal algebra, namely that each variable is a term and that for ω ∈ Σ_{n}, if τ_{1}, …, τ_{n} are terms then so is ω(τ_{1}, …, τ_{n}).

The recursive property in (21) will be used to construct a canonical distributive law of M over F_{Σ}^{@} where M is a commutative monad. These monads are the subject of the next subsection.

4.2. Commutative Monads. Commutative monads were defined in closed categories by Kock [15]. In this section we will consider commutative monads in Set. In the sequel paper [23] the definition will be generalized to closed categories and there will be new examples even in Set. In this subsection, we fix a monad M = (M, ν, ρ) in Set.

4.2.1. Definition. A function g : MX_{1} × ⋯ × MX_{n} → MY with n ≥ 1 is said to be a multihomomorphism (or mh for short) if for fixed ω_{j} ∈ MX_{j} for all j ≠ i, the resulting function

λω.g(ω_{1}, …, ω_{i−1}, ω, ω_{i+1}, …, ω_{n}) : MX_{i} → MY

is an M-homomorphism. When n = 2, we say g is a bihomomorphism. Given a function f : X_{1} × ⋯ × X_{n} → Y, a multihomomorphic extension (mh-extension) of f is a multihomomorphism f̂ such that the following square commutes

[figure: Y; MY; ρ_{Y}; X_{1} × ⋯ × X_{n}; MX_{1} × ⋯ × MX_{n}; ρ_{X_{1}} × ⋯ × ρ_{Xn}; f; f̂]

4.2.2. Lemma. If f̂, g are mh-extensions of f : X_{1} × ⋯ × X_{n} → Y then f̂ = g.

Proof. For n = 1, f̂ = Mf is the unique M-homomorphic extension of X ⟶^{f} Y ⟶^{ρ_{Y}} MY. Proceeding inductively, for fixed x ∈ X_{n+1}, f̂(–, x), g(–, x) are mh-extensions of f(–, x) : X_{1} × ⋯ × X_{n} → Y so that f̂(–, x) = g(–, x) by the induction hypothesis. Fix ω_{i} ∈ MX_{i} for i = 1 ⋯ n. As f̂(ω_{1}, …, ω_{n}, –) and g(ω_{1}, …, ω_{n}, –) are M-homomorphisms agreeing on the generators, they are equal. □

If C is any category and if H = (H, μ, η) is a monad in C, H × H is a monad in C × C with functor (A, B) ↦ (HA, HB), similarly for maps, and with unit (η_{A}, η_{B}), multiplication (μ_{A}, μ_{B}) and extension (α^{#}, β^{#}). The details are trivial. To avoid confusion with the earlier product monad in C we shall denote this monad as (H, H).

If (Y, θ) is an M-algebra and X is a set, the cartesian power (Y, θ)^{X} is an algebra as well. See [20, 22] for details.

Each ω ∈ Mn induces an n-ary operation δ_{ω} : X^{n} → X on each M-algebra (X, ξ) by

δ_{ω}(n ⟶^{f} X) = (Mn ⟶^{Mf} MX ⟶^{ξ} X)(ω)

4.2.3. Notation. When the identity map id_{X_{1}×···×X_{n}} : X_{1} ×⋯×X_{n} → X_{1} ×⋯×X_{n} has an mh extension MX_{1} × ⋯ × MX_{n} → M(X_{1} × ⋯ × X_{n}), we will denote the extension by Γ_{X_{1}×···×X_{n}}^{n}. In the case of n = 2, we may drop the superscript.

4.2.4. Theorem. The following conditions on a monad M in Set are equivalent. If any, and hence all, hold we say M is commutative.

1. Each function f : X × Y → Z has a bihomomorphic extension.

2. Each function f : X_{1} × ⋯ × X_{n} → Y has a unique multihomomorphic extension.

3. The product bifunctor × : Set×Set → Set has a Kleisli lift \overline{×} : (Set×Set)_{(M,M)} → Set_{M}. Moreover, if λ : MX × MY → M(X × Y) classifies \overline{×}, the map ψ : (MX)^{A} × (MY)^{B} → (M(X × Y))^{A×B} defined by ψ(α, β) = λ_{(X,Y)} (α × β) is a bihomomorphism with respect to the cartesian power M-algebra structures.

4. If (X, ξ), (Y, θ) are M-algebras, the set of M-homomorphisms (X, ξ) → (Y, θ) is an M-subalgebra of the cartesian power (Y, θ)^{X}.

5. Each M-operation δ_{ω} : (X, ξ)^{n} → (X, ξ) is an M-homomorphism, where (X, ξ)^{n} has the cartesian power algebra structure.

Proof. (1 ⇔ 2). That (2) ⇒ (1) is trivial. For (1) ⇒ (2), uniqueness is immediate from Lemma 4.2.2. For existence, first claim that the mh extension Γ_{X_{1}×···×X_{n}}^{n} exists. For n = 1, use the identity map. The case n = 2 is given. Proceeding inductively, define Γ_{X_{1}···X_{n}}^{n+1} = Γ_{X_{1}×···×X_{n},X_{n+1}}^{2} ∘ Γ_{X_{1}···X_{n}}^{n} × 1. Then Γ^{2} is given mh and Γ^{n} is mh by the induction hypothesis. Fix ω_{i} ∈ MX_{i}. Then Γ^{n+1}(ω_{1}, …, ω_{n}, ω) = Γ^{2}(Γ^{n}(ω_{1}, …, ω_{n}), ω) is homomorphic in ω because Γ^{2} is a bihomomorphism. For 1 ≤ i ≤ n,

Γ^{n+1}(ω_{1}, …, ω_{i−1}, –, ω_{i+1}, …, ω_{n+1}) = Γ^{2}(–, ω_{n+1}) ∘ Γ^{n}(ω_{1}, …, ω_{i−1}, –, ω_{i+1}, …, ω_{n})

is the composition of two homomorphisms and so is again one. This shows, so far, that Γ^{n} is mh for all n. We next show that Γ^{n} extends id. For n = 1 this is clear and for n = 2 this is given. Proceeding inductively, we have

Γ^{n+1} (ρ_{X_{1}} × ⋯ × ρ_{X_{n+1}}) = Γ^{2} (Γ^{n} × 1) (ρ_{X_{1}} × ⋯ × ρ_{X_{n+1}})
= Γ^{2}( Γ^{n}(ρ_{X_{1}} × ⋯ × ρ_{X_{n}}), ρ_{X_{n+1}})
= Γ^{2}(ρ_{X_{1}×···×X_{n}}, ρ_{X_{n+1}}) (induction hypothesis)
= ρ_{X_{1}×···×X_{n+1}}

Now consider f : X_{1} × ⋯ × X_{n} → Y and define f̂: MX_{1} × ⋯ × MX_{n} → MY by

f̂ = MX_{1} × ⋯ × MX_{n} ⟶^{Γ_{X_{1}···Xn}^{n}} M(X_{1} × ⋯ × X_{n}) ⟶^{Mf} MY  (23)

As Mf is a homomorphism and Γ^{n} is mh, f̂ is mh. Moreover, f̂ extends f because

f̂(ρ_{X_{1}} × ⋯ × ρ_{X_{n}}) = (Mf) Γ^{n} (ρ_{X_{1}} × ⋯ × ρ_{X_{n}})
= (Mf) ρ_{X_{1}×···×X_{n}} (Definition of Γ^{n})
= ρ_{Y} f (ρ is natural)

(1 ⇒ 3) We show that Γ_{XY}^{2} : MX×MY → M(X×Y) as above classifies a Kleisli lift of the product bifunctor × : Set × Set → Set. In (2.2.2, 2.2.6), H = (M, M), F = − × − and K = M. (\overline{F} A) holds by the definition of Γ^{2}. For (\overline{F} #), given α : W → MY,

β : X → MZ, γ = W × X ⟶^{α×β} MY × MZ ⟶^{Γ^{2}} M(Y × Z), we must show that the

following square commutes:

[figure: M(W × X); M(Y × Z); γ^{#}; MW × MX; MY × MZ; α^{#} × β^{#}; Γ_{W X}^{2}; Γ_{Y Z}^{2}]

As α^{#}, β^{#} and γ^{#} are homomorphisms and Γ^{2} is a bihomomorphism, both paths are bihomomorphisms so, by Lemma 4.2.2, we need only check equality on the generators. Indeed,

γ^{#} Γ^{2} (ρ_{W} × ρ_{X}) = γ^{#} ρ_{W ×X} (definition of Γ^{2})
= γ = Γ^{2} (α × β) = Γ^{2} ( (α^{#}ρ_{W}) × (β^{#}ρ_{X}) )
= Γ^{2} (α^{#} × β^{#}) (ρ_{W} × ρ_{X})

Thus Γ^{2} classifies a Kleisli lift of the product bifunctor. Notice that this lift (Set ×

Set)_{(M,M)} → Set_{M} maps (A ⟶^{α} MX, B ⟶^{β} MY) to γ = A × B ⟶^{α×β} MX × MY ⟶^{Γ^{2}}

M(X × Y) which is the map ψ in (3). For a ∈ A, b ∈ B, β ∈ MY^{B} we have, by the definition of ψ, that the following square commutes:

[figure: MX; M(X × Y); Γ^{2}(–, βb); MX^{A}; M(X × Y)^{A×B}; ψ(–, β); pr_{a}; pr_{(a,b)}]

As MX^{A} has the product algebra structure, pr_{a} is a homomorphism. Γ^{2}(–, βb) is a homomorphism since Γ^{2} is a bihomomorphism. Thus ψ is a homomorphism in its second variable. The proof for the first variable is similar.

(3 ⇒ 1) Let λ_{XY} : MX × MY → M(X × Y) classify a Kleisli lift of the product bifunctor such that the map ψ : MX^{A} × MY^{B} → M(X × Y)^{A×B} given by ψ(α, β) = A × B ⟶^{α×β} MX × MY ⟶^{λ} M(X × Y) is a bihomomorphism with respect to the cartesian power algebra structures. Letting A, B be singleton sets, we see that λ_{XY} is itself a bihomomorphism. Moreover, by axiom (\overline{F} A), λ_{XY} extends ρ_{X} × ρ_{Y}. Given arbitrary f : X × Y → Z, define f̂ = (Mf) λ_{XY}. Then f̂ is bihomomorphic since λ_{XY} is and Mf is a homomorphism. Further, f̂ extends f since

f̂(ρ_{X} × ρ_{Y}) = (Mf) λ_{XY} (ρ_{X} × ρ_{Y})
= (Mf) ρ_{X×Y} = ρ_{Y} f (ρ is natural)

The equivalence of (1, 2) with (4) and (5) is Linton’s theorem [17]. (We note that while (1,2) were not put into the statement of his theorem, they are prominent in the proof). □

We now explore some examples and basic properties of commutative monads in Set. Let R be a semiring with 1, that is, (R, +, 0) is an abelian monoid and (R, ·, 1) is

a monoid satisfying the laws (x + y)z = xz + yz, z(x + y) = zx + zy, 0x = 0 = x0. An R-module is an abelian monoid (X, +, 0) on which R acts satisfying the usual laws for r, s ∈ R, x, y ∈ X, namely (r + s)x = rx + sx, r(x + y) = rx + ry, (rs)x = r(sx), 1x = x, 0x = 0. The category of R-modules is equationally definable with finitary operations (think of elements of R as indexing unary operations) and hence is monadic over Set.

4.2.5. Example. For R a semiring, the monad M_{R} = (M_{R}, ν, ρ) for R-modules, is constructed by Huber’s theorem as follows. M_{R}X is the free module ⊕_{X}R generated by X whose elements are all formal sums ∑_{x} r_{x}x with r_{x} ∈ R, r_{x} = 0 for all but finitely many x ∈ X. We have ρ_{X}x = ∑_{y} δ_{y}^{x}y with δ_{y}^{x} the Kronecker delta, that is, taking the value 0 ∈ R for y ≠ x but with value 1 ∈ R when y = x. Given α : X → M_{R}Y, α^{#}(∑ r_{x}x) = ∑ r(x)α(x) is the unique R-linear extension of α.

To explain the definition of α^{#}, M_{R}Y is a module with abelian group ∑ r_{y}y + ∑ s_{y}y = ∑(r_{y} + s_{y})y and action r ∑ r_{y}y = ∑(rr_{y})y. From a data type perspective, ∑_{x} r_{x}x is a generalized finite bag with r_{x} the “multiplicity” of element x. Notice that composition in the Kleisli category of M_{R} is matrix multiplication.

4.2.6. Proposition. If R is a commutative semiring with 1 then M_{R} is commutative.

Proof. f : X × Y → Z has unique bihomomorphic extension f̂ : MX × MY → MZ given by

f̂(Σr_{x}x, Σs_{y}y) = ∑ r_{x}s_{y}f(x, y)
□

In this context, it is standard to call multihomomorphisms multilinear maps. The reader should provide the proof details to see where the commutativity of the semiring is used.

4.2.7. Example. If R = IN = {0, 1, 2, …} with the usual addition and multiplication, M_{R} -algebras are abelian monoids and M_{R}X is the set of all finite bags ∑ n_{x}x with n_{x} the number of occurrences of x in the bag.

4.2.8. Example. “Fuzzy set theory” uses the real unit interval R = [0, 1] with supremum as addition and infimum as multiplication.

The Boolean semiring is 2 = {0, 1} with 1 + 1 = 0. A 2-module is then an abelian monoid for which x + x = (1 + 1)x = 1x = x, that is, a semilattice. We then have

4.2.9. Example. For R the Boolean semiring, M_{R} is the finite power set monad P_{0}, a submonad of P. This monad is commutative. The formula of Proposition 4.2.6 gives

f̂({x_{1}, …, x_{m}}, {y_{1}, …, y_{n}}) = {f(x_{i}, y_{j}) : i = 1, …, m, j = 1, …, n}

4.2.10. Example. Consider the monad MX = X×C, where C is a monoid, η_{X}x = (x, 1), and for α : X → Y × C, α^{#}(x, d) = (y, cd) if αx = (y, c). This monad is commutative when C is a commutative monoid. In that case,

f̂((x_{1}, e_{1}), …, (x_{n}, e_{n})) = (f(x_{1}, …, x_{n}), e_{1} + ⋯ + e_{n})

4.2.11. Example. For G a non-empty set, the monad MX = X + G of Example 2.4.6 is commutative if and only if G has one element.

To see this, use Theorem 4.2.4 (4). An M-algebra is a pair (X, (∗_{g} : g ∈ G)) with each ∗_{g} ∈ X and a morphism is a function mapping ∗_{g} to ∗_{g} for all g. For a cartesian power algebra (Y, (∗_{g})))^{X}, the constant ∗_{g} is the function X → Y which is constantly ∗_{g}. A subalgebra is any subset containing all these constant functions. On the other hand, if both G and Y have more than one element and different ∗_{g} exist in Y, no homomorphism is constant so the set of homomorphisms cannot be a subalgebra. When G = {∗}, the unique multihomomorphic extension f̂: (X_{1} + {∗}) × ⋯ × (X_{n} + {∗}) → (Y + {∗}) maps (x_{1}, …, x_{n}) to f(x_{1}, …, x_{n}) if no x_{i} = ∗ and maps to ∗ otherwise.

4.2.12. Proposition. Any cartesian product of commutative monads is a commutative monad. □

Pursuant to our next result, we remind the reader that for monads H of Set (see [20, 22]) quotient monads of H correspond bijectively to full subcategories of H-algebras which are closed under products, subalgebras and quotient algebras.

4.2.13. Proposition. Any quotient of a commutative monad is commutative.

Proof. This is clear from Theorem 4.2.4 (4) since products and subalgebras in the corresponding full subcategory are the same as in the ambient category. □

4.2.14. Proposition. Any submonad of a commutative monad is commutative.

Proof. Let ι : M → H be a submonad of the commutative monad H = (H, μ, η). Fix X, Y and let Γ_{XY} : HX × HY → H(X × Y) be the bihomomorphism extending id_{X×Y}. Noting that every H-homomorphism is also an M-homomorphism via the forgetful functor, it suffices to find a fill-in

[figure: HX × HY; H(X × Y); Γ_{XY}; MX × MY; M(X × Y); Γ′_{XY}; ι_{X} × ι_{Y}; ι_{X×Y}]

for then Γ′_{XY} is an M-bihomomorphism by Lemma 2.3.5 and each f : X × Y → Z

then has M-bihomomorphic extension MX × MY ⟶^{Γ′_{XY}} M(X × Y) ⟶^{Mf} MZ. For x ∈ X write in_{x} : Y → X × Y, y ↦ (x, y). Then Γ_{XY} (x, -) = H(in_{x}) maps MY into MZ as ι : M → H is natural, defining Γ′_{XY} (x, -) : MX → MZ. With respect to the product algebra structure, let γ : MX → MZ^{MY} be the M-homomorphism extending x ↦ Γ′_{XY} (x, -) and write Γ′_{XY} (ω, ζ) = (γζ)(ω). By the uniqueness of homomorphic extensions, the square above commutes for each fixed ζ ∈ MY and hence commutes. □

4.2.15. Example. Consider the exponential monad MX = X^{A}, the cartesian power of the identity monad. By Proposition 4.2.12, this is a commutative monad. For ψ : X_{1} × ⋯ × X_{n} → Y, ψ̂ : X_{1}^{A} × ⋯ × X_{n}^{A} → Y^{A} is defined by (ψ̂(f_{1}, …, f_{n}))a = ψ(f_{1}a, … f_{n}a).

4.2.16. Example. A special case of the previous example is the rectangular bands monad R = (R, ν, ρ) of Example 2.1.7. For f : X_{1}×⋯×X_{n} → Y,Here f̂((x_{1}, y_{1}), …, (x_{n}, y_{n})) = (f(x_{1}, …, x_{n}), f(y_{1}, …, y_{n})).

4.2.17. Example. The list monad L is not a commutative monad.

For consider an arbitrary map f : A × B → C. Suppose there is a multihomomorphic extension f̂ : LA × LB → LC. In particular, λw.f̂([a, b], w) : LB → LC and λw.f̂(w, [x, y]) : LA → LC are list homomorphisms. Now f̂([a, b], [x, y]) = λw.f̂([a, b], w) applied to [x, y] which equals [f(a, x), f(b, x), f(a, y), f(b, y)] but also f̂([a, b], [x, y]) = λw.f̂(w, [x, y])([a, b]) which equals [f(a, x), f(a, y), f(b, x), f(b, y)]. Thus f(a, y) = f(b, x) for arbitrary a, b, x, y. But this will only work if f is a constant function.

4.2.18. Example. Let M be the state monad of Example 2.1.8 and recall the notations used there. Fix sets A, B and suppose that Γ = Γ_{AB}^{2} : MA × MB → M(A × B) is a bihomomorphism with Γ ∘ (ρ_{A} × ρ_{B}) = ρ_{A×B}, that is, Γ([â, id], [b̂, id]) = [â, b̂, id]. We shall show that this leads to a contradiction when S has at least two elements and so we conclude that the state monad is not commutative.

To see this, for fixed a ∈ A consider α : B → (A × B × S)^{S}, α(b) = [â, b̂, id]. Then Γ([â, id], –) = α^{#} since both are homomorphisms which restrict to α on the generators. Thus for g : S → B, u : S → S,

Γ([â, id], [g, u]) = α^{#}([g, u]) = λs . < α(gs), us >

= λs . < [â, ĝs, id], us > = λs .[a, gs, us]
= [â, g, u]

Thus if β : A → (A × B × S)^{S}, β(a) = [â, g, u], Γ(–, [g, u]) = β^{#}. Hence

Γ([f, t], [g, u]) = β^{#}([f, t]) = λs . < β(fs), ts >
= λs . < [f̂s, g, u], ts > = [f, g ∘ t, u ∘ t]

forces a general formula for Γ. But we could perform this construction by fixing variables in the other order. For fixed b ∈ B define γ : A → (A × B × S)^{S}, γ(a) = [â, b̂, id] and compute

Γ([f, t], [b̂, id]) = γ^{#}([f, t]) = [f, b̂, t]

so that, for δ : B → (A × B × S)^{S}, δ(b) = [f, b̂, t],

Γ([f, t], [g, u]); = δ^{#}([g, u]) = [f ∘ u, g, t ∘ u]

These two formulas are not equal if S has at least two elements: if t, u are different constant functions, t ∘ u ≠ u ∘ t.

4.2.19. Lemma. For commutative M, each Γ^{n} is a natural transformation.

Proof. For n = 1, Γ^{1} = id and the result is clear. For n = 2, we need to show that for functions f : A → B and g : C → D, Γ_{B,D}^{2}(Mf × Mg) = M(f × g)Γ_{A,C}^{2}. As both maps are bihomomorphisms, it is enough to check equality on the generators ρ_{A} × ρ_{C}. M(f × g)Γ_{A,C}(ρ_{A} × ρ_{C}) = M(f × g)ρ_{A×C} = ρ_{B×D}(f × g) = Γ_{B,D}(ρ_{B} × ρ_{D})(f × g) = Γ_{B,D}(Mf × Mg)(ρ_{A} × ρ_{C}). The result for general n is now obvious from the inductive definition. □

We are now ready to construct a class of recursively-defined distributive laws.

4.2.20. Theorem. Let Σ be a signature, inducing polynomial functor F = F_{Σ} and monad F^{@} = (F^{@}, μ, η). Let (F^{@}X, π) be the free Σ-algebra generated by X, π_{ω} : (F^{@}X)^{n} → F^{@}X for ω ∈ Σ_{n}. Let M be a commutative monad and let π̂_{ω} : (MF^{@}X)^{n} → MF X be the unique multihomomorphic extension of π_{ω}. Define λ recursively, by means of the free Σ-algebra structure, by

Then λ is a distributive law of M over F^{@}.

[figure: MX; F^{@}MX; η_{MX}; F F^{@}MX; in_{2}; F MF^{@}X; π̂; MF^{@}X; λ_{X}; F λ_{X}; Mη_{X}]

Proof. Noting that Set^{F^{@}} ≅ Set^{F}, define an algebra lift M^{⋆} : Set^{F} → Set^{F} as follows. On objects, M^{⋆}(X, δ) = (MX, δ̂) with δ̂_{ω} : (MX)^{n} → MX the unique multihomomorphic extension of δ_{w} : X^{n} → X for ω ∈ Σ_{n}, n ≥ 1. For ω ∈ Σ_{0}, define δ̂_{ω} = ρ_{X}(δ_{ω}) ∈ MX. To show that M^{⋆} is functorial, let f : (X, δ) → (Y, ϵ) be a Σ-homomorphism; we must show that Mf : (MX, δ̂) → (MY, ϵ̂) also is, that is, that the following square commutes:

[figure: MX; MY; Mf; (MX)^{n}; (MY)^{n}; (Mf)^{n}; δ̂_{ω}; ϵ̂_{ω}]

For n = 0 this is immediate from the naturality of ρ. For n ≥ 1, argue as follows. Mf : (MX, ν_{X}) → (MY, ν_{Y}) is an M-homomorphism by the naturality of ν. Both paths in the square are multihomomorphisms, so we need only check agreement on the generators (ρ_{X})^{n} : X^{n} → (MX)^{n}. To this end, we have

ϵ̂_{ω}(Mf)^{n}(ρ_{X})^{n} = ϵ̂_{ω}(ρ_{Y})^{n}f^{n} (ρ natural)
= ρ_{Y} ϵ_{ω} f^{n} (ϵ̂ extends ϵ)
= ρ_{Y} f δ_{ω} (f Σ-homomorphism)
= (Mf)δ̂_{ω}(ρ_{X})^{n} (δ̂ extends δ)

as desired. Considering (11) and (14), the natural transformation λ that classifies the lifting M^{⋆} is the unique Σ-homomorphism λ_{X} : (F^{@}MX, μ_{MX}) → M^{⋆}(F^{@}X, π) which extends Mη_{X}. But M^{⋆}(F^{@}X, π) = (MF^{@}X, π̂) by definition. The λ recursively specified in the statement of the theorem is precisely the unique Σ-homomorphism extending Mη_{X}, so is the λ corresponding to M^{⋆}. To complete the proof, we show that the monad M lifts to Set^{F}. By the definition of δ̂, the left square below commutes and this says, precisely, that ρ_{X} : (X, δ) → M^{⋆}(X, δ) is a Σ-homomorphism. Let (X, δ) be an F -algebra, (MMX, δ̃) = M^{⋆}(MX, δ̂) where (MX, δ̂) = M^{⋆}(X, δ). To show ν_{X} : (MMX, δ̃) → (MX, δ̂) is a Σ-homomorphism, we must show the right square below commutes.

[figure: X; MX; ρ_{X}; X^{n}; (MX)^{n}; (ρ_{X})^{n}; δ_{ω}; δ̂_{ω}; MMX; MX; ν_{X}; (MMX)^{n}; (MX)^{n}; (ν_{X})^{n}; δ̃; δ̂]

It amounts to one of the monad laws that ν_{X} : (MMX, ν_{MX}) → (MX, ν_{X}) is an M-homomorphism for any monad M. Hence both paths in the square are multihomomorphisms so we need only check commutativity restricted to the generators (ρ_{MX})^{n}. We have δ̂_{ω}(ν_{X})^{n}(ρ_{MX})^{n} = δ̂_{ω}(ν_{X} ρ_{MX})^{n} = δ̂_{ω} = ν_{X} ρ_{MX} δ̂_{ω} = ν_{X} δ̃_{ω} (ρ_{MX})^{n} and the proof is complete. □

4.3. Linear Equations. Let Σ_{0} = {1}, Σ_{2} = {·}, Σ_{n} = ∅ if 0 ≠ n ≠ 2. Then writing x · y as xy, a commutative monoid is a Σ-algebra satisfying the equations

x(yz) = (xy)z
x1 = x = 1x  (24)
xy = yx

and a semilattice is a commutative monoid also satisfying

xx = x  (25)

Given a full subcategory V of Set^{F_{Σ}}, V consists of all Σ-algebras satisfying a given set of equations if and only if V is closed under products, subalgebras and quotient algebras if and only if there exists a monad map with epic components τ : F_{Σ}^{@} → S with V corresponding to the full subcategory of Σ-algebras of Lemma 3.4.1. In this case, V is called a variety of Σ-algebras. Given sets of Σ-equations E, F, respectively inducing varieties W, V, then E ⊂ F ⇔ V ⊂ W and there is a commutative triangle of monad maps with epic components

[figure: F_{Σ}^{@}; S_{W}; τ_{W}; τ_{V}; S_{V}; τ_{WV}]

Monad maps of type τ_{WV} arise naturally in data type situations. Consider the list monad L, a quotient of F_{Σ}^{@} with Σ_{0} = {1}, Σ_{2} = {·} corresponding to the equations

x(yz) = (xy)z  (26)
x1 = x = 1x

Instead of thinking of the equations as defining monoids, consider the following. F_{Σ}^{@}X consists of terms built by the rules

• 1 is a term

• If x ∈ X, x is a term

• If p, q are terms then p · q is a term.

Two terms are equivalent if one can be transformed into the other by using the three equations, and this happens if and only if both are 1 or else both have the same list of values when all instances of 1 are deleted. In this way, lists represent the equivalence classes. Quotients of L lead to further data types. Imposing the further equation xy = yx makes the order of listing unimportant, giving rise to finite bags. To get finite subsets, eliminate repetition by imposing xx = x.

Given a commutative monad M, a signature Σ with canonical distributive law λ : F_{Σ}^{@}M → MF_{Σ}^{@} as in Theorem 4.2.20 and a set E of Σ-equations inducing monad quotient τ : F_{Σ}^{@} → S, what conditions on E will guarantee that Corollary 3.4.2 will apply to provide a quotient distributive law λ′ : SM → MS? The main theorem of this section is that linear equations do this. The definition is as follows.

4.3.1. Definition. A Σ-equation is linear if the same set of variables occurs without repetition on both sides.

All of the equations of (24) are linear (in “x1 = x”, 1 ∈ Σ_{0} is not a variable —x is the only variable). But (25) is not linear because x is repeated. The equation xx^{−1} = 1 of group theory is not linear because x is repeated and because x appears on only one side.

Before continuing with the theory, it is illustrative to consider an example.

4.3.2. Example. Let M = P_{0} be the finite power set monad and let Σ_{2} = {·}. If m : X ×X → X is a Σ-algebra, consider the unique bihomomorphic lift m̂ : P_{0}X ×P_{0}X → P_{0}X. Writing xy for m(x, y), Example 4.2.9 gives m̂(A, B) = AB = {ab : a ∈ A, b ∈ B}. If X is a semigroup, so is P_{0}X because (AB)C = {abc : a ∈ A, b ∈ B, c ∈ C} = A(BC). On the other hand, P_{0}X need not satisfy x^{2} = x if X does because A^{2} is {ab : a, b ∈ A} rather than {a^{2} : a ∈ A}. This illustrates why linear equations lift to M whereas nonlinear ones need not.

4.3.3. Lemma. Let Σ be a signature, let E be a set of linear Σ-equations and let (X, δ) be a Σ-algebra which satisfies all the equations in E. Then for any commutative monad M, the Σ-algebra (MX, δ̂) (as in the proof of Theorem 4.2.20) also satisfies all of the equations in E.

Proof. This is precisely [21, Metatheorem 6.10]. □

We can now establish the main result of this section.

4.3.4. Theorem. Let Σ be a signature and let E be a set of linear Σ-equations corresponding to the quotient monad map τ : F_{Σ}^{@} → S. Write S = (S, μ′, η′). Let M be a commutative monad and let (SX, μ′_{X}) have Σ-algebra structure (SX, π_{X}) inducing the Σ-algebra (MSX, π̂_{X}). Writing F for F_{Σ}, define ψ_{X} recursively by means of the free Σ-algebra structure, by

[figure: MX; F^{@}MX; in_{1}; Mη′_{X}; MSX; ψ_{X}; F MSX; π̂_{X}; F F^{@}MX; in_{2}; F ψ_{X}]  (27)

Then ψ respects τ-equivalence classes, that is, there exists a factorization

[figure: F^{@}MX; SMX; τ_{MX}; MSX; ψ_{X}; λ′_{X}]

and λ′ is a distributive law of M over S.

Proof. Let λ : F^{@}M → MF^{@} be the distributive law of Theorem 4.2.20, so that the induced algebra lift is M^{⋆}(Y, ϵ) = (MY, ϵ̂) with ϵ̂_{ω} the unique multihomorphic extension of ϵ_{ω}. By Lemma 4.3.3, M^{⋆} maps algebras satisfying E to algebras satisfying E so, by the quotient theorem 3.4.2 there exists a factorization

[figure: MF^{@}X; MSX; Mτ_{X}; F^{@}MX; SMX; τ_{MX}; λ_{X}; λ′_{X}]

with λ′ a distributive law of M over S. Now λ′_{X} : (SMX, π_{MX}) → (MSX, π̂) is the unique S-homomorphic extension of Mη′_{X} as τ_{MX} is a Σ-homomorphism and as

λ′_{X} τ_{MX} η_{MX} = λ′_{X} η′_{MX} = Mη′_{X}

where the last equality is (DL C). Thus λ′_{X} τ_{MX} = ψ_{X} because both satisfy the same recursive specification. □

5. Composing Recursive Data Types

We conclude the paper by cataloging examples of distributive laws involving two familiar recursive data type monads.

5.1. Lists and Trees.

5.1.1. Definition. The data type of binary trees V X with leaves in X can be recursively defined by

V X = 1 + X + (V X × V X)

where the unique element of 1 is the empty tree E. Clearly, V is the monad F^{@} corresponding to the signature Σ_{0} = {E}, Σ_{2} = {·} and all other Σ_{n} = ∅, and we denote this monad as V = (V, μ′, η′). V-algebras are sets equipped with a binary operation and a constant.

Let M = (M, ν, ρ) be a commutative monad in Set. By Theorem 4.2.20 there is a distributive law of λ : V M → MV of M over V defined recursively by the diagram

[figure: MX; V MX; η′_{MX}; Mη′_{X}; MV X; λ_{X}][figure: MV X × MV X; π̂_{X}; V MX × V MX; in_{2}; λ_{X} × λ_{X}]

where π̂ is the bihomomorphic extension of the obvious inclusion π : V X × V X → V X.

5.1.2. Example. As seen earlier for the finite case 4.2.9, the power set monad P is a commutative monad. The distributive law λ : V P A → P V A takes a tree of subsets to a subset of trees. An algebra structure of the composite monad P V on A consists of a complete sup-semilattice (A, ∨) and a binary operation with identity (A, ∗, e) satisfying a composite law similar to that of Example 2.4.8.

For instance, if we denote a trivial tree (i.e. a leaf) with value x by Lx and a tree consisting of left and right subtrees v1 and v2 by N(v1, v2), then λ(N(L{a, b}, L{c, d})) = {N(La, Lc), N(La, Ld), N(Lb, Lc), N(Lb, Ld)}.

Many other examples composing commutative monads with V exist. By previous work, these compositions also exist for linear quotients of V. To avoid repetition, we only detail these composites for a familiar V -quotient monad, the list monad.

Let M = (M, ν, ρ) be a commutative monad in Set. By Theorem 4.2.20 there is a recursive ψ : V M → ML and a distributive law λ : LM → ML of M over L defined by the diagrams

[figure: MX; V MX; η′_{MX}; Mη_{X}; MLX; ψ_{X}; MLX × MLX; ˆ+ +; V MX × V MX; in_{2}; ψ_{X} × ψ_{X}; V MX; LMX; τ_{MX}; ψ_{X}; MLX; λ_{X}]

where ˆ+ + is the bihomomorphic extension of the list concatenation map + + : LX × LX → LX. Let’s look at some examples for specific M.

5.1.3. Example. For the commutative monad M_{R} of Example 4.2.5,

λ_{X} [∑ r_{x}^{1}x, …, ∑ r_{x}^{n}x] = ∑_{x_{1}} ⋯ ∑_{x_{n}} r_{x_{1}}^{1} ⋯ r_{x_{n}}^{n} [x_{1}, …, x_{n}]

Example 2.4.5 is recovered if R = Z Z.

5.1.4. Example. For the monad of Example 4.2.10 with C a commutative monoid,

λ_{X}[(x_{1}, e_{1}), …, (x_{n}, e_{n})] = ( [x_{1}, …, x_{n}], e_{1} ⋯ e_{n})

5.1.5. Example. For the monad MX = X + {∗} of Example 4.2.11, λ_{X}[x_{1}, …, x_{n}] is equal to [x_{1}, …, x_{n}] if no x_{i} = ∗, and is otherwise ∗.

5.1.6. Example. For the exponential monad MX = X^{A} of Example 4.2.15, for f_{i} : A → X,

λ_{X}[f_{1}, …, f_{n}] (a) = [f_{1}a, …, f_{n}a]

5.1.7. Example. For the rectangular band monad of Example 4.2.16, λ : [(x_{1}, y_{1}), …, (x_{n}, y_{n})] = ([x_{1}, …, x_{n}], [y_{1}, …, y_{n}]) is exactly the usual unzip map for lists.

5.1.8. Example. The bags monad B = (B, μ, η) is the quotient monad τ : L → B obtained by imposing the further linear equation xy = yx to L. All the previous examples that composed with lists also compose with B.

Does the list monad compose with itself? When M and L are both the list monad, M is no longer a commutative monad. Consequently, we can no longer appeal to Theorem 4.3.4. The question is subtle and we begin by showing an example where composition fails.

5.1.9. Example. Define λ′_{X} : LLX → LLX as follows.

λ′_{X} [ ] = [ ]
λ′_{X} [ [x_{1}, …, x_{n}] ] = [ [x_{1}], …, [x_{n}] ]
λ′_{X} [ [x_{1}, …, x_{m}], [y_{1}, …, y_{n}] ] = [ [x_{1}, y_{1}], …, [x_{1}, y_{n}], [x_{2}, y_{1}], …, [x_{m}, y_{n−1}], [x_{m}, y_{n}] ]
⋯

so that, e.g.

λ′_{X}[ [a, b], [c, d], [e, f] ] = [ [a, c, e], [a, c, f], [a, d, e], [a, d, f], [b, c, e], [b, c, f], [b, d, e], [b, d, f] ]

Similarly, fixing rightmost variables first instead of leftmost, there is λ′′ : LL → LL so that, e.g.,

λ′′_{X}[ [a, b], [c, d], [e, f] ] = [ [a, c, e], [b, c, e], [a, d, e], [b, d, e], [a, c, f], [b, c, f], [a, d, f], [b, d, f] ]

Both λ′ and λ′′ are natural transformations satisfying (DL A), (DL C) and (DL D). The claim in [14] that these are distributive laws is incorrect, however. To see that (DL B) fails observe that the two paths in (DL B) give rise to different values on the list [ [ [a, b], [c, d] ] , [ [e, f], [g, h] ] ] ∈ LLL{a, b, c, d, e, f, g, h}, where one path begins with [ [a, e], [a, f], [b, e], …] and the other path beginning [ [a, e], [a, f], [a, g], …].

The existence of a distributive law of L over itself remains an open question. On the other hand, there does exist a distributive law of L^{+} over L where L^{+} is the submonad of nonempty lists. We turn to the details. The construction is the same for L^{+} over itself, and we emphasize this version because of its unusual involutory property.

5.1.10. Example. For the non-empty list monad L^{+} there exists a distributive law λ : L^{+}L^{+} → L^{+}L^{+} which is an involution, that is, λλ = id.

The simplest way to construct the law is with Theorem 2.4.9. Let S be the category of semigroups, these being the algebras for L^{+}. Define a lift L^{+} : S → S as follows. For (A, ·) a semigroup, (L^{+}A, ∗) is again a semigroup if

[x_{1}, …, x_{m}] ∗ [y_{1}, …, y_{n}] = [x_{1}, …, x_{m−1}, x_{m}y_{1}, y_{2}, …, y_{n}]

Here, x_{m}y_{1} refers to semigroup product in A. That η_{A} : A → L^{+}A is a semigroup homomorphism is obvious. It is also clear that f^{#} : L^{+}A → L^{+}B is a semigroup homomorphism if f : A → L^{+}B is because ∗ amalgamates only the last symbol of its first argument and the first symbol of its last argument. Thus the monad lifting corresponds to a distributive law σ of L^{+} over itself. Rather than compute σ by deciphering (16) we use a direct construction due to Koslowski [16]. Recall that μ_{A} : L^{+}L^{+}A → L^{+}A flattens a list of lists to a list. An element of L^{+}L^{+}A amounts to a pair (w, I) where w ∈ L^{+}A is a word of length n and I ⊂ {1, …, n − 1}. If w = [x_{1}, …, x_{n}] the corresponding list of lists is constructed as follows. First add leading and trailing brackets, [[x_{1}, …, x_{n}]]. Then replace the ith “,” with “], [”. For example, ([a, b, c, d], {2, 4}) corresponds to [[a], [b, c], [d]]. For fixed w this establishes a bijection between the 2^{n−1} subsets and all lists of lists μ_{A} of which is w. We then define λ : L^{+}L^{+} → L^{+}L^{+} by λ_{A}(w, I) = (w, I′) where I′ denotes set complement. Thus λ_{A}([a, b, c, d], {2, 4}) = ([a, b, c, d], {1, 3}), i.e., λ_{A} maps [[a], [b, c], [d]] to [[a, b], [c, d]]. It is obvious that such λ is a natural transformation and it is easily checked that the corresponding algebra lift is the one constructed above, so λ = σ.

The construction above easily adapts to a distributive law LL^{+} → L^{+}L.

References

[1] Ádamek, J. and Lawvere, F.W., How Algebraic is algebra?, Theory and Applications of Categories 8, 2001, 253-283.

[2] Appelgate, H., Acyclic Models and Resolvent Functors, dissertation, Mathematics Department, Columbia University, 1963.

[3] Arbib M. A. and Manes E. G., Fuzzy machines in a category, Journal of the Australian Mathematical Society 13, 1975, 169–210.

[4] Barr, M., Coequalizers and free triples, Mathematische Zeitschrift 116, 1970, 307– 322.

[5] Beck, J., Distributive laws, Lecture Notes in Mathematics 80, Springer-Verlag, 1969, 119-140.

[6] Bunge, M., Multilinear laws, Comunicaciones Técnicas, Serie Naranja 125, Instituto de Investigaciones en Matematicas Aplicadas y en Sistemas, Universidad Nacional Autonoma de Mexico, 1976.

MONAD COMPOSITIONS I  207

[7] Dubuc, E., Kan Extensions in Enriched Category Theory, Lecture Notes in Mathematics 145, Springer-Verlag, 1970.

[8] Eilenberg, S. and Moore, J. C., Adjoint functors and triples, Illinois Journal of Mathematics 9, 1965, 381–398.

[9] Gaifmann, H., Infinite Boolean polynomials I, Fundamenta Mathematicae 54, 1964, 229–250.

[10] Hales, A. W., On the non-existence of free complete Boolean algebras, Fundamenta Mathematicae 54, 1964, 45–66.

[11] Huber, P. J., Homotopy theory in general categories, Mathematisches Annalen 144, 1961, 361–385.

[12] Johnstone, P. T., Adjoint lifting theorems for categories of algebras, Bulletin London Mathematical Society 7, 1975, 294–297.

[13] Kleisli, H., Every standard construction is induced by a pair of adjoint functors, Proceedings of the American Mathematical Society 16, 1965, 544–546.

[14] King, D. and Wadler, P., Combining monads, Functional Programming, Springer Verlag, 1993, 134–143.

[15] Kock, A., Strong functors and monoidal monads, Arch. Math. 23, 1972, 113–120.

[16] Koslowski, J., A monadic approach to polycategories, Theory and Applications of Categories 14, 2005, 125–156.

[17] Linton, F. E. J., Autonomous equational categories, Journal of Mathematics and Mechanics 15, 1966, 637–642.

[18] Lüth, C. and Ghani, N. Composing monads using coproducts, ICFP’02, Oct. 4–6, 2002, www.informatik.uni-bremen.de/∼cxl/papers/icfp02.pdf.

[19] Mac Lane S., Categories for the Working Mathematician, Springer-Verlag, 1971.

[20] Manes, E. G., Algebraic Theories, Springer-Verlag, 1976.

[21] Manes, E. G., A class of fuzzy theories, Journal of Mathematical Analysis and its Applications 85, 1982, 409–451.

[22] Manes E. G., Monads of sets, in M. Hazewinkel (ed.), Handbook of Algebra, Vol. 3, Elsevier Science B.V., 2003, 67–153.

[23] Manes, E. G. and Mulry, P. S., Monad compositions II: Kleisli strength, to appear.

[24] Manes, E. G. and Mulry, P. S., Monad compositions III: monad approximation, to appear.

[25] Marmolejo, F. and Rosebrugh, R. and Wood R. J., A basic distributive law, Journal of Pure and Applied Algebra 168, 2002, 209-226.

[26] Meyer J.-P., Induced functors on categories of algebras, Mathematics Department, John Hopkins University, Preprint, 1972.

[27] Moggi, E. Notions of computation and monads, Information and Computation 93, 1991, 55–92.

[28] Mulry P. S., Lifting theorems for Kleisli categories, Springer Lecture Notes in Computer Science 802, 1994, 304–319.

[29] Mulry P. S., Lifting results for categories of algebras, Theoretical Computer Science 278, 2002, 257–269.

[30] Street R. S., The formal theory of monads, Journal of Pure and Applied Algebra 2, 1972, 149–168.

[31] Wadler, P., The essence of functional programming, Conference Proceedings of the 19th ACM Symposium on Principles of Programming Languages, ACM Press, 1–14, 1992.

[32] Wolff, H., Extension of functors to categories of algebras, preprint, circa 1971.

321 Truce Road Conway, MA 01341 USA and Dept. of Computer Science Colgate University Hamilton, NY 13346 USA

Email: manes@math.umass.edu
      pmulry@mail.colgate.edu

This article may be accessed at http://www.tac.mta.ca/tac/ or by anonymous ftp at

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/18/7/18-07.{dvi,ps,pdf}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available in .dvi, Postscript and PDF from the journal’s server at http://www.tac.mta.ca/tac/ and by ftp. It is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX2e strongly encouraged. Articles should be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Aurelio Carboni, Università dell Insubria: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk P. T. Johnstone, University of Cambridge: ptj@dpmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, University of Western Sydney: s.lack@uws.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu James Stasheff, University of North Carolina: jds@math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Insubria: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca