<< Return to blog posts

Monads in a few words
2024-09-05
Simple explanations for very lazy people

Although there’re already a lot of tutorials about monads, I would like to give it a try with my own explanations which I want to be the most down-to-earth and intuitive as possible.

This article uses the OCaml language.

Chains of functional computation

In (pure) functional programming, computation is performed by passing results produced by a function to another function. This yields a chain of function compositions. For instance, for int -> int function we can have the following chain:

computation : f1 -> f2 -> f3 -> f4 -> f5

which can be represented by the following OCaml program:

let f1 x = x+1
let f2 _ = 0
let f3 x = x-1
let f4 x = x*2
let f5 x = x*x

let computation x =
  let r1 = f1 x  in
  let r2 = f2 r1 in
  let r3 = f3 r2 in
  let r4 = f4 r3 in
  let r5 = f5 r4 in
  r5

let res = computation 5

in which functions can be inlined and made anonymous:

let computation x =
  let r1 = (fun x -> x+1) x  in
  let r2 = (fun _ -> 0)   r1 in
  let r3 = (fun x -> x-1) r2 in
  let r4 = (fun x -> x*2) r3 in
  let r5 = (fun x -> x*x) r4 in
  r5

Enriching computation

Sometimes, you want to enrich your chain of computation and consider more information than just a single argument and the result. Typically, you may want to work with:

We want to wrap our functions within a structure which embeds some computational effect of interest.

Computation with failure

Sometimes, computation can fail. A way to handle that in a purely functional way (only by using basic functions composition as we did) without using ad-hoc error and exceptions mechanisms is to wrap our functions in the 'a option type. Our int -> int functions become int option -> int option functions. Each function checks if the input is None (failure) or Some x (success) and work on that x in case of success.

We adapt our previous example to computation with failure and we introduce the division operator which can fail:

(* Always succeeds except when r2 = (function _ -> Some 1) r1 *)
let computation x =
  let r1 = (function
    | None -> None
    | Some x -> Some (x+1)
    ) (Some x) in
  let r2 = (function _ -> Some 0) r1 in
  let r3 = (function
    | None -> None
    | Some x -> Some (x-1)
    ) r2 in
  let r4 = (function
    | None -> None
    | Some x -> if x==0 then None else Some (5/x)
    ) r3 in
  let r5 = (function
    | None -> None
    | Some x -> Some (x*x)) r4 in
  r5

let res = computation 5

By using the Either type or any other datatype, it is possible to attach more information to failure (like an error message).

Computation with memory

We extend our initial int -> int functions to take into account a memory represented by a list of integers. Our functions:

This gives us functions of type (int list * int) -> (int list * int). This can be represented by the following OCaml program which stores the intermediate results of the computation in some given memory:

let computation (mem, x) =
  let (m1, r1) = (function m, x -> x+1::m, x+1) (mem, x) in
  let (m2, r2) = (function m, _ ->   0::m,   0) (m1, r1) in
  let (m3, r3) = (function m, x -> x-1::m, x-1) (m2, r2) in
  let (m4, r4) = (function m, x -> x*2::m, x*2) (m3, r3) in
  let (m5, r5) = (function m, x -> x*x::m, x*x) (m4, r4) in
  (m5, r5)

let res = computation ([], 5)

The memory can be replaced by any datatype (in particular, multiple arguments can be handled by using tuples).

Computation with action over states

The previous example can be generalised. What we did was basically applying some operation on an int input and a memory to produce a result with memory.

Instead of working with values of the “world of int with a memory”, we can work with “actions over int with memory, producing int values”. If mem = int list, this can be represented with functions of type:

(int -> mem -> mem * int) -> (int -> mem -> mem * int)

equivalent (by right-associativity of ->) to:

(int -> mem -> mem * int) -> int -> mem -> mem * int

which allows us to rewrite our previous function as follows:

let set_and_store x m = (x, x::m)
let apply_state_action f x m = f x m

let computation (mem, x) =
  let (r1, m1) = apply_state_action set_and_store (x+1)  mem in
  let (r2, m2) = apply_state_action set_and_store 0      m1  in
  let (r3, m3) = apply_state_action set_and_store (r2-1) m2  in
  let (r4, m4) = apply_state_action set_and_store (r3*2) m3  in
  let (r5, m5) = apply_state_action set_and_store (r4*r4) m4  in
  (r5, m5)

let res = computation ([], 5)

General functional wrapping

What we did was:

Although it looks different, both can be subsumed by a general construction. Adding a state action as we did is the same thing as wrapping unary functions 'a -> 'b with a 'a state datatype requiring a stateful action:

type mem = int list (* can be any datatype *)
type 'a state = mem -> ('a * mem)

More generally, given some wrapper datatype 'a t, we would like a way to compose functions by turning functions 'a -> 'b into functions 'a t -> 'b t (we would then obtain what we call a functor in category theory). Such an operator would allow us to work with wrapped 'a t -> 'b t functions as if they were 'a -> 'b functions, thus hidding all the complexity of the mechanisms of effectful computation so we can focus on what we are trying to perform without thinking about how it is handled.

Imagine we have such an operator:

(>>=) : ('a -> 'b) -> ('a t -> 'b t) = ('a -> 'b) -> 'a t -> 'b t

Unfortunately, this is actually quite inconvenient. Ideally, because it is more convenient and natural for a programmer, we would like to start from some wrapped value 'a, apply a function on the right with >>= but then applying >>= again on the result of that function. In other words, we want to stack function applications on the right like this:

(* start from some wrapped value 'ta' *)
ta >>= fun x -> (* apply a function *)
b1 >>= fun x -> (* chain by applying a function on the result *)
...
bn >>= fun x ->
...
  1. First, since functions are chained on the right, we must change the order of arguments (it doesn’t have any effect on computation):
(>>=) : 'a t -> ('a -> 'b) -> 'b t

This is not sufficient since the function 'a -> 'b produces a value of type 'b (unwrapped) on which >>= cannot be applied since it waits for a wrapped value 'a t.

We must use “asymmetric” functions ('a -> 'b t) instead of ('a -> 'b). Of course, there are ways to work without changing the type but it would be too cumbersome to use in practice.

It appears that there exists a theory which already features such a way to compose wrapped functions.

Monads

A monad is a general construction coming from category theory which indirectly yields a construction to chain effectful computation for functional programs.

To have an instance of monad, we need:

What we have defined, although called "monad" in functional programming isn't the original definition of monad in category theory. In category theory, monads are defined with an operator of type 'a t t -> a' t. The "asymmetric" bind operator we defined is known as "Kleisli composition".

Instead of a chain of computation

computation : f1 -> f2 -> f3 -> f4 -> f5

we now have

computation : t(f1) -> t(f2) -> t(f3) -> t(f4) -> t(f5)

for some monad 'a t.

Option monad

We have the following monad instance:

let return x = Some x

let (>>=) ta f = match ta with
  | None -> None
  | Some x -> f x

which allows us to rewrite the previous computation with failure program as follows:

let div a b = if b==0 then None else Some (a/b)

let computation x =
  return x   >>= fun x ->
  Some (x+1) >>= fun _ ->
  Some 0     >>= fun x ->
  Some (x-1) >>= fun x ->
  div 5 x    >>= fun x ->
  Some (x*x) >>= fun x ->
  return x

let res = computation 5

Notice how the effect of “failure” (handled by a pattern matching) is hidden in the function composition with the bind operator.

Result monad

We extend the definition with an error message:

type 'a result = Ok of 'a | Err of string
let return x = Ok x

let (>>=) ta f = match ta with
  | Err s -> Err s
  | Ok x -> f x

which allows us to rewrite the previous computation with failure program as follows (the program is ajusted to make it fail):

let computation x =
  return x >>= fun x ->
  Ok (x+1) >>= fun _ ->
  Ok 1     >>= fun x ->
  Ok (x-1) >>= fun x ->
  if x==0 then Err "Division by Zero error"
  else Ok (5/x) >>= fun x ->
  Ok (x*x) >>= fun x ->
  return x

let res = computation 5

State monad

We have the following monad instance:

let return x = fun state -> (state, x)

let (>>=) wrapped_res state_action = fun state ->
  (* "open" the wrapped res *)
  let (new_state, res) = wrapped_res state in
  state_action res new_state

which allows us to rewrite the previous computation with state program as follows:

let set_and_store x mem = (x::mem, x)

let computation x =
  return x >>= fun x ->
  set_and_store (x+1) >>= fun x ->
  set_and_store 0     >>= fun x ->
  set_and_store (x-1) >>= fun x ->
  set_and_store (x*2) >>= fun x ->
  set_and_store (x*x) >>= fun x ->
  return x

let res = computation 5 []

We can even play with more state actions to show how convenient it is:

let set x mem = (mem, x)
let store a x mem = (a::mem, x)
let sum = List.fold_left (fun acc x -> acc+x) 0
let get_sum x mem = (mem, sum mem)
let clear_memory x mem = ([], x)

let computation x =
  return x       >>= fun x ->
  store x x      >>= fun x ->
  set 100        >>= fun x ->
  clear_memory x >>= fun x ->
  store 5 x      >>= fun x ->
  store 5 x      >>= fun x ->
  get_sum x      >>= fun x ->
  return x

let res = computation 5 []

List monad

Let’s try to define a monad instance for 'a list.

  1. How to construct 'a list from 'a?

The natural way which neither loses or adds irrelevant information is:

let return x = [x]
  1. From a list 'a list and a function 'a -> 'b list, how can we construct a result 'b list?

We can apply the function on each element of the list then flatten the list with List.concat:

let (>>=) ta f = List.concat (List.map f ta)

Now, what does it do?

Lists can be seen as possible results (non-deterministic choices) on which we act with a function to get all the possible outcome of our result:

// All possible outcomes of applying (fun x -> x+5)
// over all integers between 1 and 5
[1; 2; 3; 4; 5] >>= fun x ->
return (x+5)

More interestingly, this can be used to reason on the choice of any elements from some given lists:

[1; 2; 3] >>= fun x ->
[4; 5; 6] >>= fun y ->
[7; 8; 9] >>= fun z ->
return (x, y, z)

corresponding to

E = {(x, y, z) | x in [1;2;3], y in [4;5;6], z in [7;8;9]}.

And this allows us to do list comprehension by filtering results:

[1; 2; 3] >>= fun x ->
[4; 5; 6] >>= fun y ->
[7; 8; 9] >>= fun z ->
if x+y==z then return (x, y, z) else []

corresponding to {(x, y, z) | (x, y, z) in E, x+y==z}.

<< Return to blog posts