Translation of “Monads are just Monoids in the Category of Endofunctors”

If you are interested in functional programming or Haskell, you have heard about monads. If you have heard about monads, you may have heard that…

Monads are just monoids in the category of endofunctors.

I’ll use this post to translate it, and show that what monads are can be communicated just as concisely, but also more accessible to people who don’t know what ‘monoid’, ‘category’ and ‘endofunctor’ means.

First of all, what is a monoid? A type is1 a monoid if you can take the sum of values of that type, and it has a value that doesn’t change anything that’s added to it. Monoids can be written as a Haskell typeclass like this:

class Monoid m where
  (++) :: m -> m -> m
  mempty :: m

The contract of a monoid is exactly this:

for all a, b, c: a ++ (b ++ c) = (a ++ b) ++ c
for all a: a ++ mempty = a = mempty ++ a

Many types are monoids, including integers, lists, booleans, functions from a type to itself, and many more.

As you may have noticed, I reused list concatenation as monoid addition, but this makes a lot of sense, as list concatenation satisfies all the monoid laws, and no other laws.2 A more accessible way of saying that a type is a monoid is to say that it is combinable, addable, appendable or summable.

The next question is how monoids are related to monads, which leads us to the next subject, categories.

A category is an abstraction that generalizes functions to many other things, including the new pipes library, lenses and basically anything you want. It is closely related to monoids, as it has the exact same laws, but with different types and names.

While there is a Category typeclass in Haskell, it does not contain the full required power of categories. A category C is a set9, called the Ob(C) (not to be confused with objects from OOP), with a family of sets, HomC(A, B), where A and B are elements of Ob(C), and a family of mappings ∘ from HomC(A, B) * HomC(B, C) to HomC(A, C)3, and a family of identities for ∘ called IdA, which must exist in HomC(A, A). An element of Ob(C) is called a C-object, and an element of HomC(A, B) is called a C-morphism from A to B.

All of that abstract nonsense4 can be approximated with this typeclass (assuming type operators):

class Category (~>) where
  (.) :: (a ~> b) -> (b ~> c) -> (a ~> c)
  id :: a ~> a

with the laws

for all a, b, c: a . (b . c) = (a . b) . c
for all m. m . id = m = id . m

Looks familiar? That’s the monoid laws, but with different types and different names. Unfortunately, I do not know anything making them so close to monoid laws other than convenience.10 There are a few problems with Category, but one of the biggest ones is that it’s too weak to be useful. That is because nearly all useful categories have additional structure.

The additional structure we will be talking about is called a monoidal category. A monoidal category is a category that is friendly to a generalization of monoids. Unfortunately, I can’t get to monoidal categories without functors and product categories, so you’ll have to hang on there.

A functor F from the category C to the category D is a function that maps every C-object A to a D-object F(A), and every C-morphism M from A to B to a D-morphism F(M) from F(A) to F(B). A functor also has to obey some laws that makes it easier to reason about. First, an approximation of functors in Haskell (assuming multi parameter typeclasses, functional dependencies):

class (Category (~>), Category (→)) => Functor (~>) (→) f | f -> (~>) (→) where
  map :: (a ~> b) -> (f a → f b)

A functor also has to follow some laws:

for all f, g: map f . map g = map (f . g)
map id = id

An example of a functor is the [] type constructor. [] is special because it is an endofunctor; it is a functor from a category (Hask5) to itself. It is simple to implement that functor, as Prelude already has defined map for us:

instance Functor (->) (->) ([]) where
  map =

Other endofunctors on Hask5 include Maybe, IO, Parser, (->) e. As you can see, endofunctors usually represent some kind of effects (non-determinism, partiality, universe control, parsing and environment respectively).

Now, before I can write about monoidal categories, I still have to write about product categories. A product categories are in general too advanced to implement the Category typeclass shown above, so I won’t be implementing it.

A product category C×D represents two parallel categories, C and D, and a morphism in a C×D is a tuple of a C-morphism and a D-morphism. A C×D object is a tuple of a C-object and a D-object. A product category can be written as this GADT:

data ProductCat (~>) (→) a b where
  ProductHom :: (a ~> b) -> (c → d) -> (ProductCat (~>) (→) (a, c) (b, d))

This representation of product categories will not be used, as it still doesn’t make it possible to implement the Category typeclass. Instead I will use tuples (or just curried functions)

Now that we finally have both functors and product categories, we can talk about monoidal categories. A monoidal category on C is some extra structure on C. To be exact, a monoidal category also has a functor ⊗, from C×C to C, and a C-object I. ⊗ must be associative6, and I must be identity for ⊗6. I can approximate it in Haskell like this (note: ⊗ cannot implement the functor typeclass, as product categories do not implement the category typeclass):

class Category (~>) => MonoidCat (~>) (⊗) I | ⊗ -> (~>), I -> (~>) where
  prod :: (a ~> b) -> (c ~> d) -> (a ⊗ c ~> b ⊗ d)
  leftIn :: (a ~> Id ⊗ a)
  leftOut :: (Id ⊗ a ~> a)
  rightIn :: (a ~> a ⊗ Id)
  rightOut :: (a ⊗ Id ~> a)
  assoc1 :: (a ⊗ (b ⊗ c)) ~> ((a ⊗ b) ⊗ c)
  assoc2 :: ((a ⊗ b) ⊗ c) ~> (a ⊗ (b ⊗ c))

The most important part of this typeclass is prod, which is the functor ⊗. The rest are just here to enforce the associativity of ⊗ and identity of I. Implementing the monoidal category for Hask is left as an exercise to the reader. Now that we have defined monoidal categories, we can generalize monoids.

I want to remind you that most of the Haskell code so far has been approximations of the real categorical concepts, and they do not have the full generality needed for this article, as you can see by the lack of ways to define a category instance for ProductCat.

A generalized monoid M in the monoidal category C is a C-morphism ++ from M⊗M to M, and a C-morphism mempty from I to M. We can approximate this in Haskell again:

class MonoidCat (~>) (⊗) I => Monoid (~>) (⊗) I M where
  (++) :: M ⊗ M ~> M
  mempty :: I ~> M

The generalized monoid has the same laws as the normal monoid, but they look diferrent, so I’ll write them again:

for all a :: A ~> (M ⊗ M) ⊗ M:
  a . prod (++) id . (++) = a . assoc2 . prod id (++) . (++)
for all a :: A ~> M:
  leftIn . prod mempty a . (++) = a =
  rightIn . prod a mempty . (++)

Now we only have one loose end left: what is the (monoid-) category of endofunctors? First, recall what an endofunctor is: an endofunctor on C is a functor from C to C. To define the (monoid-) category of endofunctors, we need to choose what the morphisms are (as endofunctors are the objects).

It turns out that the morphisms of the category of endofunctors are what’s called natural transformations. A natural transformation φ from F (an endofunctor on C) to G (an endofunctor on C)7 is a family of C-morphisms φA from F(A) to G(A) where A is a C-object. In Haskell, a natural transformation could be represented by this higher-ranked type:

newtype NatT (~>) F G = NatT (forall a. F a ~> G a)

Natural transformations a law. This law will always be fulfilled if the functors are endofunctors on Hask, but the law is included for completeness:

for all f :: A ~> B, φ: f . φB = φA . f

I’d love to implement Category for endofunctors and NatT, but Category is still too weak.

The next challenge is implementing MonoidCat. Remember how I wrote that endofunctors are effects? Well, turns out that the product (⊗) of two effects (endofunctors) F and G can be written as the composition of F and G8, and I is just the identity functor8. Unfortunately, I can’t implement MonoidCat with those, but I can show you what Monoid would look like if the underlying category was the category of endofunctors on Hask:

class Monoid m where
  (++) :: m (m a) -> m a
  mempty :: Id a -> m a

Does that remind you of anything? Monads are just combinable effects.

1. This is actually abuse of notation. A type can’t be a monoid, it can have an instance of the monoid algebra, but that is not important for this post.
2. Another way to say that is to say that a list of a type is the free monoid of that type.
3. Note: I have reversed the usual order of composition to something sane.
4. Some mathematicians call it that.
5. Hask is the category where Ob(Hask) is the set of all Haskell types and HomHask(A, B) is the set of all functions A -> B.
6. Strictly speaking, it must be associative/identity up to natural isomorphism. That basically means that it should seem associative/identity, but might need a little push to fix the types.
7. A natural transformation doesn’t have to be between endofunctors.
8. A functor is basically a function with a type constructor. It’s trivial to compose6 both, and the identity6 is trivial for both too. Yes, it forms a category, where the objects are categories and the morphisms are functors.
9. Many sets mentioned in this article can be proper classes if the related categories are ‘big’.
10. Categories are monoidoids.

This entry was posted in Uncategorized. Bookmark the permalink.

7 Responses to Translation of “Monads are just Monoids in the Category of Endofunctors”

  1. Omar says:

    One very minor correction: it’s “monoidal category”, not “monoid category”.

  2. Pingback: Michael Tsai - Blog - What the Heck Is a Monad

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s