From explicit failure handling to monads

Lean 4's monad machinery closely resembles what Haskell and OCaml programmers already know. A small evaluator for arithmetic expressions with addition and division makes the motivation concrete: division by zero has to be reported, and the obvious encoding is the Option type.

inductive Expr where
  | num : Int → Expr
  | add : Expr → Expr → Expr
  | div : Expr → Expr → Expr
def safeDiv (x y : Int) : Option Int :=
  if y == 0 then none else some (x / y)
def eval : Expr → Option Int
  | .num n => some n
  | .add a b =>
    match eval a with
    | none => none
    | some x =>
      match eval b with
      | none => none
      | some y => some (x + y)
  | .div a b =>
    match eval a with
    | none => none
    | some x =>
      match eval b with
      | none => none
      | some y => safeDiv x y

Every call to safeDiv forces the caller to check for none before continuing, and that check repeats throughout eval. The repeated shape is always the same: inspect an Option, short-circuit on none, and otherwise feed the unwrapped some result into the rest of the computation. Pulling it into a helper gives withSome:

def withSome (result : Option α) (onSuccess : α → Option β) : Option β :=
  match result with
  | none => none
  | some x => onSuccess x
def evalWithSome : Expr → Option Int
  | .num n => some n
  | .add a b =>
      withSome (evalWithSome a) (fun x =>
        withSome (evalWithSome b) (fun y =>
          some (x + y)))
  | .div a b =>
      withSome (evalWithSome a) (fun x =>
        withSome (evalWithSome b) (fun y =>
          safeDiv x y))

Operator overloading removes the remaining noise:

infixl:55 " >>? " => withSome

def evalOp : Expr → Option Int
  | .num n => some n
  | .add a b =>
    evalOp a >>? fun x =>
    evalOp b >>? fun y =>
    some (x + y)
  | .div a b =>
    evalOp a >>? fun x =>
    evalOp b >>? fun y =>
    safeDiv x y

This is essentially a monad, discovered by hand.

The Monad type class and do notation

Lean's Monad class, in simplified form, is:

class Monad (m : Type → Type) where
  pure : α → m α
  bind : m α → (α → m β) → m β

For Option, pure corresponds to some and bind to withSome. The instance looks roughly like this:

instance : Monad Option where
  pure x := some x
  bind opt next :=
    match opt with
    | none => none
    | some x => next x

Lean already supplies an operator equivalent to the hand-rolled >>?: it is >>=, which dispatches to the class's bind. With that, neither withSome nor a custom operator is needed:

def evalBind : Expr → Option Int
  | .num n => pure n
  | .add a b =>
    evalBind a >>= fun x =>
    evalBind b >>= fun y =>
    some (x + y)
  | .div a b =>
    evalBind a >>= fun x =>
    evalBind b >>= fun y =>
    safeDiv x y

On top of >>= sits do notation, which desugars to it and yields the most compact form of the evaluator:

def evalDo : Expr → Option Int
  | .num n => pure n
  | .add a b => do
    let x ← evalDo a
    let y ← evalDo b
    some (x + y)
  | .div a b => do
    let x ← evalDo a
    let y ← evalDo b
    safeDiv x y

Encapsulating effects

Pure functions are easier to reason about, debug and memoize, but programs that touch the outside world cannot avoid effects. A monad wraps the value a computation returns, and bind (or >>=) threads a wrapped value into the next computation. The resemblance to continuation-passing style is not accidental; continuations are themselves modelable as a monad. The signature of bind is:

bind : m α → (α → m β) → m β

Mentally, the process is: take a value carrying potential effects, take a computation that consumes the underlying value and may add effects of its own, then merge both sets of effects into one wrapped result. Chaining binds therefore sequences computations while accounting for their effects. The key property is the separation of what a computation does from how it is sequenced: the programmer writes the order and dependencies, and bind handles the bookkeeping.

Early return with none is one such effect. Lean's Except type, comparable to Rust's Result, offers a more idiomatic counterpart that carries either a success value or an error. The exception-returning division is:

def safeDivExc (x y : Int) : Except String Int :=
  if y == 0 then .error "division by zero" else .ok (x / y)

Rather than duplicating the evaluator for Except, a single version can be written against any Monad:

def evalM {m : Type → Type} [Monad m]
    (div : Int → Int → m Int) : Expr → m Int
  | .num n => pure n
  | .add a b =>
    do
      let x ← evalM div a
      let y ← evalM div b
      pure (x + y)
  | .div a b =>
    do
      let x ← evalM div a
      let y ← evalM div b
      div x y

Paired with safeDivExc this yields an Except-based evaluator, and paired with safeDiv it is equivalent to the earlier Option-specific evalDo:

#eval evalM safeDiv (.add (.num 4) (.div (.num 6) (.num 0)))
#eval evalM safeDivExc (.add (.num 4) (.div (.num 6) (.num 0)))

A writer monad for logging

Logging every step of evaluation while still propagating divide-by-zero failures calls for a new structure holding the computation state: an optional value together with a list of log strings.

structure LoggedOption (α : Type) where
  value : Option α
  log : List String
instance : Monad LoggedOption where
  pure x := ⟨some x, []⟩
  bind v next :=
    match v.value with
    | none => ⟨none, v.log⟩
    | some x =>
      let nextResult := next x
      ⟨nextResult.value, v.log ++ nextResult.log⟩

The instance appends the stored log to the log produced by the next computation, which is what yields a linear log. The evaluator itself only adds log entries; the plumbing stays inside the monad.

def evalLogged : Expr → LoggedOption Int
  | .num n => pure n
  | .add a b => do
    let x ← evalLogged a
    let y ← evalLogged b
    ⟨some (x + y), [s!"adding {x} and {y}"]⟩
  | .div a b => do
    let x ← evalLogged a
    let y ← evalLogged b
    match y with
    | 0 => ⟨none, [s!"dividing {x} by zero"]⟩
    | _ => ⟨some (x / y), [s!"dividing {x} by {y}"]⟩

LoggedOption is a writer monad, the write-only relative of the state monad.

Threading state through a computation

Mutable state is modeled as a function from an initial state to a pair of result value and updated state:

def State (σ : Type) (α : Type) : Type :=
  σ → (α × σ)

Extending the evaluator with variable assignment and lookup makes this practical. The state is an association list of name, value pairs:

abbrev Vars := List (String × Int)

and the expression enum gains the new operations:

inductive ExprV where
  | num : Int → ExprV
  | add : ExprV → ExprV → ExprV
  | div : ExprV → ExprV → ExprV
  | store : String → ExprV → ExprV
  | load : String → ExprV

The state monad for the evaluator is:

structure EvalM (α : Type) where
  run : Vars → Option (α × Vars)

The run function matches that signature: it receives the association list holding all defined variables and returns an optional pairing of the computed value with an updated state. Its Monad implementation:

instance : Monad EvalM where
  pure x := ⟨fun vars => some (x, vars)⟩
  bind action next := ⟨fun vars =>
    match action.run vars with
    | none => none
    | some (x, vars') => (next x).run vars'⟩

The evaluator now reads as follows:

def evalState : ExprV → EvalM Int
  | .num n => pure n
  | .add a b => do
    let x ← evalState a
    let y ← evalState b
    pure (x + y)
  | .div a b => do
    let x ← evalState a
    let y ← evalState b
    ⟨fun vars => (safeDiv x y).map (fun value => (value, vars))⟩
  | .load name =>
    ⟨fun vars => do
      let value ← vars.lookup name
      pure (value, vars)⟩
  | .store name rhs => do
    let value ← evalState rhs
    ⟨fun vars =>
      let vars' := (name, value) :: vars.filter (fun p => p.1 != name)
      some (value, vars')⟩

Operations such as .num and .add are unchanged in spirit; .div only needs to thread the monad type so that none propagates on division by zero. Because stores return a value and an updated state separately, they can appear as expressions, so a program such as:

-- (x := 12) + (x / 3): the right operand sees the left operand's assignment.
#eval (evalState
  (.add (.store "x" (.num 12))
        (.div (.load "x") (.num 3)))).run []

evaluates to some (16, [("x", 12)]). Compared to mutable state in a struct field or class member, Lean requires carrying the state across the computation explicitly, and the monad hides that carrying so most code avoids the bookkeeping.

IO and monad transformers

IO is the most familiar monad in languages like Lean and Haskell. A short greeting program shows the shape:

def greet : IO Unit := do
  let stdin ← IO.getStdin
  IO.println "What is your name?"
  let name ← stdin.getLine
  IO.println s!"Hello, {name}"

The do block, as above, is sugar for >>= and can be written out explicitly:

def greetBind : IO Unit :=
  IO.getStdin >>= fun stdin =>
  IO.println "What is your name?" >>= fun _ =>
  stdin.getLine >>= fun name =>
  IO.println s!"Hello, {name}"

IO is in essence a state monad whose state is the outside world; println and similar operations act on that world and pass its state along through bind. An evaluator variant that logs to standard output instead of a list looks like:

def evalIO : Expr → OptionT IO Int
  | .num n => pure n
  | .add a b => do
    let x ← evalIO a
    let y ← evalIO b
    IO.println s!"adding {x} and {y}"
    pure (x + y)
  | .div a b => do
    let x ← evalIO a
    let y ← evalIO b
    IO.println s!"dividing {x} by {y}"
    OptionT.mk (pure (safeDiv x y))

The notable piece is OptionT, a monad transformer that composes Option — needed to propagate failures from safe division — with IO. IO also provides throw for Python-like exceptions, though this example keeps Option explicit; exceptions are a matter of preference and feel out of place inside a library function such as eval.

Monad laws

Lean monads are expected to obey the same laws as Haskell's. Left identity: wrapping a value in pure and immediately binding it to f should equal applying f directly.

pure v >>= f       =    f v

Right identity: binding a computation to pure should leave it unchanged.

m >>= pure         =    m

Associativity: regrouped swaps of bind, with order preserved, should not matter.

(m >>= f) >>= g    =    m >>= (fun v => f v >>= g)

For Option, left identity holds because pure v is some v, and bind maps some x to next x, i.e. f v. Right identity holds because m >>= pure rewraps a some value and leaves none untouched. For associativity, none makes both sides none; some v reduces the left side to f v >>= g, which is exactly the right side.

Lean does not force a Monad instance to satisfy these laws, but a separate class, LawfulMonad, carries those obligations as proofs. That fits Lean's core purpose of proving theorems about programs through its type system.

[1]We've replaced some n by pure n in the .num case; technically this isn't necessary, but it will be useful later in the post when we examine other types implementing Monad.
[2]This is explored in Philip Wadler's classical paper "The essence of functional programming".
[3]Except also happens to implement Monad.
[4]We could also have used OptionT in earlier examples, e.g. instead of explicitly defining LoggedOption - try changing that code to use OptionT as an exercise.