What is a Monad, Really?
Ever since I started learning mathematics I wondered what the actual fuck is a monad. I’ve been programming since high-school, and I started learning Haskell about six months before my first semester at university. Learning Haskell was quite a paradigm shift from the more traditional, imperative languages I was used too, but I eventually able to understand it enough that I could be productive with it.
I learned how to work with typical monads in Haskell, such as
[a]
and
Maybe
a
, yet I wasn’t able to
understand what that all meant in mathematical terms. Being a student of
pure mathematics, that bothered me for a while. Well, I’m happy to
say I was finally able to understand it. I’ll try to summarize my
knowledge in this article, in the hopes that it helps other people
understand what in God’s green earth is a Monad.
The Formal Definition
I suppose you could look it up in Wikipedia, but I’ll write it down in here anyways. Monads are a very special type of endofunctors — functors from a category to itself. Let be a category and let be a functor. Let and be natural transformations such that the following diagrams commute:
Then the triple — often denoted by simply — is said to be a monad. Ok, but what does this all mean?
What is a Category, Really?
Category theory can be though-of as a generalization of Set Theory: it’s a uniform language for describing sets with a given structure — those are called objects — and functions that preserves structure between such sets — those are called morphisms or homomorphisms. A category is nothing more than that: a collection of sets with a given structure together with a collection of transformations between such sets.
For example, the category of vector spaces over is the collection of all vector-spaces over , together with the collection of all linear transformations between such vector-spaces.
Note that the identity function is a linear transformation. Furthermore, if and are linear transformations, then the composition is a linear transformation. This is a key concept in Category Theory! The identity function and the composition of two morphisms must be morphisms for a suitable collection to be called a category!
In Haskell there’s only one category we care about: the category of Haskell types, whose objects are Haskell types and whose morphisms are Haskell functions.
What is a Functor, Really?
A functor is a map between categories: it takes objects and morphisms as input and returns objects and morphism from another category. In other words, a functor is a map that associates an object for each object and a marphism for each morphism in . For to be a functor it must also preserve identity — i.e. — and composition:
The idea behind this is that not only maps objects to objects — like a regular function or a morphism — it also gives us a consistent way to turn every morphism in into a morphism in .
This mechanism for converting morphisms in to morphisms in is sometimes referred-to as penetration, such as in Haskell’s standard library:
class Functor f where
-- `fmap g fa` "penetrates" `g` in `fa`.
-- A implementation of `fmap` is expected to
-- respect the composition of functions, i.e.
-- `fmap (h . g) == (fmap h) . (fmap g)`.
fmap :: (a -> b) -> f a -> fb
Note that an instance of Functor
is an
endofunctor of the category of Haskell types.
Example
Consider the map where is the power set of and — where — is the function that takes a subset of to it’s image under .
Here denotes the category of sets, where objects are sets and morphisms are regular functions. We not only know how to map a set to it’s power set, we also know to how turn every function between sets into a function between their corresponding power sets. This is the power set functor.
What is a Natural Transformation, Really?
Natural transformations are maps between functors: it takes objects as inputs and returns morphisms between the images of those objects under different functors. If are functors a natural transformation from and takes to a morphism . For to be considered a natural transformation the following diagram must commute for each and :
The idea in here is that you have natural way to convert the action of to the action of . In other words, is a morphism between and in the category of functors between and — where the objects are functors between and .
Example
Consider the maps and given by and , respectively. Here denotes the identity functor on the category of sets, i.e. is such that and . On the other hand, denotes the functor that takes a set to the power set of it’s power set. This are both natural transformation.
We not only know how to take a set to it’s power set and a function to the corresponding , we also know how to convert each element of into an element of — using the map given by — and how to flatten an element of into an element of — using the map given by . Can you see where I’m going?
What is a Monad, Really?
A monad is simply an endofunctor — a functor from a category to itself — equipped with two natural transformations and such that the following diagrams commute:
The idea is that we have natural and consistent ways of converting elements of an object into elements of and elements of into elements of — this is sometimes called flattening.
For the haskellers out there,
is return
and
is (>>= id)
. For the mathematicians
out there, return
is
and (>>= f)
is
.
Examples
The power set functor equipped with the natural transformations and given by e is a monad! In fact, all of the following diagrams commute:
Conclusion
I hope this helps someone to understand monads. Happy haskelling!