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

This phrase appears in the hilarious A Brief, Incomplete, and Mostly Wrong History of Programming Languages, making fun of the obscure mathematical concepts in the functional programming language Haskell.

I’ve studied some category theory and I’ve programmed in Haskell, and I’ve seen this statement many times before. But I’ve never actually taken the time to break it down and see why it’s true. I just spent a couple of hours refreshing my rusty category theory knowledge and figuring it out. I wanted to write it down to make sure I actually understood it well. So… here goes.

What’s a category?

A category is simply a collection of ‘objects’ (or ‘points’) with ‘morphisms’ (or ‘arrows’) between them, satisfying two very simple rules:

  • You can compose an arrow f: A -> B with an arrow g: B -> C to get a new arrow g . f: A -> C, and this composition is associative (i.e. h . (g . f) = (h . g) . f).
  • For every object A there exists an identity arrow id_A: A -> A, such that for every arrow f: A -> B we have id_B . f = f . id_A = f.

The classical example in mathematics is the category Set, whose objects are sets, and whose arrows are functions between these sets. In the world of Haskell, we have the category Hask, whose objects are Haskell types and whose arrows are functions between these types. So, for example, Float and Int are objects, and round:: Float -> Int is an arrow.

What’s a functor?

In category theory a functor is a map between two categories. So if C and D are categories, then a functor F: C -> D will map objects in C to objects in D, and arrows in C to arrows in D. It does this in a ‘nice’ way. That is:

  • The starts and ends of arrows are mapped nicely: if f is an arrow in C from object A to B, then F(f) is an arrow in D from F(A) to F(B).
  • Identities are preserved: F(id_A) = id_F(A).
  • Composition is preserved: F(g . f) = F(g) . F(f).

Note that this concept is a bit more general than the concept of functors in Haskell (see below).

What’s an endofunctor?

An endofunctor is simply a functor from a category to itself. So in the above, assume that C = D. Note, that doesn’t mean that the endofunctor F doesn’t do anything. Just like a function from the real numbers to the real numbers might still change the numbers, the functor F might still change the objects and arrows that are fed through it in some way.

What’s a Haskell Functor?

What is known as a Functor in Haskell is actually an endofunctor on the category Hask. Recall that Hask has types as its objects and functions between these types as its arrows. So an endofunctor on Hask will map a type to some other type, and will also map functions to functions in some nice way.

This is the definition of Functor in Haskell:

{- | The 'Functor' class is used for types that can be mapped over. Instances of 'Functor' should satisfy the following laws: > fmap id == id > fmap (f . g) == fmap f . fmap g The instances of 'Functor' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO' satisfy these laws. -} class Functor f where fmap :: (a -> b) -> f a -> f b 

See the symmetry with the mathematical definition of functors above? The type constructor f fulfills the role of the functor’s action on types (objects), while fmap fulfills the role of the functor on functions (arrows).

The two classical examples of Functors in Haskell are lists ([]) and Maybe.

List is a Functor

List is a type constructor that, given some type a, will give you a new type [a], namely lists consisting of values of type a. This is the type (object) mapping part. The function mapping part is fmap (also known simply as map). Given some function f:: a -> b, it will give you a function fmap f:: [a] -> [b], namely the function that applies f to every element of a list of values of type a. You can see that fmap id is indeed the identity: doing nothing to every element of a list is the same as doing nothing to the list. The other law, fmap (f . g) = fmap f . fmap g, is also easy to see: doing g and then f to every element of a list, is the same as first doing g to every element of a list and then doing f to every element of the resulting list.

Maybe is a Functor

Maybe is a type constructor that, given some type a will give you a new type Maybe a. The values of this type are Just x, for any x of type a, and Nothing. The function mapping part fmap will take some function f:: a -> b and give you a new function fmap f:: Maybe a -> Maybe b. It will take Just x to Just (f x), and Nothing to Nothing. Can you prove the laws?

What’s the category of endofunctors?

Ok, now things are going to get a bit more tricky. First, we need to talk about natural transformations, which are basically arrows between functors. Then we’ll use this to build a category of endofunctors, and finally we’ll look at examples in Haskell.

What are natural transformations?

It turns out that if you have categories C and D, and functors F, G: C -> D between them, you can sometimes find so called ‘natural transformations‘ between the functors F and G. A natural transformation t: F => G is a family of arrows in D that satisfies two requirements:

  • The arrows t go from the results of F to the results of G. More precisly, for every object A in C, we have an arrow t_A: F(A) -> G(A) in D. This is the ‘component’ of t at A.
  • For every arrow f in C, applying F(f) first and then t is the same as applying t first and then G(f). This is the ‘natural’ part of a ‘natural transformation’. More precisely, for every f: X -> Y in C, we have t_Y . F(f) = G(f) . t_X. Graphically, it means that going around this diagram in either direction does the same thing (‘the diagram commutes’).

Of course there’s a special case where F and G are endofunctors (so C = D). There’s also nothing stopping us from setting F = G, so then we’re looking for natural transformations from a functor to itself. Just as with endofunctors, these natural transformations may still do something.

The category of endofunctors

Now, for some category C we have a bunch of endofunctors on C, and we have natural transformations between these endofunctors. We can make this into a category! So let’s introduce Endo(C), the category whose objects are endofunctors on C, and whose arrows are natural transformations between these endofunctors. You can check that composition of natural transformations is indeed associative, and that there is an identity natural transformation from every endofunctor to itself. But that’s not super relevant here.

The category of endofunctors in Haskell

Lost? Let’s think about what this would look like in the world of Haskell: what does Endo(Hask) look like? Well, its objects are endofunctors on Hask, which are simply Functors. Its arrows are ‘transformations’ from one Functor to another. So if f and g are functors, then we’re looking for some set of functions t, such that for every type a, we have a function t:: f a -> g a.

Let’s pick f = Maybe and g = []. So we’re looking for a set of functions t:: Maybe a -> [a]. Well here’s one example:

maybeToList :: Maybe a -> [a] maybeToList Nothing = [] maybeToList (Just x) = [x] 

Ok, so maybeToList is a transformation from the endofunctor Maybe to the endofunctor []. But is it natural? Well, let’s take some arbitrary function f: a-> b. If maybeToList is natural, it must satisfy maybeToList . fmap f = map . maybeToList (note that I’ve filled in map for the list’s fmap to avoid confusion). Well this is pretty easy to check:

(maybeToList . fmap f) Just x = maybeToList (Just (f x)) = [f x] (map f . maybeToList ) Just x = map f [x] = [f x] (maybeToList . fmap f) Nothing = maybeToList Nothing = [] (map f . maybeToList ) Nothing = map f [] = [] 

So yes, they’re the same! So maybeToList is a natural transformation from the endofunctor Maybe to the endofunctor [].

Another interesting natural transformation is concat:: [[a]] -> [a]. It is a natural transformation from [[]] (i.e. applying the endofunctor [] twice), to []. The naturality condition is concat . map (map f) = map f . concat.

What’s a monoid?

Ok, this one is gonna be tricky again. There’s a few different layers to this:

  • First we’ll look at the classical concept of a monoid in set theory. We’ll also look at an example of such a monoid in Haskell.
  • Then we’ll try to generalize the concept of monoids from set theory to category theory. We’ll realize that we’re missing a category-theoretic ingredient. Confusingly, this ingredient is called a ‘monoidal category’.
  • Armed with monoidal categories, we can understand a monoid in a category.

Monoids in set theory

In classical set theory, a Monoid is a set M with some binary operation •: M × M -> M satisfying the following properties:

  • Associativity: for all a, b, c in M, we have (a • b) • c = a • (b • c). Informally: “it doesn’t matter where you put the brackets.”
  • Identity element: there is some e in M such that for every a in M we have e • a = a • e = a.

An example of a monoid is the set of all finite strings over some alphabet, with string concatenation as the monoid operation. It’s easy to check that associativity holds, and that the empty string acts as an identity element.

This also gives us our example in Haskell: for every type a, the type [a] is a monoid, with ++ (concatenation) as the monoid operation, and the empty list as identity element. (Small note: technically the type [a] also includes infinite lists, for which concatenation isn’t well defined. Because of this, lists in Haskell technically aren’t monoids, nor are they monads. We will ignore this technicality in what follows.)

Monoids in category theory

Category theorists are alergic to sets. If they see a definition of a mathematical object that includes the word ‘set’, they’ll immediately start thinking about how they can rewrite this definition without using the word ‘set’. Or, more respectfully, they’ll try to generalize the definition such that it holds in categories other than Set too.

It’s obvious how to begin: the set M should be replaced by an arbitray object M in some category C. The binary operation should be replaced by some arrow μ in the category. Similarly, since we can’t ‘crack open’ an object in a category (we’d have to say what it is, and category theorists hate that), we have to replace the identity element with some arrow η going into M.

The arrow should clearly end at M, but where should it start? We need some way to construct a ‘product object’, similar to the cartesian product for sets. Turns out there’s a few different ways you can do that, but the one that’s useful for monoids is the concept of a ‘tensor product’ in a ‘monoidal category’.

Monoidal categories

The aim here is to define some operation that will allow us to combine two objects A, B in some category C into a new object A ⊗ B in that same category. The natural way to map objects in categories is through functors. But in this case we would have to map two objects into one object. We need a functor that can take two arguments.

The typical way of solving this, is by instead introducing a product space that encodes both arguments as one. So we need to have an object (A, B) in some product category C × C. At this point you may think I’m going crazy: in order to define monoids in categories we need to define products of objects, but to do that we need to define monoidal categories, but in order to that we need to define products of whole categories?!

That’s right. Luckily, it’s really quite simple. For categories C and D, the product category C × D is simply the category whose objects are pairs (c, d) of objects c in C and d in D, and whose arrows are pairs f, g: (c, d) -> (x, y) of arrows f: c -> x and g: d -> y in C and D, respectively. Composition works straight-forwardly: (f, g) . (k, l) = (f . k, g . l), with associativity easy to check. For any object (c, d) the identity arrow is simply given by (id_c, id_d).

Ok, so now that we defined product categories, the machinery of functors is available to us again, and we can start thinking about a functor ⊗: C × C -> C that combines objects (and arrows). What properties would we want this functor to posses? Well, we would certainly want it to be associative in some way: we want A ⊗ (B ⊗ C) to be ‘similar’ to (A ⊗ B) ⊗ C. This can be made precise by saying that there is a natural transformation whose components are isomorphisms α: A ⊗ (B ⊗ C) -> (A ⊗ B) ⊗ C. Similarly, we’d like there to be some identity element for , let’s call it I: we want I ⊗ A and A ⊗ I to be ‘similar’ to A. This can again be made precise by saying that there are natural transformations whose components are isomorphisms λ: I ⊗ A -> A and ρ: A ⊗ I -> A. There’s a additional conditions about these natural transformations playing nice with each other (the ‘coherence conditions’), but we’ll skip over that here.

If you compare this section to the one about monoids in set theory, you can probably spot some similarities. Instead of elements of a set, we have objects in a category; instead of a binary operation we have the functor ; instead of an identity element we have a unit object; and instead of equations involving elements of a set, we have natural transformations between functors built using . This correspondence is why the term ‘monoid’ is reused, and we this concept is called a monoidal category.

If we want to make the monoidal structure of a category C explicit, we will refer to it as the monoidal category (C, ⊗, I)

Monoids in a monoidal category

Above we defined a concept analogous to monoids. However, it’s not quite what we’re looking for; a monoidal category is a category with some additional properties. What we’re looking for is an object in a category satisfing certain properties. Namely, a monoid in a monoidal category.

We start with the definition of a monoid, and then swap out set-theoretic concepts for category-theoretic ones. This is what we get:

A monoid in a monoidal category (C, ⊗, I) is an object M with an arrow μ: M ⊗ M -> M (‘multiplication’) and an arrow η: I -> M (‘unit’) satisfying the two monoid axioms:

  • Associativity: if you have an object M ⊗ (M ⊗ M) ≅ (M ⊗ M) ⊗, it doesn’t matter if you first multiply the left side or first multiply the right side. This is made exact with a commutative diagram involving μ and the natural isomorphism α (the associator).
  • Unit is an identity with multiplication: if you have an object I ⊗ M ≅ M, then ‘forgetting’ the I using the left unitor λ is the same as first mapping to M ⊗ M using η and then to M using μ. A symmetric equation must hold for M ⊗ I using the right unitor ρ.

So how about a monoid in the category of endofunctors?

Ok, now that we know what a monoid in a (monoidal) category is, we can start thinking about a monoid in the category of endofunctors.

As we found out above, we first need to find a monoidal structure in the category of endofunctors. Turns out that’s pretty easy: composition of endofunctors satisfies all the properties of a tensor product! The tensor product identity I is simply the identity functor id. It takes a little bit of work to show that the natural transformations behave the right way, but we’ll skip over that here.

So then a monoid in the category of endofunctors is some endofunctor M, a natural transformation μ: M . M -> M (‘multiplication’), and a natural transformation η: id -> M (‘unit’), that satisfy the monoid axioms.

How can we make sense of this definition? Well, here’s one way that will carry over quite nicely to Haskell: we can think of our endofunctors as introducing some additional structure on the objects they’re applied to. The action of the endofunctors on arrows is to ‘lift’ the arrow into the structure. The endofunctor M then, is simply some chosen structure. The transformation μ (‘multiplication’) can be seen as ‘flattening’ the duplicate structure M . M down to just the structure M. The transformation η can be thought of as injecting unstructured data into the structure M.

What about the monoid axioms?

Associativity

If you have a triplicate structure M . M . M, it doesn’t matter if you flatten it down to M as (M . M) . M -> M . M -> M or as M . (M . M) -> M . M -> M. Or more succinctly, there’s a unique way to flatten layered structure.

Unit is identity with multiplication

  • If you have strucured data (M), and then use η to inject this into M again, you obtain data in M . M. You can then use μ to flatten this back down to M. This is the same as doing nothing. Symbolically, for every X, μ_M.M(X) . η_M(X) = id_M(X)
  • If you have structured data (M), and then use M(η) give structure to the ‘contents’ of your structure, you again obtain data in M . M. You can again use μ to flatten this back down to M. This is, again, the same as doing nothing. Symbolically, for every X, μ_M.M(X) . M(η_X) = id_M(X).

More succinctly: injecting structure and flattening it cancel each other out.

A monoid in Endo(Hask)

Let’s move to the world of Haskell again. As before, we look at Endo(Hask), with its familiar endofunctors of [] and Maybe and others. Let’s choose M = []. What should we pick for μ? It should be a natural transformation μ:: [[a]] -> [a]. We’ve seen one before: concat! How about η? It should be a natural transformation η:: id(a) -> [a], which is simply η:: a -> [a]. Well it’s pretty simple to come up with one:

inject :: a -> [a] inject x = [x] 

This function is also known as pure or return in Haskell.

What about the monoid axioms?

Well, for associativity we have to check that if we have some 3d list, that flattening the outer dimensions first will give the same result as flattening the inner dimensions. So: concat . concat = concat . (map concat). It shouldn’t be too hard to convince yourself that this is true.

But does our choice of unit play nice with the multiplication? We need to check:

  • Injecting a list into a list and then concatenating is the same as doing nothing to that list: concat . inject = id :: [a] -> [a]. That sounds pretty reasonable.
  • Injecting every element of a list into a list and then concatenating is the same as doing nothing to that list: concat . map inject = id :: [a] -> [a]. Again, that seems clear.

So [] is a monoid in the Endo(Hask). Or equivalently, [] is a monad in Hask. Hooray!

submitted by /u/The_JSQuareD
[link] [comments]

Published by

Nevin Manimala

Nevin Manimala is interested in blogging and finding new blogs https://nevinmanimala.com

Leave a Reply

Your email address will not be published. Required fields are marked *