A monad is just a monoid in the category of endofunctors, what's the problem?

Question

Who first said the following?

A monad is just a monoid in the category of endofunctors, what's the problem?

And on a less important note, is this true and if so could you give an explanation (hopefully one that can be understood by someone who doesn't have much Haskell experience)?

Solution 1

That particular phrasing is by James Iry, from his highly entertaining Brief, Incomplete and Mostly Wrong History of Programming Languages, in which he fictionally attributes it to Philip Wadler.

The original quote is from Saunders Mac Lane in Categories for the Working Mathematician, one of the foundational texts of Category Theory. Here it is in context, which is probably the best place to learn exactly what it means.

But, I'll take a stab. The original sentence is this:

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

X here is a category. Endofunctors are functors from a category to itself (which is usually all Functors as far as functional programmers are concerned, since they're mostly dealing with just one category; the category of types - but I digress). But you could imagine another category which is the category of "endofunctors on X". This is a category in which the objects are endofunctors and the morphisms are natural transformations.

And of those endofunctors, some of them might be monads. Which ones are monads? Exactly the ones which are monoidal in a particular sense. Instead of spelling out the exact mapping from monads to monoids (since Mac Lane does that far better than I could hope to), I'll just put their respective definitions side by side and let you compare:

A monoid is...

• A set, S
• An operation, • : S × S → S
• An element of S, e : 1 → S

...satisfying these laws:

• (a • b) • c = a • (b • c), for all a, b and c in S
• e • a = a • e = a, for all a in S

A monad is...

• An endofunctor, T : X → X (in Haskell, a type constructor of kind * -> * with a Functor instance)
• A natural transformation, μ : T × T → T, where × means functor composition (μ is known as join in Haskell)
• A natural transformation, η : I → T, where I is the identity endofunctor on X (η is known as return in Haskell)

...satisfying these laws:

• μ ∘ Tμ = μ ∘ μT
• μ ∘ Tη = μ ∘ ηT = 1 (the identity natural transformation)

With a bit of squinting you might be able to see that both of these definitions are instances of the same abstract concept.

Solution 2

First, the extensions and libraries that we're going to use:

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

Of these, RankNTypes is the only one that's absolutely essential to the below. I once wrote an explanation of RankNTypes that some people seem to have found useful, so I'll refer to that.

Quoting Tom Crockett's excellent answer, we have:

A monad is...

• An endofunctor, T : X -> X
• A natural transformation, μ : T × T -> T, where × means functor composition
• A natural transformation, η : I -> T, where I is the identity endofunctor on X

...satisfying these laws:

• μ(μ(T × T) × T)) = μ(T × μ(T × T))
• μ(η(T)) = T = μ(T(η))

How do we translate this to Haskell code? Well, let's start with the notion of a natural transformation:

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }

A type of the form f :-> g is analogous to a function type, but instead of thinking of it as a function between two types (of kind *), think of it as a morphism between two functors (each of kind * -> *). Examples:

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

Basically, in Haskell, natural transformations are functions from some type f x to another type g x such that the x type variable is "inaccessible" to the caller. So for example, sort :: Ord a => [a] -> [a] cannot be made into a natural transformation, because it's "picky" about which types we may instantiate for a. One intuitive way I often use to think of this is the following:

• A functor is a way of operating on the content of something without touching the structure.
• A natural transformation is a way of operating on the structure of something without touching or looking at the content.

Now, with that out of the way, let's tackle the clauses of the definition.

The first clause is "an endofunctor, T : X -> X." Well, every Functor in Haskell is an endofunctor in what people call "the Hask category," whose objects are Haskell types (of kind *) and whose morphisms are Haskell functions. This sounds like a complicated statement, but it's actually a very trivial one. All it means is that that a Functor f :: * -> * gives you the means of constructing a type f a :: * for any a :: * and a function fmap f :: f a -> f b out of any f :: a -> b, and that these obey the functor laws.

Second clause: the Identity functor in Haskell (which comes with the Platform, so you can just import it) is defined this way:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

So the natural transformation η : I -> T from Tom Crockett's definition can be written this way for any Monad instance t:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

Third clause: The composition of two functors in Haskell can be defined this way (which also comes with the Platform):

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

So the natural transformation μ : T × T -> T from Tom Crockett's definition can be written like this:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

The statement that this is a monoid in the category of endofunctors then means that Compose (partially applied to just its first two parameters) is associative, and that Identity is its identity element. I.e., that the following isomorphisms hold:

• Compose f (Compose g h) ~= Compose (Compose f g) h
• Compose f Identity ~= f
• Compose Identity g ~= g

These are very easy to prove because Compose and Identity are both defined as newtype, and the Haskell Reports define the semantics of newtype as an isomorphism between the type being defined and the type of the argument to the newtype's data constructor. So for example, let's prove Compose f Identity ~= f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.

Solution 3

The answers here do an excellent job in defining both monoids and monads, however, they still don't seem to answer the question:

And on a less important note, is this true and if so could you give an explanation (hopefully one that can be understood by someone who doesn't have much Haskell experience)?

The crux of the matter that is missing here, is the different notion of "monoid", the so-called categorification more precisely -- the one of monoid in a monoidal category. Sadly Mac Lane's book itself makes it very confusing:

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

Main confusion

Why is this confusing? Because it does not define what is "monoid in the category of endofunctors" of X. Instead, this sentence suggests taking a monoid inside the set of all endofunctors together with the functor composition as binary operation and the identity functor as a monoidal unit. Which works perfectly fine and turns into a monoid any subset of endofunctors that contains the identity functor and is closed under functor composition.

Yet this is not the correct interpretation, which the book fails to make clear at that stage. A Monad f is a fixed endofunctor, not a subset of endofunctors closed under composition. A common construction is to use f to generate a monoid by taking the set of all k-fold compositions f^k = f(f(...)) of f with itself, including k=0 that corresponds to the identity f^0 = id. And now the set S of all these powers for all k>=0 is indeed a monoid "with product × replaced by composition of endofunctors and unit set by the identity endofunctor".

And yet:

• This monoid S can be defined for any functor f or even literally for any self-map of X. It is the monoid generated by f.
• The monoidal structure of S given by the functor composition and the identity functor has nothing do with f being or not being a monad.

And to make things more confusing, the definition of "monoid in monoidal category" comes later in the book as you can see from the table of contents. And yet understanding this notion is absolutely critical to understanding the connection with monads.

(Strict) monoidal categories

Going to Chapter VII on Monoids (which comes later than Chapter VI on Monads), we find the definition of the so-called strict monoidal category as triple (B, *, e), where B is a category, *: B x B-> B a bifunctor (functor with respect to each component with other component fixed) and e is a unit object in B, satisfying the associativity and unit laws:

(a * b) * c = a * (b * c)
a * e = e * a = a

for any objects a,b,c of B, and the same identities for any morphisms a,b,c with e replaced by id_e, the identity morphism of e. It is now instructive to observe that in our case of interest, where B is the category of endofunctors of X with natural transformations as morphisms, * the functor composition and e the identity functor, all these laws are satisfied, as can be directly verified.

What comes after in the book is the definition of the "relaxed" monoidal category, where the laws only hold modulo some fixed natural transformations satisfying so-called coherence relations, which is however not important for our cases of the endofunctor categories.

Monoids in monoidal categories

Finally, in section 3 "Monoids" of Chapter VII, the actual definition is given:

A monoid c in a monoidal category (B, *, e) is an object of B with two arrows (morphisms)

mu: c * c -> c
nu: e -> c

making 3 diagrams commutative. Recall that in our case, these are morphisms in the category of endofunctors, which are natural transformations corresponding to precisely join and return for a monad. The connection becomes even clearer when we make the composition * more explicit, replacing c * c by c^2, where c is our monad.

Finally, notice that the 3 commutative diagrams (in the definition of a monoid in monoidal category) are written for general (non-strict) monoidal categories, while in our case all natural transformations arising as part of the monoidal category are actually identities. That will make the diagrams exactly the same as the ones in the definition of a monad, making the correspondence complete.

Conclusion

In summary, any monad is by definition an endofunctor, hence an object in the category of endofunctors, where the monadic join and return operators satisfy the definition of a monoid in that particular (strict) monoidal category. Vice versa, any monoid in the monoidal category of endofunctors is by definition a triple (c, mu, nu) consisting of an object and two arrows, e.g. natural transformations in our case, satisfying the same laws as a monad.

Finally, note the key difference between the (classical) monoids and the more general monoids in monoidal categories. The two arrows mu and nu above are not anymore a binary operation and a unit in a set. Instead, you have one fixed endofunctor c. The functor composition * and the identity functor alone do not provide the complete structure needed for the monad, despite that confusing remark in the book.

Another approach would be to compare with the standard monoid C of all self-maps of a set A, where the binary operation is the composition, that can be seen to map the standard cartesian product C x C into C. Passing to the categorified monoid, we are replacing the cartesian product x with the functor composition *, and the binary operation gets replaced with the natural transformation mu from c * c to c, that is a collection of the join operators

join: c(c(T))->c(T)

for every object T (type in programming). And the identity elements in classical monoids, which can be identified with images of maps from a fixed one-point-set, get replaced with the collection of the return operators

return: T->c(T) 

But now there are no more cartesian products, so no pairs of elements and thus no binary operations.

Solution 4

I came to this post by way of better understanding the inference of the infamous quote from Mac Lane's Category Theory For the Working Mathematician.

In describing what something is, it's often equally useful to describe what it's not.

The fact that Mac Lane uses the description to describe a Monad, one might imply that it describes something unique to monads. Bear with me. To develop a broader understanding of the statement, I believe it needs to be made clear that he is not describing something that is unique to monads; the statement equally describes Applicative and Arrows among others. For the same reason we can have two monoids on Int (Sum and Product), we can have several monoids on X in the category of endofunctors. But there is even more to the similarities.

Both Monad and Applicative meet the criteria:

• endo => any arrow, or morphism that starts and ends in the same place
• functor => any arrow, or morphism between two Categories

  (e.g., in day to day Tree a -> List b, but in Category Tree -> List)

• monoid => single object; i.e., a single type, but in this context, only in regards to the external layer; so, we can't have Tree -> List, only List -> List.

The statement uses "Category of..." This defines the scope of the statement. As an example, the Functor Category describes the scope of f * -> g *, i.e., Any functor -> Any functor, e.g., Tree * -> List * or Tree * -> Tree *.

What a Categorical statement does not specify describes where anything and everything is permitted.

In this case, inside the functors, * -> * aka a -> b is not specified which means Anything -> Anything including Anything else. As my imagination jumps to Int -> String, it also includes Integer -> Maybe Int, or even Maybe Double -> Either String Int where a :: Maybe Double; b :: Either String Int.

So the statement comes together as follows:

• functor scope :: f a -> g b (i.e., any parameterized type to any parameterized type)
• endo + functor :: f a -> f b (i.e., any one parameterized type to the same parameterized type) ... said differently,
• a monoid in the category of endofunctor

So, where is the power of this construct? To appreciate the full dynamics, I needed to see that the typical drawings of a monoid (single object with what looks like an identity arrow, :: single object -> single object), fails to illustrate that I'm permitted to use an arrow parameterized with any number of monoid values, from the one type object permitted in Monoid. The endo, ~ identity arrow definition of equivalence ignores the functor's type value and both the type and value of the most inner, "payload" layer. Thus, equivalence returns true in any situation where the functorial types match (e.g., Nothing -> Just * -> Nothing is equivalent to Just * -> Just * -> Just * because they are both Maybe -> Maybe -> Maybe).

Sidebar: ~ outside is conceptual, but is the left most symbol in f a. It also describes what "Haskell" reads-in first (big picture); so Type is "outside" in relation to a Type Value. The relationship between layers (a chain of references) in programming is not easy to relate in Category. The Category of Set is used to describe Types (Int, Strings, Maybe Int etc.) which includes the Category of Functor (parameterized Types). The reference chain: Functor Type, Functor values (elements of that Functor's set, e.g., Nothing, Just), and in turn, everything else each functor value points to. In Category the relationship is described differently, e.g., return :: a -> m a is considered a natural transformation from one Functor to another Functor, different from anything mentioned thus far.

Back to the main thread, all in all, for any defined tensor product and a neutral value, the statement ends up describing an amazingly powerful computational construct born from its paradoxical structure:

• on the outside it appears as a single object (e.g., :: List); static
• but inside, permits a lot of dynamics
  • any number of values of the same type (e.g., Empty | ~NonEmpty) as fodder to functions of any arity. The tensor product will reduce any number of inputs to a single value... for the external layer (~fold that says nothing about the payload)
  • infinite range of both the type and values for the inner most layer

In Haskell, clarifying the applicability of the statement is important. The power and versatility of this construct, has absolutely nothing to do with a monad per se. In other words, the construct does not rely on what makes a monad unique.

When trying to figure out whether to build code with a shared context to support computations that depend on each other, versus computations that can be run in parallel, this infamous statement, with as much as it describes, is not a contrast between the choice of Applicative, Arrows and Monads, but rather is a description of how much they are the same. For the decision at hand, the statement is moot.

This is often misunderstood. The statement goes on to describe join :: m (m a) -> m a as the tensor product for the monoidal endofunctor. However, it does not articulate how, in the context of this statement, (<*>) could also have also been chosen. It truly is a an example of six/half dozen. The logic for combining values are exactly alike; same input generates the same output from each (unlike the Sum and Product monoids for Int because they generate different results when combining Ints).

So, to recap: A monoid in the category of endofunctors describes:

   ~t :: m * -> m * -> m *
   and a neutral value for m *

(<*>) and (>>=) both provide simultaneous access to the two m values in order to compute the the single return value. The logic used to compute the return value is exactly the same. If it were not for the different shapes of the functions they parameterize (f :: a -> b versus k :: a -> m b) and the position of the parameter with the same return type of the computation (i.e., a -> b -> b versus b -> a -> b for each respectively), I suspect we could have parameterized the monoidal logic, the tensor product, for reuse in both definitions. As an exercise to make the point, try and implement ~t, and you end up with (<*>) and (>>=) depending on how you decide to define it forall a b.

If my last point is at minimum conceptually true, it then explains the precise, and only computational difference between Applicative and Monad: the functions they parameterize. In other words, the difference is external to the implementation of these type classes.

In conclusion, in my own experience, Mac Lane's infamous quote provided a great "goto" meme, a guidepost for me to reference while navigating my way through Category to better understand the idioms used in Haskell. It succeeds at capturing the scope of a powerful computing capacity made wonderfully accessible in Haskell.

However, there is irony in how I first misunderstood the statement's applicability outside of the monad, and what I hope conveyed here. Everything that it describes turns out to be what is similar between Applicative and Monads (and Arrows among others). What it doesn't say is precisely the small but useful distinction between them.

- E

Solution 5

Note: No, this isn't true. At some point there was a comment on this answer from Dan Piponi himself saying that the cause and effect here was exactly the opposite, that he wrote his article in response to James Iry's quip. But it seems to have been removed, perhaps by some compulsive tidier.

Below is my original answer.

---

It's quite possible that Iry had read From Monoids to Monads, a post in which Dan Piponi (sigfpe) derives monads from monoids in Haskell, with much discussion of category theory and explicit mention of "the category of endofunctors on Hask" . In any case, anyone who wonders what it means for a monad to be a monoid in the category of endofunctors might benefit from reading this derivation.

View more solutions

Comments

[Roman A. Taycher]

thanks for the explanation and thanks for the Brief, Incomplete and Mostly Wrong History of Programming Languages article. I thought it might be from there. Truly one of the greatest pieces of programming humor.

[Jonathan Sterling]

This is a fantastic explanation, but I have one question. I get that the monoidal product has type S × S -> S, but what is another example of what × is, outside of the context of functor composition? For instance, • could be multiplication or addition in the natural numbers; what is × in this context?

[Tom Crockett]

@Jonathan: In the classical formulation of a monoid, × means the cartesian product of sets. You can read more about that here: en.wikipedia.org/wiki/Cartesian_product, but the basic idea is that an element of S × T is a pair (s, t), where s ∈ S and t ∈ T. So the signature of the monoidal product • : S × S -> S in this context simply means a function that takes 2 elements of S as input and produces another element of S as an output.

[Owen]

I think the Monoid Maclane is talking about is a little more general than the one you described because the "set" is some object in some category, and the operations are morphism not necessarily defined in terms of elements. And in this particular case it is the category of endofunctors where the product of two objects (where objects are functors) is instead of being the cartesian product it is the composition of the functors... which feels pretty different though I don't have a good intuitive sense of what it means.

[Tahir Hassan]

I am confused with your definition of a monoid, specifically: "An element of S, e : 1 -> S". So e is an element of S, but then you define it as "e : 1 -> S" which means that e is a function with domain 1 and codomain S. What does this mean?

[Tom Crockett]

@TahirHassan - In the generality of category theory, we deal with opaque "objects" instead of sets, and so there is no a priori notion of "elements". But if you think about the category Set where the objects are sets and the arrows are functions, the elements of any set S are in one-to-one correspondence with the functions from any one-element set to S. That is, for any element e of S, there is exactly one function f : 1 -> S, where 1 is any one-element set... (cont'd)

[Tom Crockett]

@TahirHassan 1-element sets are themselves specializations of the more general category-theoretic notion of "terminal objects": a terminal object is any object of a category for which there is exactly one arrow from any other object to it (you can check that this is true of 1-element sets in Set). In category theory terminal objects are simply referred to as 1; they are unique up to isomorphism so there is no point distinguishing them. So now we have a purely category-theoretical description of "elements of S" for any S: they are just the arrows from 1 to S!

[Tom Crockett]

@TahirHassan - To put this in Haskell terms, think about the fact that if S is a type, all you can do when writing a function f :: () -> S is pick out some particular term of type S (an "element" of it, if you will) and return it... you've been given no real information with the argument, so there's no way to vary the behavior of the function. So f must be a constant function which just returns the same thing every time. () ("Unit") is the terminal object of the category Hask, and it's no coincidence that there is exactly 1 (non-divergent) value which inhabits it.

[Tom Crockett]

@TahirHassan So while arrows from a terminal object to an object S are not "the same thing" as S's elements, they are isomorphic to its elements, which as far as category theory is concerned is just as good.

[Yet Another Geek]

So µ is join and η is return, right? (In the world of Haskell, at least)

[Evi1M4chine]

A nice way to say it in one sentence: Monads are just pipes of (chained) “container” (content) transformations. Read “pipes of (chained)” as “monoidal”, “container” as “category”, and “… transformations” as “functors”, and you have a sentence equivalent to the quoted one. Essentially, monads are (dis)assembly lines. ^^

[Ivan Gozali]

I'm confused, since my (wrong) intuition says that monads are more abstract than monoids (since it deals with endofunctors and transformations which seem more abstract than sets and elements). But from the explanation above (which is obviously correct), monads are a "concretization" of monoids? Obviously I'm not getting this.

[dfeuer]

In the Natural newtype, I can't figure out what the (Functor f, Functor g) constraint is doing. Could you explain?

[Luis Casillas]

@dfeuer It's not really doing anything essential.

[Lambda Fairy]

@LuisCasillas I've removed those Functor constraints since they don't seem necessary. If you disagree then feel free to add them back.

[tksfz]

Can you elaborate on what it means formally for the product of functors to be taken as composition? In particular, what are the projection morphisms for functor composition? My guess is that the product is only defined for a functor F against itself, F x F and only when join is defined. And that join is the projection morphism. But I'm not sure.

[Tom Crockett]

@IvanGozali Set theory is one setting in which you can define what a monoid is; category theory is another, more abstract setting. The set-theoretic definition of monoid falls out as just one special case of the category-theoretic definition (when the category in question is Set), and monads are another special case (when the category is the category of endofunctors over another category). See the examples given here for more instances of monoids. So monoids really are the more abstract notion.

[CMCDragonkai]

The category of endofunctors is said to be a "monoidal category". Does this make the category of endofunctors itself also a monoid? If so, do monoidal categories always contain monoids as objects? Are monoids always contained in some monoidal category?

[CMCDragonkai]

Are all objects in a monoidal category a monoid? Or can some objects be not a monoid?

[Tom Crockett]

@CMCDragonkai To your first question, quoting the wikipedia page, "There is a general notion of monoid object in a monoidal category, which generalizes the ordinary notion of monoid. In particular, a strict monoidal category can be seen as a monoid object in the category of categories Cat (equipped with the monoidal structure induced by the cartesian product)."

[Tom Crockett]

@CMCDragonkai "A strict monoidal category is one for which the natural isomorphisms α, λ and ρ are identities. Every monoidal category is monoidally equivalent to a strict monoidal category."

[Tom Crockett]

@CMCDragonkai to answer your second question, no, not all objects in a monoidal category are necessarily monoids. For example, Set is a monoidal category as we observed above, but take the empty set ∅... it can't be monoidal because there can't be a unit morphism η : 1 → ∅. Recall that in the case of Set, morphisms are functions and the unit object ("I") is any one-element set.

[CMCDragonkai]

@TomCrockett thanks! Just to simplify, monoidal categories are the categorical representation of the classical monoid definition?

[Tom Crockett]

@CMCDragonkai well, the category-theoretic version is a generalization of the idea, which allows us to classify more things as monoids than the set-theoretical definition does. This is because the associativity and identity laws are given in terms of natural isomorphisms instead of simple equalities (they are equalities "up to" natural isomorphism)

[Tom Crockett]

@CMCDragonkai One way to capture the simpler set-theoretic idea of monoid in category theory is by saying it is any monoid object in the monoidal category Set, as discussed above...

[Tom Crockett]

@CMCDragonkai another, simpler way is this: a monoid in the set-theoretic sense is a (small) category with only one object. Simply think of the composition of morphisms as the monoid operation, the identity morphism on the single object as the monoid unit, and every other (endo-)morphism as another element of the monoid

[CMCDragonkai]

I am also confused at the equivalence between the eta function η : I → T and the return function in Haskell. Is the return function meant to be the eta? I don't quite see the relationship. Is eta is meant to define T as a pointed object?

[Tom Crockett]

@CMCDragonkai Yes, return is η. Remember that η is a natural transformation between endofunctors, so it is parameterized by an object (in the case of Hask, a type); its signature in Haskell would be something like η :: I a → T a. I is the identity endofunctor, so we can just write η :: a → T a, where T is your monadic endofunctor; hopefully that reminds you of the return signature.

[Tom Crockett]

Let us continue this discussion in chat.

[Tunococ]

I know this answer is old, but it bothers me to find that this popular answer provides the wrong context and wrong definition of monoid. In Mac Lane's book, a monoid may live in any category. And in the said category of endofunctors, there is no squinting required to match his definition of monoid. His monoid in the category of sets would be your (conventional) monoid. Please check the source.

[JustAskin]

"And of those endofunctors, some of them might be monads." A monad is not an endofunctor which just happens to satisfy additional properties. A monad is an endofunctor equipped with two natural transformations. This is in the same sense that a group is not a monoid which happens to have inverses for each element, it's a monoid equipped with an additional unary operation which satisfies the inverse law.

[Tom Crockett]

@barron if you really want to be pedantic you could go further and say that a monoid equipped with a unary operation which just happens to satisfy the inverse law is not a group either. It must also be equipped with the proof that said operation satisfies the inverse law! All a matter of perspective as to which requisites are part of the object language vs the metalanguage.

[JustAskin]

@TomCrockett Yes, e.g. the associator/unitor in a monoidal category, but I'm not trying to be quite that pedantic. My point is that the same endofunctor can (in some cases) be made into a monad in different ways, c.f. exotic spheres. To have an endofunctor and say "Is this a monad?" is like having a manifold and asking "Is this a differentiable manifold?" where there may exist several different non-diffeomorphic differential structures on said manifold. The phrasing "Which ones are monads?", to me, suggests that we only care about the existence of the additional data rather than its content.

[Lifu Huang]

Hi, @TomCrockett. You mentioned in comment that "for any element e of S, there is exactly one function f : 1 -> S, where 1 is any one-element set". Why? I can understand that for any element e of S, there is exactly one function (constant function) mapping from S to {e}, but it seems the f you mentioned is the other way round. IMO, there could be more than one function mapping from {e} to S. Could you please tell me where I am wrong? Thanks!

[Tom Crockett]

@LifuHuang you're right, that was incorrectly worded. What I meant was just the previous sentence: "the elements of any set S are in one-to-one correspondence with the functions from any one-element set to S", i.e. there is a bijection between S and 1 → S. The obvious bijection takes any given s ∈ S to {(e, s)}.

[Lifu Huang]

Thanks, @TomCrockett. And one more question, because I have no background in category theory. I am a little bit confused about μ(η(T)) = T = μ(T(η)). My understanding is that η is a morphism(or arrow) pointing from object I to object T (well, of course, in category of endofunctors, a morphism is a natural transformation as you mentioned). Then what does η(T) mean? what puzzles me even more is the meaning of T(η), considered T is an object and η is a morphism. Thanks a lot!

[Tom Crockett]

@LifuHuang You can read here for what the notations ηT and Tη mean: en.wikipedia.org/wiki/… ... your question made me realize that my description of the monad laws was incoherent, so I rewrote it. Unfortunately the syntactic similarity to the monoid laws is no longer as obvious; I'll have to think of a way to make that clearer.

[Lifu Huang]

Thanks again, @TomCrockett. I guess the reason why the syntactic similarity now disappear is because you describe associativity and unit of monoid in Set in terms of "element a, b, c", while there is no concept of "element" in End. But the definition of monoid in terms of "element a, b, c" is the most (and probably the only) acceptable way for newbies (like me). From my perspective, it would be great if you could, after giving the definition of monoid in Set in terms of "element a, b, c", also posts the general definition of monoid in monoidal category and then explain(cont'd)

[Lifu Huang]

how the general monoid definition corresponds to the definition of monoid in Set and also the one in End. Because most people without a background in category theory, I believe, cannot relates the definition here( en.wikipedia.org/wiki/Monoid_(category_theory) ) to their familiar definition of monoid in Set in terms of elements, not to mention to the definition of monoid in End.

[Tom Crockett]

@LifuHuang yep, you've pointed out the exact difficulty! I suspect there are no shortcuts and a satisfying explanation requires introducing the categorical notion of a monoid and showing how that specializes to Set and End respectively.

[Lifu Huang]

Well, that is indeed not easy. Thank you anyway, this is the best answer regarding monad I have ever read :)

[Lifu Huang]

Oops, one more question. Thanks to your detailed explanation, I have now understood the definition of monad in your post. But when I went back to re-learn the definition of monad in programming languages. I found the set of laws of monad (wiki.haskell.org/Monad_laws) looks different(but alike) from the one in your post. Could you please explain how these two set of laws corresponds to each other? What is the mathematical interpretation of "bind"? Thanks again.

[Tom Crockett]

@LifuHuang The best way to see how this definition relates to Haskell is to note that μ is join in Haskell, and m >>= f = join (fmap f m). Haskell's monad laws are a restatement of these laws, but in terms of of >>=. See this page for more details: wiki.haskell.org/Category_theory/Monads.

[Lifu Huang]

Thanks. So $\mu \circ F(\mu)=\mu\circ\mu$ in that page is just the same as $\mu \circ T\mu = \mu \circ \muT$ in your answer, right? $F(\mu)$ looks really weird to me, is it another standard notation?

[Tom Crockett]

@LifuHuang Yes, that's correct. The intuition behind the notation F(f) is that a functor F: C → D is a map between categories, and as such maps both objects in C (F(A)), as well as morphisms in C (F(f)).

[Tom Crockett]

@LifuHuang In Haskell, where by Functor we mean "endofunctor on Hask", a Functor maps objects of Hask to other objects in Hask. Since the objects of Hask are types, that just means a Functor instance t can be applied to a type a to yield another type t a... i.e., it is a type constructor! And the way a Functor instance t maps a function f: a -> b to a function t a -> t b is of course via fmap.

[Tom Crockett]

@LifuHuang After writing these 2 comments I realized that didn't really answer your question, because what's tricky here is that we're applying F not just to a morphism, but to a natural transformation. The intuition wrt Haskell is that natural transformations are polymorphic functions. For example, id :: forall a. a -> a is not just a morphism in Hask but actually an entire family of morphisms--a natural transformation! But fmap id :: forall a. Functor f => f a -> f a type checks just fine, and that's exactly what the notation F(μ) is about when μ is a natural transformation.

[Lifu Huang]

I see. Thanks! I really owe you a hundred upvotes :)

[mbrig]

I think I'm going to read a book on category theory and re-read this comment and answers. I have a feeling some very useful stuff is going over my head ATM.

[halfer]

"Perhaps by some compulsive tidier" - or, as we fondly refer to them on this site, a moderator :-).

[Alexander Belopolsky]

So what is your answer to the "is this true" part of the question? Is it true that a monad is a monoid in the category of endofunctors? And if yes, what is the relationship between the category theory notion of a monoid and an algebraic monoid (a set with an associative multiplication and a unit)?

[corlaez]

Amazing explanation. I am just confused in the last part. Shouldn't it be: μ ∘ Tη = μ ∘ ηT = μ (the identity natural transformation) Why does it say 1?

[K. A. Buhr]

@AlexanderBelopolsky, technically, a monad is a monoid in the monoidal category of endofunctors equipped with functor composition as its product. In contrast, classical "algebraic monoids" are monoids in the monoidal category of sets equipped with the cartesian product as its product. So, both are specific cases of the same general categorical definition of monoid.

[Daniel Wagner]

I don't think the three isomorphisms listed at the end are quite the same as saying "monoid in the category of endofunctors". In particular they don't mention join' and return' at all.

[Dmitri Zaitsev]

@AlexanderBelopolsky I have tried to explain that the answer is "yes", but with the more technical categorical notion of a monoid, when taken in the category of endofunctors of a fixed category. The easier more familiar "algebraic monoid" is a (categorical) monoid taken in the category of sets. As K.A.Buhr is saying above, you can see them as different special cases of the same general construction.