Monads and Monoids-as-categories

500 Views Asked by At

I'm trying to understand the definition of a monad as a monoid and to identify this structure in the implementation of monads in Hakell. One definition is that of a structure $(T,\eta,\mu)$ given by an endofunctor on a cat $\bf C$ and the unit and multiplicative natural transformations. The other definition is that of a monoid in the monoidal category of endofunctors on $\bf C$.

In more concrete terms, let's consider three examples: first, the two examples of the powerset and closure endofunctors as given in this related question. For the third example I'd like to understand, let's choose the list monad as implemented in Haskell.

$\bf 1)$ In the first case, the base category is ${\bf C}={\bf Set}$, if I understand it right, with arrows given by functions $f : X\to Y$, for any $X,Y\in {\bf Set}$. The endofunctor $T$ maps $X\mapsto {\cal P}(X)$, the power set of X, and $T(f) : {\cal P}(X)\to{\cal P}(Y)$ (I assume defined as $T(f)(A)= f(A)\in{\cal P}(Y),\forall A\in{\cal P}(X)$). The unit natural transformation $\eta : 1_C\Rightarrow T$ is given by the family of morphisms $$\eta_X : (1_C)(X)\equiv X\to T(X)={\cal P}(X)$$. The multiplication natural transformation $\mu : T^2\Rightarrow T$ is $$\mu_X : {\cal P}({\cal P}(X))\to {\cal P}(X)$$

$\bf 2)$ In the second case, it is ${\bf C}={\cal P}(S)$, i.e., the power set of a of a topological space $S$, with arrows given by inclusion, i.e., $X\subseteq Y$, for any $X,Y\in{\cal P}(S)$, and $T(X)={\bar X}$ and $T(X\subseteq Y)={\bar X}\subseteq {\bar Y}$. Furthermore, it is $\eta_X : X\to {\bar X}$, which again coincides with $T$, and $\mu_X : {\bar {\bar X}}={\bar X}\to {\bar X}$.

Those examples follow the definition of a monad as stated, say, in Riehl's book (to be precise, one should still check the required commutativity conditions though). What I have troubles with is in seeing how this is equivalent to the definition of monad as "a monoid in the (monoidal) cat of endofunctors on ${\bf C}$".

I can identify the only object of the monoid in each case, namely, $T$(:$\bf{Set} \to {\bf Set}$ / ${\cal P}(S)\to {\cal P}(S)$) with the mapping of objects and arrorws in ${\bf C}$ as stated above.

What I fail to see is what the natural transformations are that act as morphisms of the corresponding monoid, and how they relate to $\eta$ and $\mu$.

I expect that following this route should provide an argument for why one needs to introduce such unit and multiplication natural transformations. That is, we would start with the monoidal category $\bf V$ of endofunctors on $C$, the binary operation given by composition. Then, we construct a monoid ${\bf M}$ in $\bf V$ by taking one specific endofunctor $T\in {\bf V}$ as the single object of ${\bf M}$. The arrows in $\bf M$ are natural transformations. One must be $1_T$ the identity, i.e., $(1_T)_X : T(X)\to T(X)$.

I guess, the fact that there is an underlying monoidal structure somehow will force us to consider an arrow (natural transformation) involving $T^2$. How to make this connection explicit?

$\bf 3)$ In the third example we have the list monad []as defined in Hakell. Here, clearly, $\mu$ is the join :: Monad m => m ( m a) -> m a function, defined as concat. In the above link it is said that $\eta$ coincides with the return function, which is return a = [a].

What are in this case the base category $\bf C$ and the endofunctor $T$? The identification with return seems to set the first question: the category of types a can't be it as [] wouldn't be an endofunctor. The Haskell wiki clarifies this: $\bf C=Hask$, the collection of all types (in Haskell), and functions between types as arrows. Thus [] is indeed an endofunctor in $\bf Hask$, and its action on functions a->b is given by fmap (or simply map).

So we have a monoid $\bf M$ with the only object the list functor T := []. Now, what are the arrows in this monoid? They have to be $T\Rightarrow T$. Are they somehow given by bind:: [a] -> (a->[b]) ->[b]? How? what are their type?

Dan Piponi's intuitive argument for constructing a monad is illuminating, but I can't see how it may help to address my point.

1

There are 1 best solutions below

12
On BEST ANSWER

I think you're mixing up two things: a monoid in a monoidal category, and the usual monoid viewed as category.

Let $\mathbf C$ be a monoidal category with multiplication $⊗$ and unit $I$. A monoid in $\mathbf C$ is an object $M$ of $\mathbf C$ together with a multiplication morphism $m : M ⊗ M → M$ and a unit morphism $e : I → M$, which satisfy certain axioms you'll easily find elsewhere. If you haven't already, check that monoids in $(\mathrm{Set}, ×)$ are the usual monoids, and write out what monoids in $(\mathrm{Ab}, ⊗)$ are; these are the basic, motivating examples.

Now as you say we look at the category of endofunctors of a category $\mathbf C$, call it $\mathrm{End}(\mathbf C)$. A monoid in this category doesn't have objects or morphisms, based on the definition above, it is an object equipped with some morphisms, it consists of:

  1. an object of $\mathrm{End}(\mathbf C)$, ie. a functor $T : \mathbf C → \mathbf C$.
  2. a morphism from $T ∘ T$ to $T$, ie. a natural transformation $μ : T^2 ⇒ T$
  3. a morphism from $1_{\mathbf C}$ to $T$, ie. a natural transformation $η : 1_{\mathbf C} ⇒ T$.

In other words, these are exactly the data of a monad on $\mathbf C$, and the axioms match too, and the two definitions are just two almost identical ways of saying the same thing.

As for your examples, they are correct, but you need to write down what the unit and multiplication are, not just their type. In the first example, the unit is given by $x ↦ \{x\}$, and multiplication is the union operation, ie. given a family of subsets $\mathcal F ∈ \mathcal P(\mathcal P(X))$, $μ_X(\mathcal F) = \bigcup\mathcal F ∈ \mathcal P(X)$.

In the second example, $η_X$ is a morphism in $\mathcal P(X)$, which is just the fact that $X ⊆ \bar X$, and multiplication is $\bar{\bar X} ⊆ \bar X$.

The third example is very similar to the first, and the maps you give are indeed the ones you want. It corresponds to the free monoid monad in mathematics, which is the endofunctor $T : \mathrm{Set} → \mathrm{Set}$ mapping a set $X$ to the free monoid on $X$.