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.

One thought on “The Relative Monad Kleisli Construction”

  1. Pingback: The Relative Monad Eilenberg-Moore Construction – Dan Marsden

Leave a comment