Public:Comonads

\( \require{html} \newcommand\seArrow{\style{display: inline-block; transform: rotate(45deg)}{\Rightarrow}} \newcommand\searrow{\style{display: inline-block; transform: rotate(45deg)}{\to}} \newcommand\seEq{\style{display: inline-block; transform: rotate(45deg)}{=}} \newcommand\Id{\mathrm{Id}} \newcommand\id{\mathrm{id}} \newcommand\fcmp{\mathbin{;}} \renewcommand\epsilon{\varepsilon} \)

Different representations

Recall that a comonad on a category \(\mathcal{A}\) is a triple \((C,\epsilon,\delta)\) such that

  1. \(C\colon \mathcal{A} \to \mathcal{A}\) is a functor,
  2. \(\epsilon\colon C \to \mathrm{Id}_\mathcal{A}\) is a natural transformation,
  3. \(\delta\colon C \to C^2\) is a natural transformation, and
  4. the following diagrams commute

\[ \begin{array}{rcl} C & \overset{\delta}\rightarrow & C^2 \\ {}_\delta\downarrow & & \downarrow {}_{\delta C} \\ C^2 & \overset{C\delta}\rightarrow & C^3 \end{array} \qquad \qquad \begin{array}{rrl} C & \overset{\delta}\rightarrow & C^2 \\ & {}_{\id}\searrow & \downarrow {}_{\epsilon C} \\ & & C \end{array} \qquad \qquad \begin{array}{rrl} C & \overset{\delta}\rightarrow & C^2 \\ & {}_{\mathrm{id}}\searrow & \downarrow {}_{C\epsilon} \\ & & C \end{array} \]

Equivalently, it can be represented as a Kleisli-Manes triple \((C, \epsilon, \overline{(-)})\) (also called comonads in extension form or no-iteration comonads, cf. [1]) such that

  1. \(C\) is a mapping \(\mathrm{obj}(\mathcal{A}) \to \mathrm{obj}(\mathcal{A})\)
  2. \(\epsilon\) is a collection of morphisms \(\epsilon_A\colon C(A) \to A\), for every object \(A\in \mathcal A\)
  3. for every morphism \(f\colon C(A)\to B\) in \(\mathcal A\) we have a morphism \(\overline f\colon C(A)\to C(B)\) such that
    • (C1) \(\ \overline{\epsilon_A} = \id_{C(A)}\) for all objects \(A\in \mathcal{A}\)
    • (C2) \(\ \overline f \fcmp \epsilon_B = f\) for all morphisms \(f\colon C(A) \to B\)
    • (C3) \(\ \overline{\overline f \fcmp g} = \overline f \fcmp \overline g\) for all morphisms \(f\colon C(A) \to B\) and \(g\colon C(B) \to E\)

Here \(f \fcmp g\) is the diagramatic composition of arrows, equivalent to the more standard \(g \circ f\).


To transfer from the standard representation to the Kleisli-Manes we assign:

  • \((C,\epsilon,\delta) \mapsto (C, \epsilon, \overline{(-)}) \) where \(\overline f = \delta_A \fcmp C(f)\) for every \(f\colon C(A) \to B\)

And conversely:

  • \((C, \epsilon, \overline{(-)}) \mapsto (C,\epsilon,\delta)\) where, for a morphism \(f\colon A \to B\), the morphism \(C(f)\colon C(A) \to C(B)\) is \(\overline{\epsilon_A \fcmp f}\) and \(\delta_A\) is equal to \(\overline{\id_{C(A)}}\).

In fact, this is a bijective correspondence, cf. Proposition 1.6 in [2].

Coalgebras and co-Kleisli category

Every comonad \(C\) gives rise to two categories: the category of Eilenberg-Moore coalgebras \(EM(C)\) and the co-Kleisli category \(Klei(C)\). Note that the Kleisli-Manes axioms precisely express the fact that category \(Klei(C)\) is a category. Moreover, the category \(EM(C)\) can be also described in terms of the Kleisli-Manes liftings, see [1].

Let us state the following elementary and very useful fact.

Given an Eilenberg-Moore coalgebra \(\alpha\colon A\to C(A)\) and an object \(B\) of \(\mathcal A\), there is a bijection between coalgebra morphisms \(f\colon (A,\alpha) \to (C(B),\delta_B)\) and morphisms \(g\colon A\to B\) in \(\mathcal A\), given by the following assignments: \[ f \mapsto g_f := A \xrightarrow{f} C(B) \xrightarrow{\epsilon_B} B \qquad\qquad g \mapsto f_g := A \xrightarrow{\alpha} C(A) \xrightarrow{C(g)} C(B) \]

It is easy to see that \(g_f\) is a coalgebra morphism. We check that \(f_{g_f} = f\) first: \[ f_{g_f} = C(g_f) \circ \alpha = C(\epsilon_B) \circ C(f) \circ \alpha = C(\epsilon_B) \circ \delta_B \circ f = f \] where the second equality is the fact that \(f\) is a coalgebra morphism and the second one is one of the comonad laws for counit and comultiplication.

Conversely, given \(g\colon A\to B\), \[ g_{f_g} = \epsilon_B \circ f_g = \epsilon_B \circ C(g) \circ \alpha = g \circ \epsilon_A \circ \alpha = g \] where the third equality is naturality of counits and the third equality is the triangle law for coalgebras.

Relative comonads

A relative comonad on a functor \(J\colon \mathcal A \to \mathcal B\) is given by

  • an object mapping \(C\colon \mathrm{obj}(\mathcal A) \to \mathrm{obj}(\mathcal B)\)
  • for any \(A\in \mathcal A\) a morphism \(\epsilon_A \in \hom_{\mathcal B}(C(A), J(A))\)
  • for any \(A,B\in \mathcal A\) and \(k\in \hom_{\mathcal B}(C(A), J(B))\) a morphism \(k^*\in \hom_{\mathcal B}(C(A), C(B))\)

satisfying three conditions:

  • the left unital law: for any \(A,B\in \mathcal A\) and \(k\in \hom_{\mathcal B}(C(A), J(B))\), \(k = \epsilon_B \circ k^*\)
  • the right unital law:: for any \(A\in \mathcal A\), \(\epsilon_A^* = \id_{C(A)}\)
  • the associativity law: for any \(A,B,C\in \mathcal A\), \(k\in \hom_{\mathcal B}(C(A), J(B))\) and \(l\in \hom_{\mathcal B}(C(B), J(C))\), \((l\circ k^*)^* = l^* \circ k^*\).

For details see Relative comonads.

Comonad morphism

Given comonads \(C\) and \(D\) on categories \(\mathcal A\) and \(\mathcal B\), respectively, a comonad morphism \((F,\lambda)\colon C \to D\) is given by a functor \(F\colon \mathcal A\to \mathcal B\) and a natural transformation \(\lambda\colon FC \to DF\) such that

\[ \begin{array}{rcl} FC & \stackrel{\lambda}{\to} & DF \\ & {}_{F\epsilon^C}\searrow & \downarrow_{\epsilon^D F} \\ & & F \end{array} \qquad \qquad \begin{array}{rcl} FC & -- & \stackrel{\lambda}{---} & \to & DF \\ {}_{F\delta^C}\downarrow & & & & \downarrow {}_{\delta^D F} \\ FC^2 & \stackrel{\lambda C}{\to} & DFC & \stackrel{D\lambda}{\to} & D^2F \end{array} \]

In particular, if the two comonads \(C,D\) are on the same category \(\mathcal A\) a comonad morphism \(\lambda\colon C\to D\) is required to make the two following diagrams commute \[ \begin{array}{rcl} C & \stackrel{\lambda}{\to} & D \\ & {}_{\epsilon^C}\searrow & \downarrow_{\epsilon^D} \\ & & \Id \end{array} \qquad \qquad \begin{array}{rcl} C & -- & \stackrel{\lambda}{---} & \to & D \\ {}_{\delta^C}\downarrow & & & & \downarrow {}_{\delta^D} \\ C^2 & \stackrel{\lambda C}{\to} & D\circ C & \stackrel{D\lambda}{\to} & D^2 \end{array} \]

Note that by naturality \(\lambda C \fcmp D\lambda = C\lambda \fcmp \lambda D\).

Given two morphisms \((F,\lambda),(F',\lambda')\colon D\to C\) of comonads. A morphism of comonad morphisms \(\gamma\colon (F,\lambda) \Rightarrow (F',\lambda')\) is given by a natural transformation \(\gamma\colon F\to F'\) such that \[ \begin{array}{rcl} FC & \stackrel{\gamma C}{\to} & F'C\\ {}_{\lambda}\downarrow & & {}_{\lambda'}\downarrow \\ DF & \stackrel{D\gamma}{\to} & DF' \end{array} \]

Let's assume we have a functor \(F\colon \mathcal A\to \mathcal B\) and comonads \(C\) and \(D\) on \(\mathcal A\) and \(\mathcal B\), respectively. Then,

  1. comonad morphisms \((F,\lambda)\colon C\to D\) are in a bijective correspondence with functors \(\widehat F\colon EM(C) \to EM(D)\) such that \[ \array{ EM(C) & \stackrel{\widehat{F}}{\to} & EM(D) \\ \downarrow & & \downarrow \\ \mathcal A & \stackrel{F}{\to} & \mathcal B } \]
  2. If \(EM(C)\) has equalisers of reflexive pairs and \(F\) has a right adjoint, then any lifting \(\widehat F\) has a right adjoint.
  3. If \(F\) has a left adjoint and \(\lambda\colon FC \to DF\) is invertible, then the lifting \(\widehat F\) associated with \(\lambda\) has a left adjoint.

For details see Proposition 3.5 in [3].

Note that monad morphisms can be also defined as natural transformations of the form \(CF \to FD\) satisfying similar conditions to those mentioned above. This leads to liftings of the base functor to the Kleisli category, which commutes with free functors, cf. [4]. See also [5] for a related discussion.

Item 1 of the previous theorem admits a generalisation in the following sense. (In the language of monads:) Let \(F\) be an endofunctor and \(T\) a monad on the same category. Then, natural transformations \(F \to T\) are in one-to-one correspondence with functors from the EM-algebras of \(T\) to functor algebras of \(F\) which commute with the forgetful functors (see e.g. Proposition 5.2 in [6]).

In the situation in item 2 in the theorem above, when the comonad morphism \(\lambda\colon C\to D\) is between two comonads on the same category \(\mathcal A\), the identity functor is adjoint to itself and so the statement reduces to: If \(EM(C)\) has equalisers of coreflexive pairs, then the functor \(F\colon EM(C) \to EM(D)\) induced by \(\lambda\) has a right adjoint \(G\). (Which is often true for Regular comonads.)

The construction of the right adjoint, in terms of equalisers is a standard fact, described e.g. Lemma 3.3 in [7] (as the dual statement). Given a \(D\)-coalgebra \(\alpha\colon a \to D(a)\), the \(C\)-coalgebra \(G(\alpha)\) is computed as the equaliser of the pair of coalgebra morphisms: \[ \left(\matrix{ C(a) \\ {}_\delta \downarrow \\ C^2(a) }\right) \enspace \matrix{ \xrightarrow{C(\lambda)\circ\delta} \\[-1em] \overset{\xrightarrow{\phantom{C(\lambda)\circ\delta}}}{\quad\small C(\alpha)\quad} } \enspace \left(\matrix{ C(D(a)) \\ {}_\delta \downarrow \\ C^2(D(a)) }\right) \]

Distributive laws

These are special kinds of comonad morphisms. Let \(C,D\) be two comonads on the same category \(\mathcal A\) and let \(\lambda\colon CD \to DC\) be a natural transformation which corresponds to a lifting \(\widehat C\) such that \[ \array{ EM(D) & \stackrel{\widehat{C}}{\to} & EM(D) \\ \downarrow & & \downarrow \\ \mathcal A & \stackrel{C}{\to} & \mathcal A } \] Then, \(\lambda\) is said to be a comonad distributive law if and only if \(\widehat{C}\) is a comonad on \(EM(D)\).

There is a bijection between

  • comonad distributive laws \(\lambda\colon CD \to DC\),
  • liftings \(\widetilde D\colon Klei(C) \to Klei(C)\) such that the following diagram commutes \[ \array{ \mathcal A & \stackrel{D}{\to} & \mathcal A \\ \downarrow & & \downarrow \\ Klei(C) & \stackrel{\widetilde{D}}{\to} & Klei(C) } \] and \(\widetilde D\) has a comonad structure on \(Klei(C)\).
  • natural transformations \(\lambda\colon CD \to DC\) making the following four diagrams commute

\begin{align*} \begin{array}{rcl} CD & \stackrel{\lambda}{\to} & DC \\ & {}_{C\epsilon^D}\searrow & \downarrow_{\epsilon^D C} \\ & & C \end{array} \qquad\qquad \begin{array}{rcl} CD & -- & \stackrel{\lambda}{---} & \to & DC \\ {}_{C\delta^D}\downarrow & & & & \downarrow {}_{\delta^D C} \\ CD^2 & \stackrel{\lambda D}{\to} & DCD & \stackrel{D\lambda}{\to} & D^2C \end{array} \\[1.5em] \begin{array}{rcl} CD & \stackrel{\lambda}{\to} & DC \\ & {}_{\epsilon^C D}\searrow & \downarrow_{D\epsilon^C} \\ & & D \end{array} \qquad\qquad \begin{array}{rcl} CD & -- & \stackrel{\lambda}{---} & \to & DC \\ {}_{\delta^C D}\downarrow & & & & \downarrow {}_{D\delta^C} \\ C^2D & \stackrel{C\lambda}{\to} & CDC & \stackrel{\lambda C}{\to} & DC^2 \end{array} \end{align*}

  • There is a comonad structure on \(CD\) which is "compatible" with \(C\) and \(D\).

Also, for a distributive law \(\lambda\) (given by any of the equivalent definitions above) we have \(EM(CD) \cong EM(\widehat C)\).

This is usually attributed to Beck [8]. For details see [9] and also [10]. More references can be found on ncatlab.org.

Liftings of functors to the Kleisli category commuting with the cofree functors can be also formalised in terms of the Kleisli-Manes description of comonads, see e.g. Proposition 2.2.6 in [11].

Distributive laws with monads

See, for example, Section 5 in [3] or [9].

Comonad actions and lifting functors to coalgebras

See, Density comonads#Actions_and_lifting_functors_to_(co)algebras, for a brief overview of the dual situation.

Main sources for this are:

References

  1. ↑ 1.0 1.1 F. Marmolejo, A. Vázquez-Márquez. "No-iteration mixed distributive laws." Mathematical Structures in Computer Science 27.1 (2017): 1-16.
  2. ↑ E. Moggi. “Notions of Computations and Monads”. In: Information and Computation 93.1 (1991), pp. 55–92.
  3. ↑ 3.0 3.1 Robert Wisbauer. Algebras versus coalgebras, Applied Categorical Structures 16.1 (2008): 255-295.
  4. ↑ Tomáš Jakl, Dan Marsden, Nihil Shah: Generalizations of Bilinear Maps -- Technical Report arXiv:2205.05382
  5. ↑ Marina Lenisa, John Power, Hiroshi Watanabe. "Distributivity for endofunctors, pointed and co-pointed endofunctors, monads and comonads." Electronic Notes in Theoretical Computer Science 33 (2000): 230-260.
  6. ↑ Michael Barr. Coequalizers and free triples. Mathematische Zeitschrift 116.4 (1970): 307-322.
  7. ↑ Bart Jacobs. "Semantics of weakening and contraction." Annals of pure and applied logic 69, no. 1 (1994): 73-106.
  8. ↑ John Beck (1969). "Distributive laws". Seminar on Triples and Categorical Homology Theory, ETH 1966/67. Lecture Notes in Mathematics. 80. pp. 119–140. doi:10.1007/BFb0083084. ISBN 978-3-540-04601-1.
    Republished in Reprints in Theory and Applications of Categories, No. 18 (2008) pp. 1-303. [1]
  9. ↑ 9.0 9.1 Gabriella Böhm, Tomasz Brzeziński, Robert Wisbauer. Monads and comonads on module categories. Journal of Algebra 322.5 (2009): 1719-1747.
  10. ↑ Michael Barr. Composite cotriples and derived functors. Seminar on Triples and Categorical Homology Theory. Springer, Berlin, Heidelberg, 1969.
  11. ↑ Manes, E. and Mulry, P., 2007. Monad compositions I: general constructions and recursive distributive laws. Theory and Applications of Categories, 18(7), pp.172-208.
Retrieved from "https://kam.mff.cuni.cz/~jaklt/comonadwiki/index.php?title=Public:Comonads&oldid=3105"