relative monads

The Relative Monad Eilenberg-Moore Construction

In previous posts, we have seen that relative adjunctions induce relative monads, and in fact every relative monad arises in this way via a Kleisli construction. The Kleisli construction is the initial adjunction that induces a given relative monad. In this post, we are going to look at an Eilenberg-Moore construction that yields a terminal resolution of every relative monad.

As relative monads are described as a variant of Kleisli triples, this made describing the Kleisli construction very straightforward. Unfortunately, this formulation will make the Eilenberg-Moore construction a little bit fiddlier.

Algebras of a Relative Monad

For a $J : \mathcal{C} \rightarrow \mathcal{D}$ -relative monad $(\mathbb{T},\eta,(-)^*)$ , an Eilenberg-Moore algebra consists of:

A carrier $\mathcal{D}$ -object $A$ .
For every $\mathcal{C}$ -object $X$ and $\mathcal{D}$ -morphism $v : J(X) \rightarrow A$ , a morphism $\alpha(v) : \mathbb{T}(X) \rightarrow A$ .

These must satisfy the following axioms:

For every $\mathcal{C}$ -object $X$ and $v : J(X) \rightarrow A$ , $v = \alpha(v) \cdot \eta_Z$ .
For every pair of $\mathcal{C}$ -objects $X$ and $Y$ , $\mathcal{C}$ -object $s : J(X) \rightarrow \mathbb{T}(Y)$ and $v : J(Y) \rightarrow A$ , $\alpha (\alpha(v) \cdot s) = \alpha(v) \cdot s^*$ .

A morphism of Eilenberg-Moore algebras of type $(A,\alpha) \rightarrow (B, \beta)$ is a $\mathcal{D}$ -morphism $h : A \rightarrow B$ such that for every $\mathcal{D}$ -morphism $v : J(Z) \rightarrow A$ :

$h \cdot \alpha(v) = \beta(h \cdot v)$

These form a category $\mathbf{EM}(\mathbb{T})$ , the Eilenberg-Moore category.

Compared to the definition of the Kleisli category for a relative monad, the Eilenberg-Moore category is rather cumbersome. To get some intuition for what is going on, we will look at a particular example in some detail. As suggested by the term Eilenberg-Moore algebra, we we consider an algebraic example.

Recall that a monoid is a structure with a binary operation, which we will write as $\times$ , and a unit, denoted $1$ , satisfying the following three equations:

Left unit: $1 \times x = x$ .
Right unit: $x \times 1 = x$ .
Associativity: $x \times (y \times z) = (x \times y) \times z$ .

Given a set $X$ , we can form the set of equivalence classes of terms built up from multiplication, the unit and variables. Terms are considered equivalent if they are provably equal in equational logic from the axioms of a monoid. For example

$1, 1 \times x, x \times 1, x \times (1 \times 1), x \times y, \ldots$

are all terms, and the first four are provably equal. Only finitely many variables may appear in any given term, but the collection of equivalence classes of terms over a finite set is infinite. For example, even if we have just one variable $x$ , non of the following terms can be proved equal:

$x, x \times x, x \times (x \times x), x \times (x \times (x \times x)), \ldots$

This suggests we consider the functor $J : \mathsf{FinSet} \rightarrow \mathsf{Set}$ including the finite sets into the infinite sets, relating the finite and infinite aspects at play. For any finite set $X$ , we can then take $\mathbb{T}(X)$ to be the equivalence class of terms over $X$ . There is an obvious function:

$\eta_X : J(X) \rightarrow \mathbb{T}(X)$

picking out the equivalence class of each variable in $J(X)$ . Finally, we can think of a function

$f : J(X) \rightarrow \mathbb{T}(Y)$

as specifying a family of equivalence classes of terms over the set finite $Y$ , indexed by the finite set $X$ . Informally, the extension

$f^* : \mathbb{T}(X) \rightarrow \mathbb{T}(Y)$

is a substitution operation, taking equivalence classes of terms over $X$ to those over $Y$ , replacing variables as specified by $f$ . This data together forms a $J$ -relative monad $(\mathbb{T},\eta,(-)^*)$ .

Remark: The relative monad we have just described is the one induced from the ordinary list monad. This is unsurprising as the list monad is the free monoid monad.

A monoid consists of a carrier set $A$ and a choice of:

A function $\times^A : A \times A \rightarrow A$ telling us how the binary operation behaves.
A constant $1^A \in A$ specifying the value of the unit.

Given a term such as

$x \times y \times 1$

and a monoid $(A, \times^A, 1^A)$ , we can evaluate this term to an element of the carrier using the specified multiplication operation and unit constant, if we are given an element in the carrier for each of the variables. In fact, we should get the same value for any term provably equal to this one such as

$x \times y$

Therefore, for any valuation, $v : J(X) \rightarrow A$ , a monoid allows us to build a function

$\alpha(v) : \mathbb{T}(X) \rightarrow A$

which inductively evaluates terms over the same finite set, using the valuation to assign values to the unknowns. This function has some nice properties. Firstly, if a term is the equivalence class of a variable, it will return the value assigned to that variable. This is captured by the equation:

$\alpha(v) \cdot \eta_X = v$

Secondly, it respects the compositional structure of terms. We can think of a function $s : J(X) \rightarrow \mathbb{T}(Y)$ as specifying a substitution, which allows us to build a “bigger” $\mathbb{T}(Y)$ term from a $\mathbb{T}(X)$ term, by using the substitution to replace all the variables with terms over $Y$ . Our evaluation function $\alpha$ builds up results inductively, so we can either evaluate subterms, and then combine them, or evaluate an entire composite term, and we get the same result. This intuition is encoded in the equation:

$\alpha (\alpha(v) \cdot s) = \alpha(v) \cdot s^*$

From the discussion above, a monoid induces an Eilenberg-Moore algebra. In fact, the two axioms forcing good behaviour in terms of variables and compositional structure mean that every Eilenberg-Moore algebra encodes the structure of a monoid. This is similar to how the good behaviour of the Eilenberg-Moore algebras of an ordinary monad was encoded in the unit and multiplication axioms they are required to satisfying. A bit more work shows that the morphisms in the Eilenberg-Moore category correspond to monoid morphisms, so the Eilenberg-Moore category is actually the category of monoids.

Remark: The Eilenberg-Moore algebras may have infinite carriers, despite the fact the terms and valuations are built up from finite sets of variables.

From this example, our intuitions for an Eilenberg-Moore algebra should be:

The carrier is the carrier of some algebraic object.
The elements of $\mathbb{T}(X)$ can be thought of as terms over some object of variables.
$\alpha(v)$ tells us how to evaluate such terms, with the valuation $v$ specifying the values of the variables.
The axioms specify that the operation $\alpha(v)$ must evaluate terms in an inductive manner, built up from the variables in a compositional manner, using a fixed interpretation for each of the operations.

There is nothing in the above discussion which is specific to monoids. We can choose any algebraic structure presented by finite operations and a set of equations, and the class of models will emerge as the Eilenberg-Moore category of the corresponding $J$ -relative monad.

The Eilenberg-Moore Resolution

For $J : \mathcal{C} \rightarrow \mathcal{D}$ , and $J$ -relative monad $(\mathbb{T},\eta,(-)^*)$ , there is an obvious forgetful functor:

$U^{\mathbb{T}} : \mathbf{EM}(\mathbb{T}) \rightarrow \mathcal{D}$ .

sending an algebra to its carrier. There is also a functor

$F^{\mathbb{T}} : \mathcal{C} \rightarrow \mathbf{EM}(\mathbb{T})$ ,

such that $F^{\mathbb{T}}(X)$ has universe $\mathbb{T}(X)$ , and for $v : J(W) \rightarrow X$ :

$\alpha(v) = v^*$

On morphisms:

$F^{\mathbb{T}}(f) = \mathbb{T}(f)$ .

In fact, $F^{\mathbb{T}}$ is $J$ -relative left adjoint to $U^{\mathbb{T}}$ , and is the terminal resolution of the original relative monad $\mathbb{T}$ .

Conclusion

It is satisfying given the apparently slightly ad-hoc formulation of relative monad that a satisfactory connection with adjunctions emerges. We get two canonical resolutions, the initial Kleisli resolution and the terminal Eilenberg-Moore resolution, exactly as we did in the world of ordinary monad theory.

Our main example was from universal algebra. The relative monad structure allowed us to separate out finitary concerns about variables from infinitary aspects involving the carriers of algebras. This was not directly possible in the ordinary monadic setting, as the restriction to endofunctors forces “all the bookkeeping to happen in the same place”.

Further reading: The Eilenberg-Moore construction is introduced in the original “Monads need not be endofunctors” paper, which as usual is recommended reading.

The Relative Monad Kleisli Construction

We have now seen both relative monads and relative adjunctions, and how every relative adjunction induces a relative monad. As in conventional monad theory, it is natural to ask ourselves if every relative monad arises in this way. The mathematics parallels the situation for ordinary monads. In todays post will look at one extremal construction, generalising the ordinary Kleisli category and its corresponding adjunction.

From a computational perspective, the traditional Kleisli captured the basic aspects of effectful computation. The Kleisli category for a relative monad might be seen as modelling effectful computation on constrained or structured inputs.

Kleisli Categories of Relative Monads

For $J : \mathcal{B} \rightarrow \mathcal{D}$ assume we have a $J$ -relative monad $(\mathbb{T},\eta, (-)^*)$ . The Kleisli category $\mathbf{Kl}(\mathbb{T})$ has:

Objects: The objects of $\mathcal{B}$ .
Morphisms: The morphisms of type $B_1 \rightarrow B_2$ in $\mathbf{Kl}(\mathbb{T})$ are morphisms of type $J(B_1) \rightarrow \mathbb{T}(B_2)$ . The identity at $B$ is $\eta_{B} : J(B) \rightarrow \mathbb{T}(B)$ . The composite $g \bullet f$ in the Kleisli category is given by $g^* \cdot f$ in $\mathcal{D}$ .

The structure of this category, and verifying the category axioms, follow pretty directly from the properties of the Kleisli triple. As with the notion of $J$ -relative monad, the structure of the Kleisli category is a pretty routine generalisation of the ordinary notion, with $J$ inserted in a few places to make things type check.

Remark: We make a different notational choice for the Kleisli category of a relative monad than the one we used in the ordinary situation. This is because the traditional notation seems a bit less natural once the monad is not an endofunctor.

We will now look at a few examples, all arising as the relative monad induced by an ordinary monad, for a suitable choice of $J$ .

Example: Let $J : \mathsf{FinSet} \rightarrow \mathsf{Set}$ be the inclusion of the subcategory of finite sets into the category of sets. The Kleisli category of the $J$ -relative monad induced by the powerset monad $\mathbb{P} : \mathsf{Set} \rightarrow \mathsf{Set}$ is the category with:

Objects: Finite sets
Morphisms: A morphism $A \rightarrow B$ is a binary relation $R \subseteq A \times B$ . Composition and identities are the usual thing for binary relations.

Notice this is neither the Kleisli category of the powerset monad, or the finite powerset monad. In this case, it is equivalent to the powerset monad on the category of finite sets.

In the previous example, everything ended up being finite due to properties specific to the powerset construction. Before we start developing bad intuitions, lets look at a different example that behaves differently.

Example: For $J$ as in the previous example, consider the relative monad induced by the list monad $\mathbb{L}$ . The Kleisli category has:

Objects: Finite sets.
Morphisms: Functions $A \rightarrow \mathbb{L}(B)$ with composition and identities as for the ordinary list monad.

Notice here, this is not the same as the Kleisli category of the list monad itself. There is no obvious analogue of the finite powerset to consider in this case either. Nor can we simply restrict the list monad to an endofunctor on finite sets, as the collection of lists of elements taken from a finite set is infinite. So here we see some genuine interplay between the finite and infinite aspects of the construction.

Another natural, if a bit pathological, source of examples will help to test our intuitions even further.

Example: For any $J : \mathcal{B} \rightarrow \mathcal{D}$ , we can consider the relative monad induced by the identity monad. This will have:

Objects: Objects in the category $\mathcal{B}$ .
Morphisms: Morphisms of type $B_1 \rightarrow B_2$ are $\mathcal{D}$ -morphisms of type $J(B_1) \rightarrow J(B_2)$ . Composition and identities are exactly as in $\mathcal{D}$ .

For different choices of $J$ :

$(-) + 1 : \mathsf{Set} \rightarrow \mathsf{Set}$ gives the category of non-empty sets and functions between them.
$(-) + E : \mathsf{Set} \rightarrow \mathsf{Set}$ gives the category of sets with at least $|E|$ elements, and functions between them.
$(-) \times S : \mathsf{Set} \rightarrow \mathsf{Set}$ has Kleisli category equivalent to the Kleisli category of the state monad with state set $S$ .
$K^{(-)} : \mathsf{Set}^{op} \rightarrow \mathsf{Set}$ has Kleisli category equivalent to the Kleisli category of the continuation monad on set $K$ .

We also note the following obvious example, establishing the connection with ordinary monads.

Example: As we have previously seen, an $\mathsf{Id}$ -relative monad is the same thing as an ordinary monad. The associated Kleisli construction is also the same as in the case of ordinary monads.

The Kleisli Adjunction

For $J : \mathcal{B} \rightarrow \mathcal{D}$ , and $J$ -relative monad $(\mathbb{T}, \eta, (-)^*)$ , we have the following functors:

$F_{\mathbb{T}} : \mathcal{B} \rightarrow \mathbf{Kl}(\mathbb{T})$ , with $F_{\mathbb{T}}(B) = B$ , and $F_{\mathbb{T}}(h) = \eta_B \cdot J(h)$ .
$U_{\mathbb{T}} : \mathbf{Kl}(\mathbb{T}) \rightarrow \mathcal{D}$ , with $U_{\mathbb{T}}(B) = \mathbb{T}(B)$ and $U_{\mathbb{T}}(h) = h^*$ .

It is a routine exercise to show that $F_{\mathbb{T}}$ is a $J$ -relative left adjoint of $U_{\mathbb{T}}$ , and that this adjunction induces the relative monad $\mathbb{T}$ .

We can form a category with objects resolutions of a fixed $J$ -relative monad. A morphism of resolutions via categories $\mathcal{C}_1$ and $\mathcal{C}_2$ is a functor $H : \mathcal{C}_1 \rightarrow \mathcal{C}_2$ commuting with the left and right adjoints in the obvious way. The Kleisli adjunction is initial in this category. For another resolution with left adjoint $L$ , the unique Kleisli comparison functor is given on objects by $K(B) = L(B)$ and on morphisms $K(h)$ is the transpose of $h$ under the codomain adjunction. As taking transposes is a bijection, this functor is full and faithful.

Generalising the situation for ordinary monads:

The comparison functor is an isomorphism iff $L$ is bijective on objects.
The comparison functor is an equivalence iff $L$ is essentially surjective.

Conclusion

We have seen that every relative monad is induced by an adjunction, via a generalisation of the Kleisli construction for ordinary monads. The resulting Kleisli categories were surprisingly varied, given the extra flexibility that relative monads provide.

Given what we have learned about ordinary monad theory, we should ask ourselves whether there is an analogue of the Eilenberg-Moore construction as well. That is the topic we will address next time.

Futher reading: The Kleisli construction for relative monads appears in “Monads need not be endofunctors”. That the characterisation of adjunctions of Kleisli type generalises to the relative setting appears in Nathanael Arkor’s thesis, where they serve an important role in connection to algebra.

Relative Adjunctions and Density

In the previous post, we encountered relative adjunctions. One curious aspect was that if $L$ is left $J$ -relative adjoint to $R$ :

$R$ determines $L$ up to isomorphism.
$L$ does not necessarily determine $R$ up to isomorphism.

In this post, we’re going to look at this aspect of relative adjunctions in more detail. We will see that we get better behaviour if $J$ is a dense functor. This is an important aspect of relative monad theory, so it is worth seeing it in action.

Adjoints determine each other

As before, we will warm up by considering the non-relative situation, and look at ordinary adjunctions. In that case, if $L \dashv R$ and $L \dashv R'$ , we have natural isomorphisms:

$\mathcal{D}(A, R(B)) \cong \mathcal{C}(L(A),B) \cong \mathcal{D}(A,R'(B))$

Now we calculate:

$[\mathcal{C},\mathcal{D}](F,R) \cong \int_C \mathcal{D}(F(C),R(C)) \cong \int_C \mathcal{D}(F(C),R'(C)) \cong [\mathcal{C},\mathcal{D}](F,R')$

The first and final steps use the following standard natural isomorphism relating natural transformations and ends:

$[C,D](F,G) \cong \int_C \mathcal{C}(F(C),G(C))$

The middle step then simply uses our assumed adjunctions. From our calculated isomorphism, as the Yoneda lemma is full and faithful:

$R \cong R'$ ,

so $L$ determines $R$ up to isomorphism. It is clear that we could use a symmetrical argument to show that $L$ is fully determined by $R$ . For a reader familiar with these “Yoneda style” arguments, this is a very routine proof, with the relationship between natural transformations and ends allowing us to make the connection between functors and their actions.

Relative adjunctions

Now we have seen a proof relating adjoints for ordinary adjunctions, lets see how we can adapt it to the $J$ -relative setting. As relative adjunctions are asymmetrical, there are two aspects to consider.

Firstly, we assume that both $L$ and $L'$ are left $J$ -relative adjoint to $R$ , so we have natural isomorphisms:

$\mathcal{C}(L(A), B) \cong \mathcal{D}(J(A),R(B)) \cong \mathcal{C}(L'(A),B)$

We can actually perform an a very similar calculation to before:

$[\mathcal{B},\mathcal{C}](L,F) \cong \int_B \mathcal{C}(L(B),F(B)) \cong \int_B \mathcal{C}(L'(B),F(B)) \cong [\mathcal{B},\mathcal{C}](L',F)$ ,

and so $L \cong L'$ . So far, so straightforward.

Now lets consider the situation for the right adjoint. We now assume that $L$ is left $J$ -relative adjoint to both $R$ and $R'$ , so we have natural isomorphisms:

$\mathcal{D}(J(A),R(B)) \cong \mathcal{C}(L(A),B) \cong \mathcal{D}(J(A),R'(B))$

We can try and proceed as before, with the first step

$[\mathcal{C},\mathcal{D}](F,R) \cong \int_C \mathcal{D}(F(C),R(C))$ ,

but we immediately become stuck, as the only relationships we have involving the functor $R$ also mention $J$ . To make progress, we need something new.

A functor $J : \mathcal{B} \rightarrow \mathcal{D}$ is said to be dense if the restricted Yoneda embedding

$\mathcal{D} \rightarrow [\mathcal{B}^{op},\mathsf{Set}]$

is full and faithful. Explicitly, this means we have a natural isomorphism:

$\mathcal{D}(D,D') \cong [\mathcal{B}^{op},\mathsf{Set}](\mathcal{D}(J(-),D), \mathcal{D}(J(-),D'))$

This looks encouraging, as $J$ appears exactly in the position we would hope. With the same assumptions as before, assuming $J$ is dense, we calculate:

$\begin{aligned} [\mathcal{C},\mathcal{D}](F,R) &\cong \int_C \mathcal{D}(F(C),R(C)) \\ &\cong \int_C [\mathcal{B}^{op},\mathsf{Set}](\mathcal{D}(J(-),F(C)), \mathcal{D}(J(-),R(C))) \\ &\cong \int_C \int_B \mathsf{Set}(\mathcal{D}(J(B),F(C)), \mathcal{D}(J(B),R(C))) \\ &\cong \int_C \int_B \mathsf{Set}(\mathcal{D}(J(B),F(C)), \mathcal{D}(J(B),R'(C))) \\ &\cong \int_C [\mathcal{B}^{op},\mathsf{Set}](\mathcal{D}(J(-),F(C)), \mathcal{D}(J(-),R'(C))) \\ &\cong \int_C \mathcal{D}(F(C),R'(C)) \\ &\cong [\mathcal{C},\mathcal{D}] (F,R') \end{aligned}$

Therefore, $R \cong R'$ , so if $J$ is dense, right adjoints are determined up to isomorphism.

Conclusion

This post was a bit more technical than usual. This was so that the role of density in the arguments could be made fully explicit. Along the way we saw that density wasn’t a particularly complicated condition, simply allowing us to make Yoneda style arguments in more restrictive settings. Density fits very naturally into calculations involving relative monads or adjunctions, and was introduced by Ulmer in the same paper as relative adjunctions. Ulmer indicates that Gabriel had also introduced the same notion independently at about the same time. Kelly points out in “Basic Concepts in Enriched Category Theory” that the special case of dense subcategories actually goes back further to Isbell’s “Adequate subcategories” from 1960. That the idea has arisen independently several times provides evidence of its utility.

Further reading: I’ve probably recommended it before, but for users wanting more background on these Yoneda style arguments, I strongly recommended Loregian’s “(Co)end calculus” book.

Acknowledgement: Thanks to Nathanael Arkor for very helpful feedback correcting some erroneous remarks relating to the history of dense functors in earlier versions.

Relative Adjunctions

A large part of the richness of ordinary monad theory comes with the interplay between monads and adjunctions. Now we have encountered relative monads, a natural next step is to look for connections with adjunctions. That is the purpose of todays post.

Kleisli Triples and Adjunctions

As relative monads are formulated as a generalisation of Kleisli triples, it makes sense to use the relationship between adjunctions and that formulation of ordinary monads as a starting point, before attempting to generalise to the relative setting.

As we are favouring monads in Kleisli form, it is worth thinking about which formulation of adjunctions is going to fit comfortably. There are many equivalent choices, we can consider adjunctions in terms of:

Cup and cap natural transformations satisfying snake equations.
A pair of functors satisfying a certain unique fill-in condition.
A natural bijection between hom sets $\mathcal{C}(L(A),B) \cong \mathcal{D}(A,R(B))$ .
…

As a monad in Kleisli form has an extension operation:

$(-)^* : \mathcal{C}(A,\mathbb{T}(B)) \rightarrow \mathcal{C}(\mathbb{T}(A),\mathbb{T}(B))$ ,

which is a mapping between hom sets, this seems to connect well with the natural bijection between hom sets formulation of adjunctions. So lets assume we have an adjunction, witnessed by a natural isomorphism:

$\mathcal{C}(L(A),B) \xrightarrow{\theta_{A,B}} \mathcal{D}(A,R(B))$

We wish to show that this induces a monad, using the extension form. The action on objects is:

$X \mapsto RL(X)$

For the unit map, we note that $\theta_{A,L(A)}$ has type

$\mathcal{C}(L(A),L(A)) \xrightarrow{\theta_{A,L(A)}} \mathcal{D}(A,R(L(A)))$

so we take the components of our unit as

$\eta_A = \theta_{A,L(A)}(\mathsf{id})$ .

Finally, we need to identify a suitable extension operation. The following composite has the right type:

$\mathcal{D}(A,RL(B)) \xrightarrow{\theta^{-1}_{A,L(B)}} \mathcal{C}(L(A),L(B)) \xrightarrow{R_{A,B}} \mathcal{D}(RL(A),RL(B))$

where $R_{A,B}$ is the map that applies the functor $R$ to a given hom set. More explicitly, we take:

$f^* = R(\theta^{-1}_{A,B}(f))$ .

We have three axioms to check. Firstly, we calculate:

$\eta^*_A = \theta(\mathsf{id})^* = R(\theta^{-1}(\theta(\mathsf{id})) = R(\mathsf{id}) = \mathsf{id}$ .

Secondly,

$f^* \cdot \eta_A = R(\theta^{-1}(f)) \cdot \theta(\mathsf{id}) =\theta(\theta^{-1}(f) \cdot \mathsf{id}) = \theta(\theta^{-1}(f)) = f$ ,

where we use the naturality of $\theta$ in the only non-trivial step.

Finally:

$g^* \cdot f^* = R(\theta^{-1}(g)) \cdot R(\theta^{-1}(f)) = R(\theta^{-1}(g) \cdot \theta^{-1}(f)) = R(\theta^{-1}(R(\theta^{-1}(g)) \cdot f)) = R(\theta^{-1}(g^* \cdot f) = (g^* \cdot f)^*$

Again, the only non-trivial step uses naturality. With this proof for ordinary monads under our belts, we’re ready to look at relative monads.

Relative adjunctions

We now want to tweak things to try and recover a $J$ -relative monad, from a similar situation to before. Previously, we constructed the unit $\eta_A$ as the image of the identity under a map of type:

$\mathcal{C}(L(A),L(A)) \rightarrow \mathcal{D}(A,RL(A))$

For a $J$ -relative monad, the component of the unit at $A$ has type $J(A) \rightarrow RL(A)$ . This suggests we require a natural isomorphism of type:

$\mathcal{C}(L(A),B) \xrightarrow{\theta_{A,B}} \mathcal{D}(J(A),R(B))$

where $J : \mathcal{J} \rightarrow \mathcal{D}$ , $L : \mathcal{J} \rightarrow \mathcal{C}$ and $R : \mathcal{C} \rightarrow \mathcal{D}$ . If we have such an isomorphism, we can follow an almost identical recipe to before to form a $J$ -relative monad with:

Object map $T(X) = RL(X)$ .
Unit components $\eta_A = \theta(\mathsf{id}) : J(A) \rightarrow RL(A)$ .
Extension operation $f^* = R(\theta^{-1}(f))$ .

The proofs of the three axioms are identical to the previous ones, up to trivial changes in type information.

Our calculations lead us to consider isomorphisms of hom sets of the form:

$\mathcal{C}(L(A),B) \cong \mathcal{D}(J(A),R(B))$

If we have such an natural isomorphism we say that $R$ has a left $J$ -relative adjoint $L$ . We could also consider the situation:

$\mathcal{C}(L(A),J(B)) \cong \mathcal{D}(A,R(B))$

in which case we say that $L$ has a right $J$ -relative adjoint $R$ . Both situations are known as relative adjunctions.

Example: A functor $F : \mathcal{C} \rightarrow \mathcal{D}$ is full and faithful if and only if $\mathsf{Id}$ is its $F$ -relative left adjoint, as that is the case when we have a natural isomorphism:

$\mathcal{C}(A,B) \cong \mathcal{D}(F(A),F(B)$

It follows that every full and faithful functor induces a relative monad.

We also have the obvious source of examples.

Example: Every ordinary adjunction is a $\mathsf{Id}$ -relative adjunction.

We can also build new relative adjoints in a routine way.

Example: If we have relative adjunction:

$\mathcal{C}(L(A),B) \cong \mathcal{D}(J(A),R(B))$

then for any $F$ of appropriate type:

$\mathcal{C}(L(F(A)), B) \cong \mathcal{D}(J(F(A)),R(B))$

so $L \circ F$ is $J \circ F$ -relative left adjoint to $R$ . Using the previous example, given an ordinary adjunction $L \dashv R$ , we get relative adjunctions:

$\mathcal{C}(L(F(A)),B) \cong \mathcal{D}(F(A),R(B))$

so $L \circ F$ is $F$ -relative adjoint to $R$ .

Some words of caution

We have seen that left $J$ -relative adjoints yield $J$ -relative monads. Unfortunately relative adjunctions are not as well behaved as ordinary adjunctions, for example:

The situation is asymmetric. Left $J$ -relative adjoints induce $J$ -relative monads but not comonads, and unit maps of type $J \Rightarrow RL$ , but no counit. On the other hand, right $J$ -relative adjoints induce $J$ -relative comonads but not monads, and counit maps of type $LR \Rightarrow J$ , but no unit.
A functor determines its $J$ -relative left adjoint, but the $J$ -relative left adjoint does not fully determine the right adjoint.
There is an equivalent formulation of relative adjunctions in terms of absolute Kan lifts. This might sound like it would lead to a tidier setting, more suitable for formal category theory. Unfortunately, it does not capture the right notion if we move to the setting of enriched category theory.

Conclusion

By examining the construction of Kleisli triples from ordinary adjunctions, we identified a variation on the notion of adjunction, that induces relative monads. We have seen a small number of examples of relative adjunctions so far. Readers of this blog are probably (hopefully) asking themselves the following questions:

Does every relative monad arise via an adjunction?
Is there a suitable generalisation of the Kleisli construction?
Is there a suitable generation of the Eilenberg-Moore construction?

Positive answers to these questions would provide stronger evidence that relative adjunctions are a reasonable concept. We shall explore these topics in future posts.

Further reading: Ulmers “Properties of Dense and Relative Adjoint Functors” is a good place to start for more background, and is surprisingly readable for an older category theory paper.

Acknowledgements: Nathanael Arkor helpfully pointed out a blunder in an earlier version of this post, where I had muddled up Kan extensions and lifts in a remark.

In todays post, we move away from the fancy 2-categorical formal monad theory we have been exploring recently, and commence a new topic. Beginning in a fairly elementary manner, we consider a generalisation of the notion of monad which comes up frequently in practice; that of relative monads.

Does a monad have to be an endofunctor?

As we have seen many times, a monad consists of an endofunctor $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ , along with unit and multiplication natural transformations satisfying some equations. These equations say that this structure is a monoid in the endofunctor category $[\mathcal{C},\mathcal{C}]$ , with respect to the composition monoidal structure.

We will now consider how we can generalise the notion of monad so that $\mathbb{T}$ can be an arbitrary functor rather than just an endofunctor. Lets explore how we might try and make this work.

Firstly, we fix an arbitrary functor $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{D}$ . As a first step to viewing $\mathbb{T}$ as the functor component of a monad, we would like a suitable generalisation of unit for this structure. For an ordinary monad, this would be a natural transformation:

$\eta : \mathsf{Id} \Rightarrow \mathbb{T}$

Unfortunately, this wont type check now that $\mathbb{T}$ has more general type, as natural transformations must go between a pair of functors of the same type. To fix this problem, we shall introduce a second functor $J : \mathcal{C} \rightarrow \mathcal{D}$ , and take our unit to be of type:

$\eta : J \Rightarrow \mathbb{T}$

The functor $J$ is an extra parameter that didn’t appear in the definition of a conventional monad, so we are heading towards a definition that is relative to this choice of functor $J$ . So maybe we’re looking for monoids in the functor category $[\mathcal{C}, \mathcal{D}]$ ?

To see if this is the case, we also need to consider the type of the multiplication natural transformation. For an ordinary monad, this has type:

$\mathbb{T} \circ \mathbb{T} \Rightarrow \mathbb{T}$ .

Here we hit on a harder problem than before, as we cannot compose $\mathbb{T}$ with itself, as the domain and codomain don’t match now we’ve removed the restriction to working with endofunctors. What to do?

We seem to have reached a bit of a dead end, so lets try addressing the same problem from a different direction. We have seen an alternative definition of monads before, using the extension or Kleisli form. Recall that this consists of three pieces of data:

A function of type $\mathbb{T} : \mathsf{obj}(\mathcal{C}) \rightarrow \mathsf{obj}(\mathcal{C})$ .
An $\mathsf{obj}(\mathcal{C})$ -indexed family of unit morphisms $\eta_A : A \rightarrow \mathbb{T}(A)$ .
A family of extension operations on morphisms $(-)^* : \mathcal{C}(A, \mathbb{T}(B)) \rightarrow \mathcal{C}(\mathbb{T}(A),\mathbb{T}(B))$ , indexed by pairs of $\mathcal{C}$ objects.

We also require the following three axioms to hold:

$(\eta_A)^* = \mathsf{id}_A$ .
$f^* \cdot \eta_A = f$ .
$(g^* \cdot f^*) = (g^* \cdot f)^*$ .

Using what we learned from our first attempt to generalise to more general functors, we are going to try and adjust this definition relative to an endofunctor $J : \mathcal{C} \rightarrow \mathcal{D}$ . So from our previous analysis, we will need a function

$\mathbb{T} : \mathsf{obj}(\mathcal{C}) \rightarrow \mathsf{obj}(\mathcal{D})$

and a family of unit maps

$\eta_A : J(A) \rightarrow \mathbb{T}(A)$ .

It remains to generalise the extension operations. Unlike with the definition of monad multiplication, the type of the extension operations for a monad do not involve any composites of the form $\mathbb{T} \circ \mathbb{T}$ , so life is more straightforward. We simply adjust the types as follows:

$(-)^* : \mathcal{D}(J(A),\mathbb{T}(B)) \rightarrow \mathcal{D}(\mathbb{T}(A),\mathbb{T}(B))$ .

The three equations above still type check, and so it is natural to require that they hold. This gives us our definition of $J$ -relative monad, as a triple consisting of:

A function $\mathbb{T} : \mathsf{obj}(\mathcal{C}) \rightarrow \mathsf{obj}(\mathcal{D})$ .
An $\mathsf{obj}(\mathcal{C})$ -indexed family of unit morphisms $\eta_A : J(A) \rightarrow \mathbb{T}(A)$ .
A family of extension operations on morphisms $(-)^* : \mathcal{C}(J(A), \mathbb{T}(B)) \rightarrow \mathcal{C}(\mathbb{T}(A),\mathbb{T}(B))$ , indexed by pairs of $\mathcal{C}$ objects.

These should satisfy the three equations above. As a first check that this definition is reasonable, we note the following implications.

The function $\mathbb{T}$ extends to a functor of type $\mathcal{C} \rightarrow \mathcal{D}$ with action $\mathbb{T}(f) = (\eta_B \cdot f)^*$ .
Now $\mathbb{T}$ is a functor, we can show that the family of unit morphism form a natural transformation $\eta : J \Rightarrow \mathbb{T}$ .
The extension operations $(-)^* : \mathcal{D}(J(A),\mathbb{T}(B)) \rightarrow \mathcal{D}(\mathbb{T}(A), \mathbb{T}(B))$ are natural in both variables. That is: $(\mathbb{T}(g) \cdot f \cdot J(e))^* = \mathbb{T}(g) \cdot f^* \cdot \mathbb{T}(e)$ .

As further evidence that this definition is reasonable, it is a legitimate generalisation of ordinary monads.

Example: A $\mathsf{Id}$ -relative monad is the same thing as an ordinary monad.

We also have the following source of many additional relative monads.

Example: Given an ordinary monad $\mathbb{T}$ on category $\mathcal{D}$ , and a functor $J : \mathcal{C} \rightarrow \mathcal{D}$ , we get a $J$ -relative monad with object map

$A \mapsto \mathbb{T}(J(A))$ ,

unit morphisms

$\eta_{J(A)} : J(A) \rightarrow \mathbb{T}(J(A))$ .

The extension maps for the ordinary monad $\mathbb{T}$ restrict to act on morphisms with codomains of the form $J(A)$ for our relative monad.

The previous examples are often referred to as trivial, as they are built from ordinary monads. This underplays their importance, as in many cases it can be more natural to work with data in the form of a relative monad, rather than an ordinary monad, or to explore the relationship between the two. We will explore examples of this type in more detail in later posts, along with more general examples.

Conclusion

We have introduced a generalisation of the notion of monad, removing the restriction to endofunctors. I have to admit that when I initially encountered this definition, my first instinct was that the whole thing looked rather arbitrary, and a bit of a hack. I think this knee jerk opinion was wrong, and that actually relative monads are a natural and important concept. This revised opinion is based on the following evidence:

Relative monads occur naturally in practice, and also yield a starting point for further useful generalisation.
It is possible to develop a useful body of theory at the level of relative monads, so the abstraction is sufficiently powerful to do useful mathematical work.
Even when other formulations are possible, it is often convenient to present certain mathematical constructions in the form of relative monads, making them a practical mathematical tool.

We will see examples illustrating the claims above in future posts.

Another instructive aspect of relative monads is how we benefit from having multiple formulations of the same mathematical abstraction. In this case, it turned out to be more convenient to generalise the extension or Kleisli form of a monad. By contrast, the monoid formulation, often preferred by mathematicians, proved more challenging. We will return to the question of whether relative monads can be seen as monoids in a later post.

Further reading: The standard starting point for relative monads is probably the paper “Monads need not be endofunctors” by Altenkirch, Chapman and Uustalu. It is worth finding the longer journal version if possible, as this contains more details and proofs than the shorter conference paper that typically crops up first on internet searches. For those wanting more theory and recent developments, I’d recommend reading the PhD thesis of Nathanael Arkor, which also contains a very enjoyable introduction to the topic.

Acknowledgements: I am grateful to Zhixuan Yang who identified a confusing mathematical typo in an earlier version of this post.