1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think there's a misunderstanding here on what a natural transformation is. In your first example, you state correctly that $η$ is a natural transformation $1_{\mathbf C} ⇒ \mathcal P$. This means that $η_X$ is a function $X → \mathcal P(X)$, which is in this case given by $η_X(x) = \{x\}$, for every $x ∈ X$. You write instead that $η_X$ coincides with $T$, which doesn't really make sense. A natural transformation is not a functor, it's a family of morphisms. $\endgroup$ – user54748 May 20 '16 at 0:57
  • $\begingroup$ @user54748 I just meant it in the sense that, as a mapping restricted to $X$, its type looks the same, namely, $X\to {\cal P}(X)$. But you are right, I glossed over those details without paying enough attention. Do the commutative diagrams enforce that $\eta_X(X)$ be just the set of its singletons? $\endgroup$ – MASL May 20 '16 at 2:29
  • 1
    $\begingroup$ What do you mean by a mapping restricted to $X$? And the type is not the same, $η_X$ is a function $X → \mathcal P(X)$, and $T$ is functor $\mathbf C → \mathbf C$. Those are very different things. What $η$ is is part of specifying the monad structure on $T$. Checking if the commutative diagrams are satisfied for a certain definition of $η$ is another. $\endgroup$ – user54748 May 20 '16 at 2:52
  • $\begingroup$ I mean, for an object $X$, the unit $\eta : 1_C\Rightarrow T(X)$ is given by the morphism $\eta_X : 1_C(X)\to {\cal P}(X)$, i.e., $\eta_X : X\to {\cal P}(X)$. The action of the endofunctor $T:{\bf C}\to{bf C}$ on objects $X$ is $X\to{\cal P}(X)$... Uhm...I think I can't write such a thing as it's not a function, but only that $T(X)={\cal P}(X)$, i.e., $X\mapsto{\cal P}(X)$ under $T$. I think glossing over this distinction is what lead me to compare $\eta_X$ and $T(X)$. I will edit my post to correct that. In any case, I think it doesn't affect my question. $\endgroup$ – MASL May 20 '16 at 3:22
4
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Let's denote a Monoid, with capital M, as category and monoid (lower case) the algebraic structure of a set with a binary, associative internal operation that has a unit. From Baez's Cat Theory course notes (available at nLab and his Azimuth site), he seems to define a Monoid simply as a 1-object X cat. Its homset, hom(X,X) with composition forms a usual monoid. Thus a Monoid still has morphisms, namely, hom(X,X). In page 5, footnote 9, of Riehl's book, she states that a monoid (lower case) is precisely a 1-object cat. Does she mean that a monoid can always be viewed as acting on something... $\endgroup$ – MASL May 20 '16 at 10:53
  • $\begingroup$ ...and thus, that something together with the monoid, form a Monoid? It makes sense to me, although I don't see what a 1-object cat say (${\mathbb Z},+)$ may be. In any case, a monoidal category is then simply category with an additional structure mimicking that of a monoid (lower case). So far I seem to have it clear. I don't see yet, what you mean by "a monoid in this cat doesn't have objects". Are you saying a Monad is a monoid (not a Monoid) in the cat of endofunctors on $\bf C$? $\endgroup$ – MASL May 20 '16 at 11:08
  • 1
    $\begingroup$ As I said, you're dealing with two different things here: 1. monoids (ie. the standard notion of them), which are indeed almost the same thing as one object categories, and 2. monoids (or more precisely called monoid objects) in a monoidal category, which is a distinct and more abstract notion. The first definition can not in any way be used for what you want: you can't have monoids-as-categories in a monoidal category. The objects of End(C) for example are functors, not categories with objects and morphisms, which is exactly what you were having trouble with. $\endgroup$ – user54748 May 20 '16 at 11:29
  • 1
    $\begingroup$ @MASL ... so yes, as you say in your third comment, there is a third notion of monoid - a monoid object in a monoidal category. The first two are more or less the same, the third is more general (it subsumes standard monoids: they are exactly the monoid objects in (Set, $\times$)). You can read the precise definition of the relevant concepts (monoidal categories and monoid objects in them) in many places, even on Wikipedia; ask if something is still unclear afterwards. $\endgroup$ – user54748 May 20 '16 at 11:34
  • 1
    $\begingroup$ @MASL: that's quite true, and it never occurred me someone would interpret "a monoid in the category of endofunctors" in that way, but it makes sense if you weren't familiar with the intended meaning. What you describe is what you'd call simply "the monoid of endomorphisms of T", because that's exactly what it is. Every object of every category has an endomorphism monoid, as you note; it's not a special property, but monad on the other hand is a very special kind of endofunctor. $\endgroup$ – user54748 May 20 '16 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.