Monads in Lean

This post demonstrates how to use monads in the Lean programming language (Lean 4, to be specific). If you're not familiar with Lean, this part of the language is very similar to other functional programming languages, like Haskell or OCaml.

Motivating example - evaluating expressions

Suppose we want to write a simple numerical expression evaluator that supports numbers with addition and division:

inductive Expr where
  | num : Int → Expr
  | add : Expr → Expr → Expr
  | div : Expr → Expr → Expr

What happens when we encounter a division by zero? We'll want our evaluator to report this as a failure, which will be represented explicitly using the the Option type: