If you're watching this video, there are
only four possibilities: you have one too many functional programming friends, you have one too many category theory friends, you already know what a monad is but you're
just itching for an argument, or, you're a bot. If you're from either of the first two
categories, you have my condolences. If you're from the third category, I'll have you know I have the power of
imprecision and ad hominem on my side. If you're from the last
category, welcome to my channel! So what is a monad? Is it a monoid object in the monoidal category of endofunctors under composition? Well... technically, yes. But, like most people, I don't
really like that definition. Ignoring the fact that most people don't
even know what this definition means, when you talk about a monoid, that gives the
impression that you're interested in its action, and in this level of generality, monoids
act on objects of the same category. However, when we talk about monads,
we're not so interested in its action as a monoid on other endofunctors.
This is why am monad is actually much better defined as an endofunctor-enriched
category with one object. As with all concepts, although the algebraic
structure is completely dictated by the axioms, the axioms are completely dictated by how we
intended to use the object in the first place. In particular we shouldn't
be asking what a monad is, but rather we should be asking what
a monad is supposed to be used for. So how is a monad supposed to be used?
Well, it depends. In case you are worried, let me assure
you that I am not a functional programmer. Before we talk about monads, we need
to talk about a much more fundamental disagreement between mathematicians and
computer scientists: the humble function. On the surface level, functions just take
inputs from one domain into outputs in another. "How can mathematicians and computer scientists
disagree on something so simple?" I hear you ask. Well, let me ask you: if g(1)
equals 5 then what is g(1)? If you said 5, then I'm afraid
you might be a mathematician. The thing is, functions in the context of
imperative programming have the ability to affect the global state of the program.
Take the function below, for example. At first, calling callme() with a
value of 5.0 will result in 5.0. But then, immediately afterwards, if
I call callme() with a value of 5.0, I'm going to get not 5.0 but 6.0.
This is because callme() is not only dependent on its argument, but is also implicitly
dependent on the global variable num_calls. A function in the context of mathematics
cannot have any Earthly tethers. Accordingly, computer scientists
refer to such functions as "pure". Any function can be made pure if it repents
and makes its dependencies explicit. For example, we can make callme() into
a pure function by adding an explicit dependency on num_calls and also output
its effect on numb calls in the output. In general, if you have an impure function
foo that takes an input of type X and yields an output of type Y, but it implicitly
depends on the global state of type S, then you can view foo as a pure function by
writing it down as a function of X and S, and yielding an output pair consisting of the original
output Y and a modification of the state in S. The transformation T that sends the output type
Y into the type of functions from S into pairs Y x S is called the "state monad", which is used
to encode that a function outputs a value of type Y and also has a computational
effect on the global state in S. Let's look at another example.
As they say, to err is human, and to forgive impure.
Consider the function below. Although this function does not depend on
any global state, a thrown exception will lead to an effect on the global state once
it gets handled or if it crashes the program. Of course, we can make this into a pure function
by modifying the return value so that it indicates if an error would have happened originally.
More generally, we can modify a function foo to account for exceptions by extending its output
type Y to have a new element to indicate an error. The transformation T that adjoins a new element
to a type Y is called the "maybe monad", and is used to encode that a function may
output Y, but may also throw an exception. The common denominator among monads
is that monads extend a type to encode some additional computational effects.
Therefore, a function f from X to Y with that kind of computational effect can instead
be viewed as a pure function from X to T(Y). Now we can revisit how a monad is really defined. If a monad T is supposed to extend types,
then for every type Y we had better have some kind of map "ret" from Y to T(Y).
We can then use this mapping to view Y as the portion of T(Y) where there
are no computational effects. To understand the second ingredient of a
monad, consider the function is_pos below, which just checks if a number is positive.
The function by itself is pure, but if I compose it with divide, then it may throw an exception.
"fmap" encodes how pure functions have no influence on the computational
effects at their input. The last ingredient of a monad encodes
how to compound computational effects. For example, if we compute the division
of a with the division of b and c, then an exception may occur in two places,
but as far as the composite is concerned, it doesn't matter where that exception occurred. And there you have it: a complete ingredient
list for a monad in functional programming. The role of monads in mathematics
is to encode algebraic structure. To help this make more sense, let's
consider the monad for linear algebra. The only operations that count as linear
are scaling and tail-to-tip vector addition. If we mix and match these operations, we
can get arbitrary linear combinations. Any set that supports linear combinations
is known in the business as a vector space. While this gives the impression that
everything in a vector space comes with a direction and a magnitude, really anything
with the well- defined notion of scaling and addition counts as a vector space.
Of course, linear combinations don't make sense on a general set.
For example, consider the set of suits: what would 3 * clubs - 1/2 * hearts even mean?
Luckily for us, math doesn't require us to have an understanding: if we can write
it down, we can make a set out of it, so let's let T(X) denote the set of all
formal linear combinations of elements of X. "Formal" in this case means that we don't care and
we probably also don't don't know what this means. Even though 3 * clubs - 1/2 *
hearts doesn't make any sense in X, it does make sense in T(X),
and that's good enough for us. While formal linear combinations
aren't real and can't hurt you, there are some linear combinations that
look eerily like the elements of X. These are the astral projections of real elements
of X picked out by the unit map of our monad T. While we generally cannot make sense of
linear combinations in X, we can make sense of linear combinations of
linear combinations in T(X). For example, if we take u to be the linear
combination 3 * clubs - 1/2 * hearts, and take v to be a different linear combination
4 * clubs + 3 * spades, then the linear combination 2 * u + v in T(X) makes sense.
In other words, we can describe a map mu which takes a formal linear combination
of formal linear combinations and realise it as a single linear combination.
This is the purpose of the monad multiplication. For a general monad encoding algebraic structure,
the unit identifies which expressions are supposed to do nothing, while the multiplication explains
how we can combine expressions in this language. So, if T is the monad that formally gives linear
algebraic structure to a set, then what happens if the set already has linear algebraic structure?
Suppose X is the three-dimensional vector space R^3.
In this case, what is T(X)? Well, this is a trick question: T doesn't
care if X already had linear combinations; it's going to completely ignore it and
add formal linear combinations instead. For example, the formal linear combination 2
* (1, 0, 1) - (2, 2, 1) is not equal to (0, -2, 1) in T(R^3), even though they
evaluate to the same vector in R^3. So what's going on?
It seems that T just completely destroys any algebraic structure that's already there!
Well, this is completely by design: T provides us a way of talking about linear combinations on
X without worrying about what they actually mean. If we want to talk about what a linear
combination means in X, then what we have to do is define a function alpha from formal
linear combinations into real linear combinations. This function is called a T-action, and a set
equipped with a T-action is called a T-algebra. In general, a T-action is a way
of taking formal expressions and interpreting them in the original set.
For example, using the vector space structure in R^3 gives us a canonical T-action,
and using that T-action, we see that 2 * (1, 0, 1) - (2, 2, 1) can be viewed as the
same as (0, -2, 1) in the T-algebra. Conversely, we can use any T-action to
obtain a vector space structure on a set. In particular, we see that vector spaces are precisely the algebras for
the linear algebra monad! Now we know that a monad in computer science is
a paradigm for encoding computational effects, whereas a monad in category theory is a
paradigm for encoding algebraic structure. Despite this difference in usage, the
underlying structure of a monad in both cases is the same... but why is that?
This boils down to how a monad's purpose is to append formal language onto an object.
Mathematics interprets this language as algebraic expressions, whereas computer science
interprets this language as computational effects. So despite them both having
the same general principle, why do monads feel so different in
computer science as opposed to mathematics? I could be cheeky and just say that it's because
mathematicians have no idea how to program, and programmers have no idea how to do
mathematics, but there's another explanation. If we start with the category of sets,
and the pure functions between them, and I give you a monad, then there's two ways
you can use that monad to build another category. If you're a functional programmer, then
the category you're interested in is the category of sets where the maps between
them carry additional computational effects. In other words, you're interested in
the category of sets where the maps from X to Y are the pure functions from X to T(Y). This is called the Kleisli
category associated to the monad. If you're a mathematician, then you would be more
interested in the category of all T-algebras, where the maps between them are the functions
of underlying sets that respect the T-action. This category is called the Eilenberg-Moore
category associated to a monad. Although both categories seem quite different
at face value, it turns out that the Kleisli category embeds fully faithfully
into the Eilenberg-Moore category. This embedding associates to a set X
the T-algebra T(X), where the action is induced by the multiplication of the monad.
In other words, the embedding associates to X the T-algebra that is freely generated by
X, where "free" means "no relationships". "Just like in real life," said
the coping category theorist. For this mapping to be functorial,
we need to associate to any Kleisli map X to T(Y) a map T(X) to T(Y).
In functional programming terms, we do so by combining fmap with join---the
combination also being known as the "bind" map. "bind" is the secret ingredient
that functional programmers use to write sequential code using monads. The punchline is that the Kleisli
category from functional programming is nothing but the full subcategory of
the Eilenberg- Moore category consisting of those T-algebras that are freely generated.
If you think about it, this makes a lot of sense, because mathematicians tend to have
very interesting relationships, whereas functional programmers
are most often maidenless. Now, if you're in the comment section typing away
that vector spaces are always freely generated, I want you to stop right there and realize
that you just assume the axiom of choice. To all the non-haters, if I
reach 1 million subscribers, I'll reveal the special-edition Vector Space
Without A Basis that I leave in my closet. If you're still here, thank you for watching!
If you like what you saw, I'm sure there's a way you can express that somehow.
If you didn't like what you saw, well, that's cool man, I'll always
have one fan who's got my back.
