What's a monad?

A practical monad

Say, we have an object, and we want to apply some operations to it. To save lots of parenthesises we can write more conveniently using infix notation:

let inc i = i+1
let sqr i = i*i
let _ =
  (* compute (2+1)^2 *)
  2 |> inc |> sqr

Note that mathematicians often write function composition the other way around, but let's not bother about that today. And if you're familiar with the Unix commandline, try comparing |> with the shell's pipe operator.

$ ls | sort -n`

Here's the challenge: Suppose we want to wrap integers in some sort of container, say an int option, then how would we need to change our example code?

Ocaml's int option type has an element None, and one element for every integer, like for example Some 3. Now we know enough to write some code which takes an int option and calls a given function on the integer, if any:

let bind o f =
  match o with
  | Some x -> f x
  | None -> None

If you look closely, you'll note that f will also have to return an option. Let's introduce a function named return as shorthand for wrapping something in a container.

let return x = Some x
let return_none = None

With that we can tidy up our example to look like this:

let inc i = return (i+1)
let sqr i = return (i*i)
let _ =
  bind (bind (Some 2) inc) sqr

We can, once more, get rid of the parenthesis using an infix operator:

let (|>>) = bind
let _ =
  (Some 2) |>> inc |>> sqr

That's pretty close, right?

There's another way to put it, which emphasizes a close relationship to let statements. Notice how inline-defining a function for every call to bind introduces a new named value:

let _ =
  (Some 2) 
  |>> fun i -> (Some (i+1))
  |>> fun j -> (Some (j*j))

Ocaml has a syntax variant for that! It works by defining a magic infix operator (let* ) which can then be used in a way similar to let..in:

let (let* ) = bind
let _ =
  let* i = Some 2 in
  let* j = Some (i+1) in
  Some (j*j)

Note: since Ocaml denotes comments like this: (* comment *), I needed to add an extra space to not accidentally close a comment there.

Why return t?

You might wonder why the signature of bind says that the function given to it should return a container object:

val bind: 'a t -> ('a -> 'b t) -> 'b t

Wouldn't it be more natural to have that function simply return an object 'b? And also, why isn't the function the first argument, so we could convert a function which works on objects into a function which works on containers?:

val map: ('a -> 'b) -> 'a t -> 'b t

Or maybe bind isn't about applying a function to a lot of objects, perhaps it's about applying many functions to the same object instead...

Still, why does bind only do half the work, unpacking 'a t, but not wrap up f's result again?

Here's a practical reason: Let's talk about lists. We can filter a list using a predicate, or we can map a list's elements using a function. What about this: a function returning an option could signal wether it wants to map a given value to some other, or to remove it altogether. It is simply more general to let it return a container!

There's also a theoretical reason: category theory is about mapping things, and a monad is actually a functor, and the function needs to return a functor... See below for details.

And in some practical sense it's just arbitrary. There are a few different ways to define monads, and I believe the above is popular in education, because it gives an opportunity to talk about categories and the deeper meaning of monads. But there are alternatives. Read on...

Links

Sanjiv Sahayam on his blog "Babylon Candle": "A Simple Reader Monad Example": https://blog.ssanj.net/posts/2014-09-23-A-Simple-Reader-Monad-Example.html

Applicative functors

An applicative functor is a somewhat simpler alternative to a monad. Here's the signature right away:

val pure: 'a -> 'a t
val apply: ('a -> 'b) t -> 'a t -> 'b t

Again, think of the type 'a t as a kind of container. Then pure x could create that kind of container with a single object in it. In addition we get apply ft xt which can be used to apply functions in one container to the objects in another container, returning yet another, new container with the result.

The key difference is that apply decides how to wrap f's result, which is why f is required to return an actual value. That's the reason it's called static binding in contrast to monads which bind dynamically. Applicative functors are less general.

But wait, apply takes functions in a container! That's not too bad, as it is easy enough to get one by writing (pure f) instead of f, but... why?

In this case it turns out that the duo pure and apply are actually equivalent to the more traditional map operation, which applies a function to every element of a list, together with a product, which produces all possible pairs:

let map f l = List.map f l
let product al bl =
  List.fold_left (fun ret a ->
    List.fold_left (fun ret b ->
      a,b
    ) ret bl
  ) List.empty al

Like so:

let pure f = [f]
let apply fl l = List.map (fun (f,x) -> f x) (product fl l)

Here's a cool example:

let (<*>) = apply
let _ =
  pure (fun a b -> print_int (a+b); print_endline "")
  <*> [1;2;3]
  <*> [40;50]

This will call the given print function with all combinations of elements from the first list as first argument with elements from the second list as second argument. This works for any function,

Links

Joel Björnson, "More type classes in OCaml": http://blog.shaynefletcher.org/2017/05/more-type-classes-in-ocaml.html

The theoretical monad

A monad is a categorification of a monoid. We can describe a monoid providing three bits of data $(M,\otimes,1_M)$ , a set of objects $M$ , an associative operation $\otimes$ , and an element $1_M$ which is an identity with respect to $\otimes$ . A monoid is similar to a group, but we don't require inverses.

Categorification means that we replace $M$ with a category $C$ , and come up with maps to generalize operation and identity: $\eta: 1 \rightarrow C$ is the identity, and $\mu: C \rightarrow C$ the operation. That eta is a fancy e borrowed from the german word "Einheit", and mu is a kind of "m" in allusion to "multiplication".

How is that more general? For one, when we map a constant somewhere like $\eta$ does, that has the effect of selecting an element of $C$ .

It is what return does.
map morphisms
works for any category $C$

Definition

$\eta: 1 \rightarrow T \\ \mu: T*T \rightarrow T$

And here's the associative law:

$\begin{array}{ccc} T*T*T & \xrightarrow[]{\_,\,\mu(\_,\_)} & T*T \\ {\tiny \mu(\_,\_),\_} \downarrow & & \downarrow \\ T*T & \xrightarrow[]{} & T \\ \end{array}$

Significance in the context of category theory

Category theory is all about arrows, where whe have compositions obeying associativity. A monad is a model for category theory!

See also: cartesian closed categories, monoidal categories, ...

Optics

Monads are part of a collection of ideas known as categorical(?) optics. Which introduces notations for a number of simple (or popular) recursion schemes to make reasoning about them easier. A lens is a formalism that encapsulates modifying an object indirectly. It can be used to access data inside a container.

A catamorphism consumes a structured type, say a parsing tree representing an arithmetical expression. It may transform it (e.g. substitute something in it), or it may fold it down to a single value (e.g. evaluate it to obain its value).

An anamorphism creates a structured type.

...

Links

Erik Meijer, Maarten Fokkingay, Ross Patersonz: "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" https://maartenfokkinga.github.io/utwente/mmf91m.pdf

Examples for monads and comonads

We have already discussed options. What else is there?

Reader Comonad
Writer Monad
Error monad (swallows exceptions)
Result monad (stop computation once we have a result)