```What is a Monad?
================

A monad is a monoid in the category of endofunctors.

That's usually given as a joke answer, but it's true. And I think it's the
proper way to explain what monads are and why they're useful.

First, let's go over what a monoid is. A monoid has three components:

- A category
- An associative binary operation on that category
- An "identity value" for the operation

The easiest example is addition on the natural numbers. Here, the identity
value is 0, because adding 0 to any number does not change it. Also note that
addition is an associative operation; that is, (1 + 2) + 3 = 1 + (2 + 3).

Similarly, multiplication is a monoid with identity value 1. However, we can
easily show that subtraction and division are not monoids, because they are
not associative: (1 - 2) - 3 ≠ 1 - (2 - 3).

Given this definition, we can easily construct our own monoid. For example,
our category could be shopping lists, with the identity value being an empty
list. Our binary operation will be to take two lists and merge their elements,
deleting any duplicate items. You can verify for yourself that this operation
is associative.
The point is: monoids aren't just a mathematical oddity, they're an
abstraction that we can use to our advantage. As an example, we can define a
fold function (also known as reduce) on any monoid. Start by setting an
"accumulator" variable to monoid's identity value. Then successively apply the
monoid operation to the accumulator and each element of the input list. With
addition, this yields the sum of the list. With multiplication, it yields the
product. And because monoids are associative, fold is "embarassingly
parallel:" we can split the list into any number of groups, fold each group,
in a separate thread, and then fold the results.

Now the only missing piece is endofunctors. Once we understand endofunctors,
we'll have a complete picture of what a monad is. In category theory, a functor
is a mapping from one category to another. For example, when you turn the dial
on your stove, you're mapping the category of rotation to the category of heat.
An endofunctor is a special case: it's a mapping from a category to itself.
Thus, most of the mathematical functions you're familiar with are endofunctors:
they map one number to another.

Now we can turn to programming. In functional programming, we generally only see
one kind of monad: those whose endofunctor's category is types. In other
words, throw out the term "endofunctor," and replace it with "a mapping from one
type to another" -- i.e. a (pure) function! So in the context of programming, a
monad is just a monoid in the category of functions. So now we have a rough idea
of what a monad looks like. It's a category (functions from type A to type B),
an operation that composes two such functions, and an identity function.
Generally, the tricky part is the composing. We need to take two functions with
signature A -> B, and produce a new function with the same signature.

Let's make this more concrete by implementing a monad in a language that isn't
Haskell. Our monad's category will be functions that take an integer and return
a pointer to an integer. In Go syntax, that's:

func foo(x int) *int

We'll compose our functions like so:

func compose(f, g func(int) *int) func(int) *int {
return func(x int) *int {
fx := f(x)
if fx == nil {
return nil
}
return g(*fx)
}
}

Now the only thing missing is an identity function. Remember, when we compose
some function f with our identity function, the result should be the same as
calling f directly. So our identity function is simply:

func identity(x int) *int {
return &x
}

So, what is this monad we just created? What is it useful for? Well, we can use
it to chain together lots of functions that can fail, without having to check
for nil over and over again. Instead, our chain will "short circuit" as soon as
a function returns nil. Compare:

x := foo(0)
if x != nil {
y := bar(*x)
if y != nil {
z := baz(*y)
}
}

vs:

foobarbaz := compose(foo, compose(bar, baz))
z := foobarbaz(0)

type-safety, and it works with any type (not just int), but the basic idea is
the same. Other languages, e.g. Rust, often have types like Option that work
similarly.

There's a particular point that I want to stress here, because it confused my
they're actually referring to two things working in tandem. First is the Maybe
data type, which in Haskell is defined as:

data Maybe a = Nothing | Just a

Second is the monad instance that is defined, somewhat arbitrarily, on this type:

return        = Just
Nothing >>= _ = Nothing
Just a  >>= f = f a

Do you see why this is arbitrary? This isn't the only monad that can be created
from the Maybe data type. For example, we could have made a monad that always
returns Nothing. It wouldn't be useful, but it would still qualify as a monad.
Or, returning to monoids, consider that both addition and multiplication are
monoids for the type Int. If we had to declare instance Monoid Int, which one
should we use? The decision would be arbitrary.

In practice, you typically start by imagining a useful monad, then you define a
data type that implements it, not the other way around. For example, what if we
want something like Maybe, but with the ability to propagate error values
instead of Nothing? By tweaking our definition of Maybe, we could come up with:

data Either a b = Left a | Right b

return        = Right
Left  l >>= _ = Left l
Right r >>= k = k r

Which is indeed a real monad in the Haskell standard library. (The Go equivalent
of Either is (int, error); the Rust equivalent is Result.)

Finally: why are monads such a big thing in Haskell, and not any other
mainstream language? There are two reasons: first, Haskell is really strict