Monad

In functional programming, a monad is a type constructor $M$ together with two operations: $return : a \to M a$ , which wraps a plain value, and $> > = : M a \to (a \to M b) \to M b$ (bind), which runs a computation and passes its result to a function that produces the next one. Code with some extra behaviour, such as failing, producing several results, reading configuration, threading state or performing I/O, can then be written as a sequence of ordinary-looking steps, and the behaviour is defined once, in bind.

The notion comes from category theory, where it was studied from the late 1950s. Moggi used monads in 1989 to give a uniform semantics to computational effects^[1]^[2], and Wadler showed how to use them to structure functional programs^[3]^[4]. Haskell adopted monadic I/O in version 1.3^[15]. Monads are a type class in Haskell and a module signature in OCaml, and the same structure appears in mainstream languages under names like flatMap (Scala, Java), and_then (Rust) and SelectMany (C#).

§ 01

Overview

Consider three lookups in a row, each of which can fail. Written directly, every step is a match on the result of the previous one, and the failure case is repeated at every level:

Looking up an employee's manager's email, with and without bind.

(* Three lookups, each of which can fail. Without a monad every step is a match. *)
let find k l = List.assoc_opt k l
 
let manager_email_nested employees managers emails name =
  match find name employees with
  | None -> None
  | Some dept -> (
      match find dept managers with
      | None -> None
      | Some boss -> (
          match find boss emails with None -> None | Some e -> Some e))
 
(* With bind, the None case is written once, inside bind. *)
let ( let* ) m f = match m with Some x -> f x | None -> None
 
let manager_email employees managers emails name =
  let* dept = find name employees in
  let* boss = find dept managers in
  find boss emails

Running it.

manager_email "ada"   ->  Some [email protected]
manager_email "brom"  ->  None
same as nested match   ->  true

Every step has the same shape: run a computation, and if it produced a value, pass that value to the next step. let*, which is bind for option, captures exactly that, and the None case is written once, inside it. Other monads differ only in what it means for a computation to produce a value and for that value to be passed on: a list produces several, a state computation produces one along with a new state, an I/O action produces one after interacting with the world.

§ 02

Definition

A monad consists of a type constructor $M$ and two operations

return : a \to M a > > = : M a \to (a \to M b) \to M b

that satisfy the laws below. In Haskell they are the methods of the Monad class; in OCaml they are the contents of a module matching a signature, and a functor derives everything else from them.

The monad interface as an OCaml signature, and the operations every monad gets from return and bind.

(* The interface every monad provides. *)
module type MONAD = sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end
 
(* Everything else follows from return and bind, once, for every monad. *)
module Extend (M : MONAD) = struct
  include M
  let ( let* ) = bind
  let map f m = bind m (fun x -> return (f x))
  let join mm = bind mm (fun m -> m)
  let ( >=> ) f g x = bind (f x) g
  let rec sequence = function
    | [] -> return []
    | m :: ms -> bind m (fun x -> bind (sequence ms) (fun xs -> return (x :: xs)))
  let traverse f xs = sequence (List.map f xs)
end
 
module Option_m = Extend (struct
  type 'a t = 'a option
  let return x = Some x
  let bind m f = match m with Some x -> f x | None -> None
end)
 
module List_m = Extend (struct
  type 'a t = 'a list
  let return x = [ x ]
  let bind m f = List.concat_map f m
end)

Running it.

Option_m.traverse parse ["1"; "2"; "3"]  ->  Some [1; 2; 3]
Option_m.traverse parse ["1"; "x"; "3"]  ->  None
List_m.sequence [[1; 2]; [3; 4]]         ->  [[1; 3]; [1; 4]; [2; 3]; [2; 4]]
List_m.join [[1]; [2; 3]; []]            ->  [1; 2; 3]

Laws

return a > > = f m > > = return (m > > = f) > > = g = f a = m = m > > = (λ x . f x > > = g) left identity right identity associativity

The identity laws say that $return$ adds no behaviour of its own. Associativity says that the way a chain of binds is nested does not matter, which is what makes a flat sequence of steps, as written with do-notation or let*, unambiguous. The laws are not checked by any compiler; they are what allows code using a monad to be refactored, such as extracting a few steps into a helper function, without changing its meaning.

The laws checked on random lists and random functions for the list monad.

(* The laws, checked on random inputs for the list monad. *)
let return x = [ x ]
let bind m f = List.concat_map f m
 
let () = Random.init 7
let rand_list () = List.init (Random.int 4) (fun _ -> Random.int 10)
(* Random functions int -> int list, built from a random table. *)
let rand_fun () =
  let table = Array.init 10 (fun _ -> rand_list ()) in
  fun x -> table.(abs x mod 10)
 
let left_identity () = let a = Random.int 10 and f = rand_fun () in bind (return a) f = f a
let right_identity () = let m = rand_list () in bind m return = m
let associativity () =
  let m = rand_list () and f = rand_fun () and g = rand_fun () in
  bind (bind m f) g = bind m (fun x -> bind (f x) g)

Running it.

left identity     holds on 10000 random cases
right identity    holds on 10000 random cases
associativity     holds on 10000 random cases

Kleisli composition

The laws are easier to remember in terms of Kleisli composition, which composes functions that return monadic values:

(f > = > g) x = f x > > = g f : a \to M b, g : b \to M c

In that form the three laws say that $return$ is an identity for $> = >$ and that $> = >$ is associative:

return > = > f = f f > = > return = f (f > = > g) > = > h = f > = > (g > = > h)

so functions $a \to M b$ form a category, the Kleisli category of the monad.

Join and map

An equivalent definition replaces bind by join, which removes one layer of structure, together with fmap:

join : M (M a) \to M a m > > = f = join (fmap f m) join mm = mm > > = id

and $fmap f m = m > > = (return \circ f)$ . For lists join is concatenation; for option it turns Some (Some x) into Some x and anything else into None. This is the form used in category theory.

§ 03

Notation

Chains of binds with a lambda at each step are hard to read, so most languages with monads provide syntax for them. Haskell's do-notation is defined by three rewriting rules:

do {x \leftarrow e; s} do {e; s} do {e} = e > > = λ x . do {s} = e > > = λ_. do {s} = e

OCaml has binding operators instead: once let* is defined as bind, let* x = e in body means bind e (fun x -> body). Other languages have their own forms:

Bind and its syntax in several languages.

Haskell    >>=                  do-notation
OCaml      bind, let*           let* x = e in ...
F#         Bind                 computation expressions: let! x = e
Scala      flatMap              for-comprehensions: for (x <- e) yield ...
C#         SelectMany           LINQ query syntax: from x in e select ...
Rust       and_then             the ? operator, for Option and Result
Java       flatMap              (method chains on Optional and Stream)

List comprehensions are do-notation for the list monad, and Wadler generalised them to comprehensions over any monad^[3].

§ 04

Examples

Option

The option monad (Maybe in Haskell) models computations that can fail without a reason. Bind stops at the first None; the Overview uses it.

Result

Result (Either in Haskell) is the same, but a failure carries an error value, and the first error ends the computation:

Validating two ages with Result.bind.

let ( let* ) = Result.bind
 
let parse_age s =
  match int_of_string_opt s with
  | None -> Error ("not a number: " ^ s)
  | Some n when n < 0 -> Error "negative age"
  | Some n -> Ok n
 
let older a b =
  let* x = parse_age a in
  let* y = parse_age b in
  Ok (max x y)

Running it. Only the first error is reported; reporting all of them needs an applicative instead.

older "36" "41"  ->  Ok 41
older "36" "x"   ->  Error "not a number: x"
older "-1" "x"   ->  Error "negative age"

Stopping at the first error is inherent: the second step is a function of the first step's result, and there is no result to apply it to. An applicative can report every error, because its steps do not depend on each other.

List

The list monad models nondeterminism: a computation produces any number of results, and bind runs the rest of the computation once for each, concatenating what they produce. A step that produces no results prunes that branch.

Pythagorean triples as a search.

let return x = [ x ]
let ( let* ) xs f = List.concat_map f xs
let guard b = if b then [ () ] else []
 
(* Every choice of a, b, c; the ones that fail the guard contribute nothing. *)
let triples n =
  let* a = List.init n succ in
  let* b = List.init (n - a + 1) (fun i -> a + i) in
  let* c = List.init (n - b + 1) (fun i -> b + i) in
  let* () = guard ((a * a) + (b * b) = c * c) in
  return (a, b, c)

Running it.

triples 20  ->  (3,4,5) (5,12,13) (6,8,10) (8,15,17) (9,12,15) (12,16,20)

Writer

A writer computation produces a value and some output, and bind concatenates the outputs. Here the output is a log:

Counting Collatz steps and logging each one.

module Writer = struct
  type 'a t = 'a * string list
  let return x = (x, [])
  let bind (x, log) f = let y, log' = f x in (y, log @ log')
  let tell msg = ((), [ msg ])
end
 
let ( let* ) = Writer.bind
 
let rec collatz n : int Writer.t =
  if n = 1 then Writer.return 0
  else
    let next = if n mod 2 = 0 then n / 2 else (3 * n) + 1 in
    let* () = Writer.tell (Printf.sprintf "%d -> %d" n next) in
    let* steps = collatz next in
    Writer.return (steps + 1)

Running it.

collatz 6  ->  8 steps, log: 6 -> 3, 3 -> 10, 10 -> 5, 5 -> 16, 16 -> 8, 8 -> 4, 4 -> 2, 2 -> 1

The output only needs to be a monoid, so the same structure accumulates a sum, a maximum or a set.

Reader

A reader computation is a function of a shared, read-only environment, $E \to a$ . Bind passes the same environment to both steps, which removes the need to thread a configuration value through every call by hand.

A greeting that depends on a configuration record.

module Reader = struct
  type ('e, 'a) t = 'e -> 'a
  let return x _ = x
  let bind m f env = f (m env) env
  let ask env = env
end
 
let ( let* ) = Reader.bind
 
type config = { name : string; verbose : bool }
 
let greeting : (config, string) Reader.t =
  let* c = Reader.ask in
  Reader.return (if c.verbose then "Hello, " ^ c.name ^ ", welcome back." else "Hi " ^ c.name)

Running it.

greeting { verbose = true }   ->  Hello, Ada, welcome back.
greeting { verbose = false }  ->  Hi Ada

State

A state computation is a function from a state to a result and a new state, $S \to a \times S$ . Bind runs the first computation on the current state and the second on the state it leaves behind:

m > > = f = λ s . let (x, s^{'}) = m s in f x s^{'}

A stack machine evaluating 2 3 + 4 * with the stack as state.

(* State: a computation that threads a value through, s -> a * s. *)
module State = struct
  type ('s, 'a) t = 's -> 'a * 's
  let return x s = (x, s)
  let bind m f s = let x, s' = m s in f x s'
  let get s = (s, s)
  let put s _ = ((), s)
  let run m s = m s
end
 
let ( let* ) = State.bind
 
(* A stack machine: the stack is the state. *)
let push x = let* st = State.get in State.put (x :: st)
let pop = let* st = State.get in match st with x :: rest -> let* () = State.put rest in State.return x | [] -> failwith "empty"
 
let binop f = let* b = pop in let* a = pop in push (f a b)
 
(* 2 3 + 4 *  in reverse Polish notation *)
let program = let* () = push 2 in let* () = push 3 in let* () = binop ( + ) in let* () = push 4 in let* () = binop ( * ) in pop

Running it.

run program []   ->  result 20, final stack []

Continuation

A continuation computation receives the rest of the program as a function and decides how to call it:

Cont_{r} a = (a \to r) \to r m > > = f = λk . m (λ x . f x k)

This is continuation-passing style packaged as a monad. Because the continuation is a value, it can be ignored, called twice or stored, which gives early exit, backtracking and coroutines. callcc passes the current continuation to its argument:

Early exit from a fold with call/cc.

module Cont = struct
  type ('r, 'a) t = ('a -> 'r) -> 'r
  let return x k = k x
  let bind m f k = m (fun x -> f x k)
  (* call/cc hands the computation its own continuation, as a function
     that abandons whatever continuation it is later called under. *)
  let callcc f k = f (fun x _ -> k x) k
  let run m = m Fun.id
end
 
let ( let* ) = Cont.bind
 
(* Product of a list, leaving the whole computation as soon as a zero appears. *)
let product xs =
  Cont.run
    (Cont.callcc (fun exit ->
         let rec go = function
           | [] -> Cont.return 1
           | 0 :: _ -> exit 0
           | x :: rest -> let* p = go rest in Cont.return (x * p)
         in
         go xs))

Running it.

product [2; 3; 4]  ->  24
product [2; 0; 4]  ->  0

I/O

Haskell has no side effects in expressions, so input and output are values of type IO a: descriptions of interactions that produce an a. The runtime system performs the one called main. Bind sequences two descriptions into one, and do-notation makes the result read like imperative code:

Haskell. The do block is getLine >>= \name -> putStrLn ("Hello, " ++ name).

main :: IO ()
main = do
  name <- getLine
  putStrLn ("Hello, " ++ name)

Conceptually IO a is a state monad over the state of the world, $W \to a \times W$ , where the world can only be passed along, never copied; Peyton Jones and Wadler describe this design^[5]. OCaml performs effects directly and does not need an I/O monad, but its promise libraries, such as Lwt, are monads over the same idea: a value that will be available later.

Parsers

A parser is a function from input to a result and the remaining input, or failure, which is the state monad combined with option or list. Bind runs one parser after another on what is left, and parser combinators are built from it.

§ 05

Derived operations

Many functions are written once for all monads, in terms of return and bind:

fmap f m join mm sequence traverse = m > > = (return \circ f) = mm > > = id : [M a] \to M [a] : (a \to M b) \to [a] \to M [b]

sequence runs a list of computations in order and collects their results; for option it fails if any fails, and for lists it takes the cartesian product, as the output in the Definition section shows. traverse maps and then sequences, and is the usual way to apply a fallible function to every element of a list. The OCaml functor Extend above defines them once for every monad passed to it.

§ 06

Relation to functors and applicative functors

Every monad is a functor, with fmap defined from bind as above, and an applicative functor, with

pure = return m f ⊛ m x = m f > > = λ f . m x > > = λ x . return (f x)

The difference between the three is what a later step may depend on. With fmap there is only one computation. With the applicative $⊛$ there are several, but each is fixed before any runs. With bind the next computation is chosen by a function of the previous result, which is strictly more powerful: it can decide whether to continue, and which computation to run next. The cost is that a monadic computation cannot be inspected before it runs^[13]. Haskell's standard library has made Applicative a superclass of Monad since 2015.

§ 07

Category theory

A monad on a category $C$ is a triple $(T, η, μ)$ of an endofunctor $T : C \to C$ and natural transformations $η : 1_{C} \to T$ and $μ : T^{2} \to T$ satisfying

μ \circ T μ = μ \circ μ T μ \circ T η = μ \circ η T = 1_{T}

With composition of endofunctors as the tensor product, these are exactly the associativity and unit laws of a monoid, which is the meaning of the phrase "a monad is a monoid in the category of endofunctors"^[10]. The programming definition is the equivalent Kleisli triple form, with $η = return$ and $μ = (> > = id)$ ^[16].

Kleisli category

The Kleisli category $C_{T}$ has the objects of $C$ , arrows $A \to T B$ as its morphisms from $A$ to $B$ , identities $η_{A}$ , and composition

g \circ_{T} f = μ_{C} \circ T g \circ f

which is Kleisli composition, written the other way round.

Adjunctions

Every adjunction $F ⊣ G$ with $F : C \to D$ gives a monad $GF$ on $C$ ^[7], and every monad arises this way: the Kleisli category and the category of Eilenberg–Moore algebras give the smallest and largest adjunctions that produce it^[8]^[9]. Two programming monads come from familiar adjunctions. The state monad comes from the currying adjunction $(- \times S) ⊣ (S \to -)$ :

T A = S \to (A \times S)

and the list monad from the free monoid adjunction between sets and monoids, with $T A = A^{*}$ , the finite sequences over $A$ , and $μ$ concatenation.

§ 08

Variations

Additive monads

Some monads also have a failing computation and a way to combine alternatives, with laws that make them a monoid compatible with bind:

mzero : M a mplus : M a \to M a \to M a mzero > > = f = mzero

For lists they are the empty list and concatenation; for option, None and taking the first Some. guard, as used in the list example, is defined from them.

Monad transformers

Monads do not compose in general: the composite of two monads is not always a monad. A monad transformer adds one effect on top of any monad, so effects can be stacked^[11].

StateT as an OCaml functor, applied to option: state that can also fail.

(* A monad transformer adds one effect to any monad. StateT over option:
   state that can also fail, s -> (a * s) option. *)
module StateT (M : sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end) = struct
  type ('s, 'a) t = 's -> ('a * 's) M.t
  let return x s = M.return (x, s)
  let bind m f s = M.bind (m s) (fun (x, s') -> f x s')
  let lift (m : 'a M.t) : ('s, 'a) t = fun s -> M.bind m (fun x -> M.return (x, s))
  let get s = M.return (s, s)
  let put s _ = M.return ((), s)
end
 
module S = StateT (struct
  type 'a t = 'a option
  let return x = Some x
  let bind m f = match m with Some x -> f x | None -> None
end)
 
let ( let* ) = S.bind
 
(* Take the next token from the input; fail when it runs out. *)
let next = let* input = S.get in match input with t :: rest -> let* () = S.put rest in S.return t | [] -> S.lift None
let number = let* t = next in S.lift (int_of_string_opt t)
let sum_of_two = let* a = number in let* b = number in S.return (a + b)

Running it.

sum_of_two ["2"; "40"; "x"]  ->  Some (42, [x])
sum_of_two ["2"; "x"]        ->  None
sum_of_two ["2"]             ->  None

The order of a stack matters. $StateT s Maybe$ is $s \to (a \times s) option$ , so a failure discards the state. $MaybeT (State s)$ is $s \to a option \times s$ , so the state reached before the failure survives. Effect handlers are the other widely used answer to combining effects.

Free monads

For a functor $F$ , the free monad is the tree of $F$ -shaped layers ending in values:

Free F a = Pure a ∣ Free (F (Free F a))

It is a monad for any functor, and a program written in it is a data structure describing its effects without performing them, which separate interpreters can then run, test or translate^[12].

Comonads

A comonad is the categorical dual: $extract : W a \to a$ and $extend : (W a \to b) \to W a \to W b$ . Where a monad builds context around a value, a comonad computes from a value in context: streams, zippers focused on one position, and cellular automata, where each cell's next state depends on its neighbours^[14].

§ 09

History

Godement described the structure in 1958 as a "standard construction"^[6]. Huber showed in 1961 that every adjunction gives one^[7], and in 1965 Kleisli and, independently, Eilenberg and Moore showed that every one arises from an adjunction^[8]^[9]. It was called a triple in that period; the name monad came later and became standard through Mac Lane's textbook^[10].

Moggi proposed monads in 1989 as a way to structure the semantics of programming languages, with one monad for each notion of computation: partiality, exceptions, state, nondeterminism, continuations^[1]^[2]. Wadler turned the idea into a programming technique for pure functional languages^[3]^[4], Peyton Jones and Wadler used it for I/O in Haskell^[5], and Haskell 1.3 made monadic I/O part of the language^[15]. Monad transformers followed in 1995^[11].

Outside functional languages the structure is common without the name. JavaScript promises come close: then acts as bind, but it flattens nested promises automatically, so a promise of a promise cannot exist and the laws hold only up to that. Java's Optional and Stream, Rust's Option and Result with the ? operator, and C#'s LINQ are all built around a bind.