Before Jumping into Monads

A lot of people come from popular languages that tout being "object-oriented" and they hear about something called "monads" but haven't found the time to figure them out completely. They look for a simple explanation, but run into one or more of the following problems:

too many concepts explained at once
vague explanations (including analogies that break)
inaccurate explanations (or so they're told)

So I'd like to try to do what everyone else should have done -- not have a monad tutorial, and instead address specifically some problems that most people seem to face.

Assumptions and goals

I don't want to assume you know too much, but as a starting point I'll assume

you come from a traditional "object-oriented" language
you've seen a type system with interfaces and type polymorphism (Java and C# call these "generics").

If I do my job well enough, you should understand

what type classes are, which is a language feature we can use to define monads
why some type systems have a concept of kinds and why that can be important for defining type classes
a functor as an example of a type class
some pointers on what's left to understand a monad.

The greatest part of OO

OO very confusingly doesn't have a formal definition that everyone agrees upon. I personally subscribe a particular definition of objects as implementations of interfaces, which I find gives objects useful properties:

They can be implemented by everybody (the person defining the interface or a client using the interface).
We never assume to know how many implementations are out there.
When given an instance of the interface, we don't even know what kind of instance it is -- just that it satisfies the interface.
The interface has a contract -- invariant laws that hold true universally for every instance of the interface.

Start thinking about that last point for all the interfaces you've ever used. What are the contracts? Are they very compelling?

These concepts from OO relate to type classes, and I mention them to bridge something familiar to something new.

The greatest part of FP

If you haven't heard it before, I want to be clear that there's nothing making it hard to mix OO with FP if you define objects just as simply as I did above and completely ignore subtyping and encapsulated mutable state. Subtyping creates a myriad of academic frustrations. Mutable state is even worse -- it's definitionally contrary to the highest principles of FP. We simple can't have it. And concepts like type classes will have broken contracts if we have side-effects.

So we can't have an interface for a list like this:

interface List<A> {
  void add(A a);
  ...
}

Because that implies we we're going to mutate our list. Instead, we need to have immutable lists with an interface like

interface List<A> {
  List<A> add(A a);
  ...
}

which returns a copy of the original list with the new element added. If we don't do this, we miss out on something people refer to as referential transparency which means we can replace expressions with their evaluated values. We do this all the time with arithmetic. We can always replace any occurance of 1 + 2 + 3 with 6. FP allows us to do this with function calls without worrying about side-effects getting in the way. Referential transparency allows us to liberally refactor our code to an extent we couldn't otherwise.

Also, we're going to have very strong contracts on our interfaces that will survive all this refactoring. This is going to help us reason about our code by just looking at our code (statically) rather than having to (dynamically) run our code to see if our contracts hold.

Mapping lists

Let's consider a "map" function that you may have seen before. It runs a function on all elements of the list, returning a new list with the results in order.

interface List<A> {
  ...
  List<B> map(Function<A, B> f);
}

What kind of contract can we guaranteee here? There's a simple one that if we have an identity function (Function<A, A>) that just passes the input through to the output, then we always have:

list.map(identity) === list

This is called the identity law

Also, if we have two functions, f and g, and a list:

Function<A, B> f;
Function<B, C> g;
List<A> list;

then we always have the following:

list.map(f).map(g) === list.map(f.andThen(g))

This is called the composition law.

I'm not going to prove rigorously that these two laws always hold for a list, but see if you can think about why these laws always hold in your head.

A lot of OO programmers would stop here -- a useful method (map) on a useful data structure (list). But let's keep going. Let's look at something really different from lists, and see if we can find something similar to this map function. And what will be really nice is if we can abstract away something general we can reuse.

Switching to Functions

Let's look a little more at the interface for a function specialized to take integers as an input:

interface IntFunction<A> {
  A apply(Integer i);
  IntFunction<B> andThen(Function<A, B> f);
}

The apply method is just the requist method we need to run our function and get a result. Take a closer look at the andThen method. It's remarkably similar in structure to the map method we defined for List above. In fact, let's look at them side by side:

interface List<A> {               |   interface IntFunction<A> {
  ...                             |     ...
  List<B> map(Function<A, B> f);  |     IntFunction<B> andThen(Function<A, B> f);
}                                 |   }

They almost have the same signature, except for one is for List, and the other is for IntFunction. So let's put a method called map on IntFunction that just delegates to andThen:

interface IntFunction<A> {
  ...
  IntFunction<B> andThen(Function<A, B> f);
  IntFunction<B> map(Function<A, B> f);
}

But what's really interesting is that both our identity law and our composition law seem to hold for IntFunction:

intFunc.map(identity) === intFunc

intFunc.map(f).map(g) === intFunc.map(f.andThen(g))

Again, I'm not going to formally prove this, but please take a moment to reason in your head that this is true.