There are surely too many monad tutorials on the internet by now. However, I, like many before me, feel the need to try my hand at it.

In most non-duck-typed programming languages, you can define an interface, which is a set of functions of particular names and types. A type implement that interface, by implementing the function signatures the interface requires. Many types can implement the same interface. If I write functions that only interact with their inputs in terms of the interface, then I can use those functions easily on any type that implements that interface.

When mathematicians use interfaces, they call it Category Theory. They have more expressive interfaces, with more kinds of rules, because they get to use human mathematicians as their compilers. One mathematician will make up an interface, called a “category”. Other mathematicians will implement the interface for their types, by proving their mathematical objects are in the category.

The creator of the category will say what functions (“operators”) the objects need to have and set down more rules about how the operators need to work. For example, they might say that a binary operator (a function with two arguments) is commutative. + is commutative because switching the order of the arguments does not affect the out come (2+3 is the same as 3+2).

Then other mathematicians can prove things are in the category by providing implementations of the operators and proofs that they obey the rules. Membership in a category becomes useful when there are other proofs that are in terms of the category. Proving something about a category is like implementing functions that only interact with their inputs in terms of the interface. Once you prove that a new object is in the category, you know a lot more about it because you know that all the existing proofs for that category apply to your object.

##Monads

Haskell is one of the programming languages on the border between code and math. One of the things they’ve borrowed from Category Theory is the concept of a Monad. “Monad” is just the name of a particular category/interface.

A Monad is always a “generic type”, which means that it is like a List<A> in that it has another type embedded in it. A List<A> can be instantiated as a List<Int> or a List<List<String>>, and it doesn’t make a difference to the functions that work on List<A>. So, our interface is Monad<A>. A type can be either “inside the Monad” or “outside the Monad”. For example, Int is outside the Monad and Monad<Int> is inside the Monad.

In my peculiar pseudo-code, the Monad interface looks like this:

 interface Monad<A>
   fn bind(A,A -> Monad<B>) -> Monad<B>
   fn return(A) -> Monad<A>
 end

The interface for Monad<A> requires two functions. The simpler function is just a way to get a value from outside the Monad to inside the Monad. This is a poorly named function; it is called return. More concretely, the function return takes one arguments of type A and returns a value of type Monad<A>. So, return(5) would return something of type Monad<Int>.

Once things are inside the Monad, we’d still like to use our normal outside-the-monad functions on them. For example, I might have a function that takes an Int and returns some Monad<String>. Inconveniently, I have a Monad<Int>. This problem is solved by the second required Monad function, bind. This function takes two arguments. The first is a monadic value Monad<A>. (We call things “inside the monad”, “monadic”) The second is a function that takes one normal A and returns a Monad<B>. bind returns a Monad<B>.

The idea with bind is to run that function inside the Monad. The way this happens depends on the Monad.

At this point, I think some examples of Monad implementations will make things clearer.

Example 1: Maybe

The usual first example of a Monad is the Maybe type (also known as Option).

 type Maybe<A> = Some A | Nothing

This type says that if I have a value of type Maybe<A>, it will either be Some A or Nothing. For example:

• Some 5 is of type Maybe<Int>
• Some "hi" is of type Maybe<String>
• Nothing is of type Maybe<A>. It works in any context, so it could also be Maybe<Int> or Maybe<String>.

This can be a useful type for operations that might fail:

fn divide(Int top, Int bottom)
  if(bottom == 0)
    return Nothing
  else
    return Some (top/bottom)
  end
end

Some examples of using our divide function:

 > divide(3,2)
 Some 1.5
 > divide(0,2)
 Some 0
 > divide(2,0)
 Nothing
 > divide(0,0)
 Nothing
 > divide(divide(1,2),3)
 Error: divide expected an Int but received a Maybe<Int>.

That last one is unfortunate, isn’t it? I’d like to be able to chain these operations together without having to unwrap the Some values. This is where Monads come in handy!

If we want to make an existing value into a Maybe value, we’d just wrap it in Some. If we want to run a divide inside the Maybe monad, we’d just use the value inside a Some or skip the operation if we already have Nothing.

implementation of Monad<A> for Maybe<A>
  fn return(a:A) -> Maybe<A> = Some a
  fn bind(ma:Maybe<A>,f:A->Maybe<B>) -> Maybe<B> =
    if ma == Nothing
      Nothing
    else
      (Some x) = ma; //x is the value inside ma's `Some`.
      f(x)
    end
  end
end

This allows us to do things like:

> bind(divide(1,2), fn x -> divide(x,3))
Some 0.167
> bind(divide(1,0), fn x -> divide(x,9))
Nothing
> bind(divide(1,2), fn x -> divide(x,0))
Nothing

After looking at Maybe as a Monad, I felt like I understood how to define it for Maybe, but not really what was going on. Let’s try some more examples.

Example 2: List

The second least complex Monad is List.

implementation of Monad<A> for List<A>
  fn return(a:A) -> List<A> = [a]
  fn bind(ma:List<A>,f:A->List<B>) -> List<B> =
    result = []
    for elem in ma
      result = result ++ f(ma) //append the result of each call to our output
    end
    result
  end
end

Here, return just puts an element outside the Monad into a singleton list.

bind is only a little more complicated. If the list ma is empty, we’ll skip the for loop and just return []. Otherwise, for each element of the input list, we get the result of the input function f and concatenate all the results together. So, if I had a function substrings(String) -> List<String>, and a List<String>, I could call bind(mylist, substrings) and end up with a list of all the substrings of each of the strings in mylist.

Example 3: Future

This a more complex monad. The implementation details are beyond the scope of this blog post, which is partially why I am covering it.

The idea is that there is a type Future<A> which represents a promise to eventually deliver a value of type A. A Future is either in a fulfilled or unfulfilled state. If it is fulfilled, it may be successfully, with an A, or there may have been an error. In addition to bind and return, there is the idea of fn wait(Future<A>) -> Maybe<A>, which allows you to wait for the promise to be fulfilled.

While this is the first time we’ve talked about more than the minimal Monad interface functions, it is normal for implementations to have more functions that just the basic Monad ones. List<A> obviously implements a lot more functions than just bind and return. Maybe<A> also has other function, including a fn with_default(A, Maybe<A>) -> A that would make Nothing show up as another value.

On obvious place where Futures are useful is networking code. You say “I’d like to request this file from the network”, and you get a Future of that request, and then later you actually wait for the answer, when you really need to.

This is an interface for doing non-blocking I/O. For example, Jane Street’s Async library for OCaml is used for their networking, OS, and filesystem calls. Whenever you call bind or wait in the Async monad, you yield, allowing the scheduler to switch tasks. This means that other work is being done while you wait for data.

//read in a file
Future<String> foo = read_file("./hello_world.txt");
//when we've read in the file, read in the file it names
Future<String> bar = bind(foo,fn(String s){read_file(s)});
//just wait for the contents of that second file
String output = wait(bar);
//print out the contents of the second file.
println(output);

Conclusion

Monads are a cool concept. I still don’t full understand them. Category-theory heavy tutorials balanced with more practical code-focused tutorials and actually using monads is what helped me make progress.

For an explanation of why Monads are cool that uses Parser Combinators, you should take a look at this blog post by a fellow Hacker Schooler. Parser Combinators are another place where a slightly more complicated Monad is used, like Future in networking code.

Using the Async monad in OCaml was very helpful in understanding what is actually hidden in the Haskell syntactic sugar (such as is common in the IO monad).