It's come to my attention that the internet is lacking in monad tutorials, so I've decided to write my own. In this first, preliminary part, we'll look at different flavours of abstractions in order to explain what flavour a monad is.

I'm using "flavour" here for a bunch of things with some common properties because "class", "type", "kind" and "category" all have very specific meanings in related computer science fields and I want to avoid confusion. I am not trying to draw any kind of analogy with taste buds.

What is an abstraction?

Before we try to dive into different flavours of abstractions, let us first attempt to formalize what an abstraction is. We'll start by taking a look at the well-known "stack" abstraction.

In Java, the Stack abstraction could be defined as an interface along the lines of:

public interface StackMut<T> {
    void put(T t);
    T pop();
}

If we wanted to make it immutable, we could also define it as:

public interface StackIm<T> {
    StackIm<T> put(T t);
    StackIm<T> pop();
    T peek();
}

In both cases, there are two very important things missing from that code:

• How do we create a stack?
• What properties of these two/three functions make this a "proper" Stack?

Let us contrast these with example interfaces for the queue abstraction. Mutable:

public interface QueueMut<T> {
    void put(T t);
    T pop();
}

Immutable:

public interface QueueIm<T> {
    QueueIm<T> put(T t);
    QueueIm<T> pop();
    T peek();
}

Hopefully this should make it obvious that a Java interface does not capture the real essence of the abstraction we are trying to define here. This is not an attempt to diss Java: I don't know of any language that does it better.

Here is an example of how the same two abstractions could be defined in Haskell:

class Stack s where
  put :: s e -> e -> s e
  pop :: s e -> s e
  peek :: s e -> e
  make :: s e

and

class Queue q where
  put :: q e -> e -> q e
  pop :: q e -> q e
  peek :: q e -> e
  make :: q e

Beside the difference in syntax (things are a bit more explicit: the class Queue can be applied to a type q if we define a put function that takes a q with elements of type e and a e and returns a new q with elements of type e, and a function pop that takes a q with elements of type e and returns a q with elements of type e, etc.), the main difference here is that Haskell does let us make the constructor an explicit part of the abstraction itself. But still no visible difference except for the names.

The crucial difference between a Stack and a Queue is in the expected dynamic behaviour of sequenced calls to the methods they define. For the purpose of this blog post, we'll call this a protocol.

The protocol for stacks could be illustrated by the following example "trace":

StackMut<Integer> s = new <...>;
s.put(1);
s.put(2);
s.put(3);
s.pop(); // 3
s.pop(); // 2
s.pop(); // 1

whereas the behaviour of a queue would be:

QueueMut<Integer> q = new <...>;
q.put(1);
q.put(2);
q.put(3);
q.pop(); // 1
q.pop(); // 2
q.pop(); // 3

I am not going to attempt a formal definition of either protocol, but, informally, the stack abstraction requires that a call to pop returns the argument passed to the most recent call to put that has not yet been popped, whereas the queue abstraction requires that pop returns the argument passed to the least recent call to put that has not yet been popped.

A more complete formalization of those protocols would require addressing the case where there is no element to pop, but here we'll just gloss over that.

As a working definition, we'll say that an abstraction is composed of three parts:

• A (possibly parametric) type,
• A set of functions acting on that type,
• A protocol that defines the expected results of sequences of calls to said functions on said type.

Now, let us move on to flavours.

The thing

The first flavour we'll discuss is what I call a thing. Object would probably have been a better name here (literally "the thing we talk about"), but like kind, category, class and type, it's a bit too loaded with meaning for my tastes.

The thing is what we're talking about. When you write code using a thing abstraction, you write most of your code against that one abstraction and, even though you know there could be different implementations of it, you think of the abstraction as the thing you're manipulating.

Code that works with a stack is usually written against a Stack interface directly, i.e. with no knowledge at all of what the actual implementation will be. The abstraction is the entire thing you are concerned with.

This is the most opaque, hiding, encapsulating type of abstraction. Stacks, sets, queues and maps are usually in this category.

The temporary mask

Another common flavour of abstraction, at least in languages with subtyping, is the parent, which I'll call temporary mask. Think of the typical OO example of representing a zoo of animals with an Animal superclass and a subclass for each animal species.

In such a system, there will be some code written against the Animal type, but the vast majority of the code will want to know exactly which type of animal it is dealing with. Still, it's useful to know that the thing you're dealing with is an Animal, and you may rely on some of the Animal properties.

Another example of this flavour of abstraction is the sequence abstraction in Clojure. It has two methods (first and next) and is often used to traverse all manners of collections (and collection-like things, such as network sockets or files). In some cases you'll be writing code that really just cares about the sequence abstraction (in which case you'll treat it as the thing), but in most code we know what the real (or at least "a more concrete") type is.

This flavour of abstraction is typically used to indicate that a thing can temporarily act like another (more abstract) thing.

The extra property

Some abstractions are really just an add-on, a marker for extra properties of a thing. A typical example in Java would be the Serializable interface, which is characterized by the fact that it has no attached method.

A more interesting one for our purposes here is the AutoCloseable interface. This is an interface that only contains one method, close(). You will very rarely write any code directly against the AutoCloaseable interface, but almost any code that uses an autocloseable thing will call close() at some point.

This is also the flavour of monads. The Monad abstraction is very rarely treated as a thing, which I believe is what makes it so hard to explain and understand at first. The Monad abstraction is an "extra property" flavour of abstraction.

Monad

The monad abstraction can be defined in Haskell as:

class Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    return :: a -> m a

Unlike the other abstractions we've discussed, Monad does have a formal defintion for its protocol, which can be expressed in the loosely Haskell-like notation:

return a >>= h  === h a
m >>= return    === m
(m >>= g) >>= h === m >>= (\x -> g x >>= h)

I'll walk through the definition and protocol in more details in a future post. In this post, what I want to get across is that a monad is typically not a thing itself, but a set of properties that something else has, just like AutoCloseable.

The Java language has special syntax for AutoCloseable in the form of the so-called "try-with-resources" statement:

try (BufferedReader br = new BufferedReader(new FileReader(path))) {
    return br.readLine();
}

This is only syntactically valid because BufferedReader (the thing) also has the extra property AutoCloseable, and that makes the above semantically equivalent to:

BufferedReader br = new BufferedReader(new FileReader(path));
try {
    return br.readLine();
} finally {
    if (br != null) br.close();
}

In Haskell, Monad is similarly special. If M is an instance of the Monad type class, one can write the following code:

code_block :: M Int
code_block = do
  a <- m_add 4 5
  b <- m_add a 3
  return (a + b)

and it will be semantically equivalent to:

code_block :: M Int
code_block = m_add 4 5 >>= (\a -> m_add a 3 >>= (\b -> return (a + b)))

At this point, we know two things:

• "Monad" itself is an incomplete abstraction; it very rarely exists by itself and is generally more a set of properties that something else has.
• Haskell has special syntax for things that are monads, just like Java has special syntax for things that are autocloseable.

In the next post, I'll explain what a monad is, what its protocol means and why that might be useful.