# 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. Look at 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)
```

?? why do I need both, map and product, to define apply? I cannot compute pure from map+product?

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)