{"article":{"slug":"monads-in-lean","title":"Monads in Lean","subtitle":null,"summary":"Eli Bendersky's tutorial on using monads in Lean 4, starting from an expression evaluator with Option-based failure handling and building up through the Monad type class, do-notation, logging, Except and monad transformers like OptionT.","content_type":"tutorial","language":"en","canonical_url":"https://eli.thegreenplace.net/2026/monads-in-lean/","author":{"name":"Eli Bendersky","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Eli Bendersky's website","url":"https://eli.thegreenplace.net/","listing_slug":null,"listing":null},"topics":[{"name":"programming-languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"},{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":2423,"reading_minutes":11,"published_at":"2026-11-10T00:00:00.000Z","added_at":"2026-11-11T11:13:56.754Z","updated_at":"2026-11-11T11:13:56.754Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/monads-in-lean","markdown_url":"https://listedarticles.com/articles/monads-in-lean.md","example":false,"citation":"Eli Bendersky, Eli Bendersky's website. \"Monads in Lean.\" 10 Nov 2026. https://eli.thegreenplace.net/2026/monads-in-lean/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://eli.thegreenplace.net/2026/monads-in-lean/"},"body_markdown":"# Monads in Lean\n\nThis post demonstrates how to use monads in the Lean programming language\n(Lean 4, to be specific). If you're not familiar with Lean, this part of the\nlanguage is very similar to other functional programming languages, like\nHaskell or OCaml.\n\n## Motivating example - evaluating expressions\n\nSuppose we want to write a simple numerical expression evaluator that supports\nnumbers with addition and division:\n\n```\ninductive Expr where\n  | num : Int → Expr\n  | add : Expr → Expr → Expr\n  | div : Expr → Expr → Expr\n```\n\nWhat happens when we encounter a division by zero? We'll want our evaluator\nto report this as a failure, which will be represented explicitly using the\nthe Option type:\n\n```\ndef safeDiv (x y : Int) : Option Int :=\n  if y == 0 then none else some (x / y)\n```\n\nWith this in hand, the eval function can be written as follows:\n\n```\ndef eval : Expr → Option Int\n  | .num n => some n\n  | .add a b =>\n    match eval a with\n    | none => none\n    | some x =>\n      match eval b with\n      | none => none\n      | some y => some (x + y)\n  | .div a b =>\n    match eval a with\n    | none => none\n    | some x =>\n      match eval b with\n      | none => none\n      | some y => safeDiv x y\n```\n\nsafeDiv returns an Option; to propagate that possible failure to\nits caller, eval also returns an Option, and - moreover - has to perform\nlots of tedious checking for the possibility of a none value. Is there a\nbetter way?\n\nNote a common code pattern repeated here:\n\n1. Examine the value of an Option\n2. If it's none, return none without proceeding\n3. Otherwise if it's some result, continue the computation with result\n\nWe can extract it into a helper function:\n\n```\ndef withSome (result : Option α) (onSuccess : α → Option β) : Option β :=\n  match result with\n  | none => none\n  | some x => onSuccess x\n```\n\nAnd rewrite our eval using this helper:\n\n```\ndef evalWithSome : Expr → Option Int\n  | .num n => some n\n  | .add a b =>\n      withSome (evalWithSome a) (fun x =>\n        withSome (evalWithSome b) (fun y =>\n          some (x + y)))\n  | .div a b =>\n      withSome (evalWithSome a) (fun x =>\n        withSome (evalWithSome b) (fun y =>\n          safeDiv x y))\n```\n\nThis is already much better; we can make it even cleaner using operator\noverloading:\n\n```\ninfixl:55 \" >>? \" => withSome\n\ndef evalOp : Expr → Option Int\n  | .num n => some n\n  | .add a b =>\n    evalOp a >>? fun x =>\n    evalOp b >>? fun y =>\n    some (x + y)\n  | .div a b =>\n    evalOp a >>? fun x =>\n    evalOp b >>? fun y =>\n    safeDiv x y\n```\n\nCongratulations - we've pretty much invented monads!\n\n## Option as a Monad in expression evaluation\n\nIn simplified form, the Monad type class in Lean is defined as:\n\n```\nclass Monad (m : Type → Type) where\n  pure : α → m α\n  bind : m α → (α → m β) → m β\n```\n\nIn our code, pure is equivalent to some, and bind is equivalent\nto withSome; in fact, the Monad instance for Option is something\nlike:\n\n```\ninstance : Monad Option where\n  pure x := some x\n  bind opt next :=\n    match opt with\n    | none => none\n    | some x => next x\n```\n\nAn operator akin to >>? for monads is already defined in Lean; it's called\n>>=, and picks up the bind method of the Monad type class. So we can\nrewrite our evaluator using the standard Monad instance, without defining\nwithSome or the >>? operator [[1]](#footnote-1):\n\n```\ndef evalBind : Expr → Option Int\n  | .num n => pure n\n  | .add a b =>\n    evalBind a >>= fun x =>\n    evalBind b >>= fun y =>\n    some (x + y)\n  | .div a b =>\n    evalBind a >>= fun x =>\n    evalBind b >>= fun y =>\n    safeDiv x y\n```\n\nWe can go even further with the do notation, which is syntactic sugar around\n>>= that lets us rewrite the evaluator as:\n\n```\ndef evalDo : Expr → Option Int\n  | .num n => pure n\n  | .add a b => do\n    let x ← evalDo a\n    let y ← evalDo b\n    some (x + y)\n  | .div a b => do\n    let x ← evalDo a\n    let y ← evalDo b\n    safeDiv x y\n```\n\nThis notation should be familiar if you've seen Lean code dealing with I/O;\nwe'll revisit I/O later in the post.\n\n## Monads for modeling side effects\n\nFunctional programming languages place a lot of emphasis on *pure* functions\nthat are free of side effects. There's no question that such functions are\neasier to reason about, debug, and even optimize (by memoization). That said,\nthe real world is messy and sometimes side effects are inescapable; monads\nhelp encapsulate side effects in functional programs.\n\nThe core idea is: side effects are encapsulated inside a Monad, which\nwraps the value returned from a computation. The bind method (or the\nequivalent >>= operator) lets us take a wrapped value and push it into the\nnext computation in the sequence. This may look familiar from\ncontinuation-passing style (CPS). Continuations themselves can also be modeled\nwith a monad [[2]](#footnote-2).\n\nThe definition of bind is:\n\n```\nbind : m α → (α → m β) → m β\n```\n\nHere's a mental model to think about it:\n\n1. Take a value wrapped with potential side effects\n2. Take a computation that takes this value and may produce additional side\n   effects\n3. Combine the results into a final wrapped value\n\nChaining multiple binds together is essentially a sequence of computations\nwhile keeping track of the side effects. A monad decouples what computations\n*do* from *how they are sequenced*. The programmer describes the sequence of\ncomputations and their dependencies, while the monad's bind implementation\nhandles the bookkeeping necessary to combine their side effects.\n\nOur evaluator case study shows one example of side effects: early return from\na computation with a none value.\n\nLet's see another idiomatic way of doing that, with the Except type that\ncontains either a successful result or an error value (very similar to the\nResult type in Rust).\n\nWe'll begin by writing an exception-returning version of safeDiv:\n\n```\ndef safeDivExc (x y : Int) : Except String Int :=\n  if y == 0 then .error \"division by zero\" else .ok (x / y)\n```\n\nInstead of writing a whole new eval variant for Except, we'll\ncreate a generic one that works with any Monad [[3]](#footnote-3):\n\n```\ndef evalM {m : Type → Type} [Monad m]\n    (div : Int → Int → m Int) : Expr → m Int\n  | .num n => pure n\n  | .add a b =>\n    do\n      let x ← evalM div a\n      let y ← evalM div b\n      pure (x + y)\n  | .div a b =>\n    do\n      let x ← evalM div a\n      let y ← evalM div b\n      div x y\n```\n\nNow evalM can be used with safeDivExc to implement an evaluator where\ndivision returns Except; used with safeDiv, it would be equivalent to\nthe Option-specific evalDo we've written before.\n\n```\n#eval evalM safeDiv (.add (.num 4) (.div (.num 6) (.num 0)))\n#eval evalM safeDivExc (.add (.num 4) (.div (.num 6) (.num 0)))\n```\n\n## Logging computations - an example of the writer monad\n\nLet's look at a more advanced example: an evaluator that also *logs* the\ncomputation it executes in a linear log of strings. The challenge here is that\nwe still have to combine that with Option to support the divide-by-zero\ncase, so we'll start by creating a new structure to carry the state of the\ncomputation:\n\n```\nstructure LoggedOption (α : Type) where\n  value : Option α\n  log : List String\n```\n\nThis will be the result of one eval call; it produces an optional value,\nalong with a list of strings (the log). Here's the Monad implementation for\nthis type:\n\n```\ninstance : Monad LoggedOption where\n  pure x := ⟨some x, []⟩\n  bind v next :=\n    match v.value with\n    | none => ⟨none, v.log⟩\n    | some x =>\n      let nextResult := next x\n      ⟨nextResult.value, v.log ++ nextResult.log⟩\n```\n\nThe main idea is combining the stored log with the log of the next computation\nby appending them (thus accumulating a linear log). Here's our evaluator:\n\n```\ndef evalLogged : Expr → LoggedOption Int\n  | .num n => pure n\n  | .add a b => do\n    let x ← evalLogged a\n    let y ← evalLogged b\n    ⟨some (x + y), [s!\"adding {x} and {y}\"]⟩\n  | .div a b => do\n    let x ← evalLogged a\n    let y ← evalLogged b\n    match y with\n    | 0 => ⟨none, [s!\"dividing {x} by zero\"]⟩\n    | _ => ⟨some (x / y), [s!\"dividing {x} by {y}\"]⟩\n```\n\nNote how the code of evalLogged doesn't have to deal with the mechanics\nof logging too much (other than adding new log entries). All of that is hidden\nwithin the monad instance. LoggedOption is an example of the *writer monad*,\nwhich is a write-only version of the *state monad*.\n\n## State monad\n\nOne of the most important use cases of monads in functional programming\nlanguages is modeling mutable state through a computation.\n\nA stateful computation is modeled as a function that takes an initial state\nand returns a tuple containing the result value and a new, updated state. In\nLean notation:\n\n```\ndef State (σ : Type) (α : Type) : Type :=\n  σ → (α × σ)\n```\n\nTo demonstrate this in action, let's enhance our evaluator to support variable\nassignments and lookups. Our state is going to be an association list of\nname, value pairs:\n\n```\nabbrev Vars := List (String × Int)\n```\n\nAnd we'll augment our expression enum with additional operations:\n\n```\ninductive ExprV where\n  | num : Int → ExprV\n  | add : ExprV → ExprV → ExprV\n  | div : ExprV → ExprV → ExprV\n  | store : String → ExprV → ExprV\n  | load : String → ExprV\n```\n\nThis is going to be our state monad:\n\n```\nstructure EvalM (α : Type) where\n  run : Vars → Option (α × Vars)\n```\n\nNote the correspondence of the run function to the State signature\nabove:\n\n- It takes the current state, which for our use cases is an association list\n  carrying values for all defined variables.\n- It returns an optional result which is a pair of some value (in our case,\n  the result of the computation) and an updated state.\n\nThis is its Monad class implementation:\n\n```\ninstance : Monad EvalM where\n  pure x := ⟨fun vars => some (x, vars)⟩\n  bind action next := ⟨fun vars =>\n    match action.run vars with\n    | none => none\n    | some (x, vars') => (next x).run vars'⟩\n```\n\nAnd finally, the evaluator:\n\n```\ndef evalState : ExprV → EvalM Int\n  | .num n => pure n\n  | .add a b => do\n    let x ← evalState a\n    let y ← evalState b\n    pure (x + y)\n  | .div a b => do\n    let x ← evalState a\n    let y ← evalState b\n    ⟨fun vars => (safeDiv x y).map (fun value => (value, vars))⟩\n  | .load name =>\n    ⟨fun vars => do\n      let value ← vars.lookup name\n      pure (value, vars)⟩\n  | .store name rhs => do\n    let value ← evalState rhs\n    ⟨fun vars =>\n      let vars' := (name, value) :: vars.filter (fun p => p.1 != name)\n      some (value, vars')⟩\n```\n\nOperations that don't deal with variables directly (like .num and\n.add) just do their work as before. .div only has to deal with the\nactual monad type to ensure that none is propagated in case of division\nby zero. Note also that this evaluator supports stores as expressions, since\nthey separately return a value and the updated state; therefore, computations\nlike this one will work:\n\n```\n-- (x := 12) + (x / 3): the right operand sees the left operand's assignment.\n#eval (evalState\n  (.add (.store \"x\" (.num 12))\n        (.div (.load \"x\") (.num 3)))).run []\n```\n\nProducing the result some (16, [(\"x\", 12)]).\n\nIn a language with mutable state, modeling side effects is easy - just assign\nsome state (like a struct field or class member). In a functional language like\nLean, however, we have to carry this state across the computations explicitly;\nmonads help us do this with elegance - by hiding most of the mechanics of\nactually carrying the state around, the majority of the code remains free\nof bookkeeping.\n\n## IO monad\n\nPerhaps the most well known example of a monad in functional programming\nlanguages like Lean and Haskell is IO. To anyone who's written a \"real\"\nprogram that interacts with the outer world, IO is very familiar. Here's\na customized \"Hello\" program that's typically taught in the first 15\nminutes of learning a new programming language:\n\n```\ndef greet : IO Unit := do\n  let stdin ← IO.getStdin\n  IO.println \"What is your name?\"\n  let name ← stdin.getLine\n  IO.println s!\"Hello, {name}\"\n```\n\nNote the do notation here, suggesting monads. As mentioned before, do\nis syntactic sugar for the monad's bind method, or the >>= operator; we\ncan rewrite this code more explicitly as:\n\n```\ndef greetBind : IO Unit :=\n  IO.getStdin >>= fun stdin =>\n  IO.println \"What is your name?\" >>= fun _ =>\n  stdin.getLine >>= fun name =>\n  IO.println s!\"Hello, {name}\"\n```\n\nIn essence, IO is a state monad, where the state carried around represents\nthe \"outside world\". IO operations like println act on that world,\nand its state is carried over using bind, like other state monads.\n\nHere's a version of our expression evaluator that logs directly to standard out,\ninstead of collecting the log as a list of strings:\n\n```\ndef evalIO : Expr → OptionT IO Int\n  | .num n => pure n\n  | .add a b => do\n    let x ← evalIO a\n    let y ← evalIO b\n    IO.println s!\"adding {x} and {y}\"\n    pure (x + y)\n  | .div a b => do\n    let x ← evalIO a\n    let y ← evalIO b\n    IO.println s!\"dividing {x} by {y}\"\n    OptionT.mk (pure (safeDiv x y))\n```\n\nThe only unusual construct here is OptionT, which is a *monad transformer*\nthat helps us compose Option (for propagating failure from safe division)\nwith the IO Monad [[4]](#footnote-4).\n\nThe IO monad also supports throw for Python-like exception behavior,\nbut in this example we use Option explicitly; exceptions are a matter of\nprogramming preference, and using them inside library functions like eval\ndoesn't feel right to me.\n\n## Monad laws in Lean\n\nJust like in Haskell, monads in Lean should obey [certain laws](https://lean-lang.org/doc/reference/latest/Functors___-Monads-and--do--Notation/Laws/).\nThose are:\n\n**Left identity**: wrapping a value in pure and immediately passing it to\nf with bind should be equivalent to just calling f on the value:\n\n```\npure v >>= f       =    f v\n```\n\n**Right identity**: extracting a value from a computation and immediately\nwrapping it with pure again should not change the computation:\n\n```\nm >>= pure         =    m\n```\n\n**Associativity**: the grouping of operations doesn't matter, as long as their\norder remains the same:\n\n```\n(m >>= f) >>= g    =    m >>= (fun v => f v >>= g)\n```\n\nLet's see how Option obeys these laws.\n\nFor left identity, pure v is some v and the bind implementation\nmatches some x to next x, which is equivalent to f v.\n\nFor right identity, m >>= pure just rewraps a some value in pure,\nleaving none alone - this is equivalent to keeping things as they are.\n\nFor associativity, if m is none then both sides are none. If m\nis some v, the left side is f v >>= g, and the right side reduces to\nthe same, so again they are equivalent.\n\nWhile Lean doesn't enforce that a Monad instance obeys these laws, it has\na separate type class called LawfulMonad which *does* require Lean proofs;\nthis is useful for Lean's main use case - proving theorems about programs,\nexpressed through its powerful type system. But this is a topic for another\nday.\n\n---\n\n|  |  |\n| --- | --- |\n| [[1]](#footnote-reference-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. |\n\n|  |  |\n| --- | --- |\n| [[2]](#footnote-reference-2) | This is explored in Philip Wadler's classical paper \"The essence of functional programming\". |\n\n|  |  |\n| --- | --- |\n| [[3]](#footnote-reference-3) | Except also happens to implement Monad. |\n\n|  |  |\n| --- | --- |\n| [[4]](#footnote-reference-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. |\n","body_html":"<h1 id=\"monads-in-lean\">Monads in Lean</h1>\n<p>This post demonstrates how to use monads in the Lean programming language\n(Lean 4, to be specific). If you&#39;re not familiar with Lean, this part of the\nlanguage is very similar to other functional programming languages, like\nHaskell or OCaml.</p>\n<h2 id=\"motivating-example-evaluating-expressions\">Motivating example - evaluating expressions</h2>\n<p>Suppose we want to write a simple numerical expression evaluator that supports\nnumbers with addition and division:</p>\n<pre><code>inductive Expr where\n  | num : Int → Expr\n  | add : Expr → Expr → Expr\n  | div : Expr → Expr → Expr</code></pre>\n<p>What happens when we encounter a division by zero? We&#39;ll want our evaluator\nto report this as a failure, which will be represented explicitly using the\nthe Option type:</p>\n<pre><code>def safeDiv (x y : Int) : Option Int :=\n  if y == 0 then none else some (x / y)</code></pre>\n<p>With this in hand, the eval function can be written as follows:</p>\n<pre><code>def eval : Expr → Option Int\n  | .num n =&gt; some n\n  | .add a b =&gt;\n    match eval a with\n    | none =&gt; none\n    | some x =&gt;\n      match eval b with\n      | none =&gt; none\n      | some y =&gt; some (x + y)\n  | .div a b =&gt;\n    match eval a with\n    | none =&gt; none\n    | some x =&gt;\n      match eval b with\n      | none =&gt; none\n      | some y =&gt; safeDiv x y</code></pre>\n<p>safeDiv returns an Option; to propagate that possible failure to\nits caller, eval also returns an Option, and - moreover - has to perform\nlots of tedious checking for the possibility of a none value. Is there a\nbetter way?</p>\n<p>Note a common code pattern repeated here:</p>\n<ol><li>Examine the value of an Option</li><li>If it&#39;s none, return none without proceeding</li><li>Otherwise if it&#39;s some result, continue the computation with result</li></ol>\n<p>We can extract it into a helper function:</p>\n<pre><code>def withSome (result : Option α) (onSuccess : α → Option β) : Option β :=\n  match result with\n  | none =&gt; none\n  | some x =&gt; onSuccess x</code></pre>\n<p>And rewrite our eval using this helper:</p>\n<pre><code>def evalWithSome : Expr → Option Int\n  | .num n =&gt; some n\n  | .add a b =&gt;\n      withSome (evalWithSome a) (fun x =&gt;\n        withSome (evalWithSome b) (fun y =&gt;\n          some (x + y)))\n  | .div a b =&gt;\n      withSome (evalWithSome a) (fun x =&gt;\n        withSome (evalWithSome b) (fun y =&gt;\n          safeDiv x y))</code></pre>\n<p>This is already much better; we can make it even cleaner using operator\noverloading:</p>\n<pre><code>infixl:55 &quot; &gt;&gt;? &quot; =&gt; withSome\n\ndef evalOp : Expr → Option Int\n  | .num n =&gt; some n\n  | .add a b =&gt;\n    evalOp a &gt;&gt;? fun x =&gt;\n    evalOp b &gt;&gt;? fun y =&gt;\n    some (x + y)\n  | .div a b =&gt;\n    evalOp a &gt;&gt;? fun x =&gt;\n    evalOp b &gt;&gt;? fun y =&gt;\n    safeDiv x y</code></pre>\n<p>Congratulations - we&#39;ve pretty much invented monads!</p>\n<h2 id=\"option-as-a-monad-in-expression-evaluation\">Option as a Monad in expression evaluation</h2>\n<p>In simplified form, the Monad type class in Lean is defined as:</p>\n<pre><code>class Monad (m : Type → Type) where\n  pure : α → m α\n  bind : m α → (α → m β) → m β</code></pre>\n<p>In our code, pure is equivalent to some, and bind is equivalent\nto withSome; in fact, the Monad instance for Option is something\nlike:</p>\n<pre><code>instance : Monad Option where\n  pure x := some x\n  bind opt next :=\n    match opt with\n    | none =&gt; none\n    | some x =&gt; next x</code></pre>\n<p>An operator akin to &gt;&gt;? for monads is already defined in Lean; it&#39;s called</p>\n<blockquote><blockquote><p>=, and picks up the bind method of the Monad type class. So we can\nrewrite our evaluator using the standard Monad instance, without defining\nwithSome or the &gt;&gt;? operator <a href=\"#footnote-1\">[1]</a>:</p></blockquote></blockquote>\n<pre><code>def evalBind : Expr → Option Int\n  | .num n =&gt; pure n\n  | .add a b =&gt;\n    evalBind a &gt;&gt;= fun x =&gt;\n    evalBind b &gt;&gt;= fun y =&gt;\n    some (x + y)\n  | .div a b =&gt;\n    evalBind a &gt;&gt;= fun x =&gt;\n    evalBind b &gt;&gt;= fun y =&gt;\n    safeDiv x y</code></pre>\n<p>We can go even further with the do notation, which is syntactic sugar around</p>\n<blockquote><blockquote><p>= that lets us rewrite the evaluator as:</p></blockquote></blockquote>\n<pre><code>def evalDo : Expr → Option Int\n  | .num n =&gt; pure n\n  | .add a b =&gt; do\n    let x ← evalDo a\n    let y ← evalDo b\n    some (x + y)\n  | .div a b =&gt; do\n    let x ← evalDo a\n    let y ← evalDo b\n    safeDiv x y</code></pre>\n<p>This notation should be familiar if you&#39;ve seen Lean code dealing with I/O;\nwe&#39;ll revisit I/O later in the post.</p>\n<h2 id=\"monads-for-modeling-side-effects\">Monads for modeling side effects</h2>\n<p>Functional programming languages place a lot of emphasis on <em>pure</em> functions\nthat are free of side effects. There&#39;s no question that such functions are\neasier to reason about, debug, and even optimize (by memoization). That said,\nthe real world is messy and sometimes side effects are inescapable; monads\nhelp encapsulate side effects in functional programs.</p>\n<p>The core idea is: side effects are encapsulated inside a Monad, which\nwraps the value returned from a computation. The bind method (or the\nequivalent &gt;&gt;= operator) lets us take a wrapped value and push it into the\nnext computation in the sequence. This may look familiar from\ncontinuation-passing style (CPS). Continuations themselves can also be modeled\nwith a monad <a href=\"#footnote-2\">[2]</a>.</p>\n<p>The definition of bind is:</p>\n<pre><code>bind : m α → (α → m β) → m β</code></pre>\n<p>Here&#39;s a mental model to think about it:</p>\n<ol><li>Take a value wrapped with potential side effects</li><li><p>Take a computation that takes this value and may produce additional side</p><p> effects</p></li><li>Combine the results into a final wrapped value</li></ol>\n<p>Chaining multiple binds together is essentially a sequence of computations\nwhile keeping track of the side effects. A monad decouples what computations\n<em>do</em> from <em>how they are sequenced</em>. The programmer describes the sequence of\ncomputations and their dependencies, while the monad&#39;s bind implementation\nhandles the bookkeeping necessary to combine their side effects.</p>\n<p>Our evaluator case study shows one example of side effects: early return from\na computation with a none value.</p>\n<p>Let&#39;s see another idiomatic way of doing that, with the Except type that\ncontains either a successful result or an error value (very similar to the\nResult type in Rust).</p>\n<p>We&#39;ll begin by writing an exception-returning version of safeDiv:</p>\n<pre><code>def safeDivExc (x y : Int) : Except String Int :=\n  if y == 0 then .error &quot;division by zero&quot; else .ok (x / y)</code></pre>\n<p>Instead of writing a whole new eval variant for Except, we&#39;ll\ncreate a generic one that works with any Monad <a href=\"#footnote-3\">[3]</a>:</p>\n<pre><code>def evalM {m : Type → Type} [Monad m]\n    (div : Int → Int → m Int) : Expr → m Int\n  | .num n =&gt; pure n\n  | .add a b =&gt;\n    do\n      let x ← evalM div a\n      let y ← evalM div b\n      pure (x + y)\n  | .div a b =&gt;\n    do\n      let x ← evalM div a\n      let y ← evalM div b\n      div x y</code></pre>\n<p>Now evalM can be used with safeDivExc to implement an evaluator where\ndivision returns Except; used with safeDiv, it would be equivalent to\nthe Option-specific evalDo we&#39;ve written before.</p>\n<pre><code>#eval evalM safeDiv (.add (.num 4) (.div (.num 6) (.num 0)))\n#eval evalM safeDivExc (.add (.num 4) (.div (.num 6) (.num 0)))</code></pre>\n<h2 id=\"logging-computations-an-example-of-the-writer-monad\">Logging computations - an example of the writer monad</h2>\n<p>Let&#39;s look at a more advanced example: an evaluator that also <em>logs</em> the\ncomputation it executes in a linear log of strings. The challenge here is that\nwe still have to combine that with Option to support the divide-by-zero\ncase, so we&#39;ll start by creating a new structure to carry the state of the\ncomputation:</p>\n<pre><code>structure LoggedOption (α : Type) where\n  value : Option α\n  log : List String</code></pre>\n<p>This will be the result of one eval call; it produces an optional value,\nalong with a list of strings (the log). Here&#39;s the Monad implementation for\nthis type:</p>\n<pre><code>instance : Monad LoggedOption where\n  pure x := ⟨some x, []⟩\n  bind v next :=\n    match v.value with\n    | none =&gt; ⟨none, v.log⟩\n    | some x =&gt;\n      let nextResult := next x\n      ⟨nextResult.value, v.log ++ nextResult.log⟩</code></pre>\n<p>The main idea is combining the stored log with the log of the next computation\nby appending them (thus accumulating a linear log). Here&#39;s our evaluator:</p>\n<pre><code>def evalLogged : Expr → LoggedOption Int\n  | .num n =&gt; pure n\n  | .add a b =&gt; do\n    let x ← evalLogged a\n    let y ← evalLogged b\n    ⟨some (x + y), [s!&quot;adding {x} and {y}&quot;]⟩\n  | .div a b =&gt; do\n    let x ← evalLogged a\n    let y ← evalLogged b\n    match y with\n    | 0 =&gt; ⟨none, [s!&quot;dividing {x} by zero&quot;]⟩\n    | _ =&gt; ⟨some (x / y), [s!&quot;dividing {x} by {y}&quot;]⟩</code></pre>\n<p>Note how the code of evalLogged doesn&#39;t have to deal with the mechanics\nof logging too much (other than adding new log entries). All of that is hidden\nwithin the monad instance. LoggedOption is an example of the <em>writer monad</em>,\nwhich is a write-only version of the <em>state monad</em>.</p>\n<h2 id=\"state-monad\">State monad</h2>\n<p>One of the most important use cases of monads in functional programming\nlanguages is modeling mutable state through a computation.</p>\n<p>A stateful computation is modeled as a function that takes an initial state\nand returns a tuple containing the result value and a new, updated state. In\nLean notation:</p>\n<pre><code>def State (σ : Type) (α : Type) : Type :=\n  σ → (α × σ)</code></pre>\n<p>To demonstrate this in action, let&#39;s enhance our evaluator to support variable\nassignments and lookups. Our state is going to be an association list of\nname, value pairs:</p>\n<pre><code>abbrev Vars := List (String × Int)</code></pre>\n<p>And we&#39;ll augment our expression enum with additional operations:</p>\n<pre><code>inductive ExprV where\n  | num : Int → ExprV\n  | add : ExprV → ExprV → ExprV\n  | div : ExprV → ExprV → ExprV\n  | store : String → ExprV → ExprV\n  | load : String → ExprV</code></pre>\n<p>This is going to be our state monad:</p>\n<pre><code>structure EvalM (α : Type) where\n  run : Vars → Option (α × Vars)</code></pre>\n<p>Note the correspondence of the run function to the State signature\nabove:</p>\n<ul><li><p>It takes the current state, which for our use cases is an association list</p><p>carrying values for all defined variables.</p></li><li><p>It returns an optional result which is a pair of some value (in our case,</p><p>the result of the computation) and an updated state.</p></li></ul>\n<p>This is its Monad class implementation:</p>\n<pre><code>instance : Monad EvalM where\n  pure x := ⟨fun vars =&gt; some (x, vars)⟩\n  bind action next := ⟨fun vars =&gt;\n    match action.run vars with\n    | none =&gt; none\n    | some (x, vars&#39;) =&gt; (next x).run vars&#39;⟩</code></pre>\n<p>And finally, the evaluator:</p>\n<pre><code>def evalState : ExprV → EvalM Int\n  | .num n =&gt; pure n\n  | .add a b =&gt; do\n    let x ← evalState a\n    let y ← evalState b\n    pure (x + y)\n  | .div a b =&gt; do\n    let x ← evalState a\n    let y ← evalState b\n    ⟨fun vars =&gt; (safeDiv x y).map (fun value =&gt; (value, vars))⟩\n  | .load name =&gt;\n    ⟨fun vars =&gt; do\n      let value ← vars.lookup name\n      pure (value, vars)⟩\n  | .store name rhs =&gt; do\n    let value ← evalState rhs\n    ⟨fun vars =&gt;\n      let vars&#39; := (name, value) :: vars.filter (fun p =&gt; p.1 != name)\n      some (value, vars&#39;)⟩</code></pre>\n<p>Operations that don&#39;t deal with variables directly (like .num and\n.add) just do their work as before. .div only has to deal with the\nactual monad type to ensure that none is propagated in case of division\nby zero. Note also that this evaluator supports stores as expressions, since\nthey separately return a value and the updated state; therefore, computations\nlike this one will work:</p>\n<pre><code>-- (x := 12) + (x / 3): the right operand sees the left operand&#39;s assignment.\n#eval (evalState\n  (.add (.store &quot;x&quot; (.num 12))\n        (.div (.load &quot;x&quot;) (.num 3)))).run []</code></pre>\n<p>Producing the result some (16, [(&quot;x&quot;, 12)]).</p>\n<p>In a language with mutable state, modeling side effects is easy - just assign\nsome state (like a struct field or class member). In a functional language like\nLean, however, we have to carry this state across the computations explicitly;\nmonads help us do this with elegance - by hiding most of the mechanics of\nactually carrying the state around, the majority of the code remains free\nof bookkeeping.</p>\n<h2 id=\"io-monad\">IO monad</h2>\n<p>Perhaps the most well known example of a monad in functional programming\nlanguages like Lean and Haskell is IO. To anyone who&#39;s written a &quot;real&quot;\nprogram that interacts with the outer world, IO is very familiar. Here&#39;s\na customized &quot;Hello&quot; program that&#39;s typically taught in the first 15\nminutes of learning a new programming language:</p>\n<pre><code>def greet : IO Unit := do\n  let stdin ← IO.getStdin\n  IO.println &quot;What is your name?&quot;\n  let name ← stdin.getLine\n  IO.println s!&quot;Hello, {name}&quot;</code></pre>\n<p>Note the do notation here, suggesting monads. As mentioned before, do\nis syntactic sugar for the monad&#39;s bind method, or the &gt;&gt;= operator; we\ncan rewrite this code more explicitly as:</p>\n<pre><code>def greetBind : IO Unit :=\n  IO.getStdin &gt;&gt;= fun stdin =&gt;\n  IO.println &quot;What is your name?&quot; &gt;&gt;= fun _ =&gt;\n  stdin.getLine &gt;&gt;= fun name =&gt;\n  IO.println s!&quot;Hello, {name}&quot;</code></pre>\n<p>In essence, IO is a state monad, where the state carried around represents\nthe &quot;outside world&quot;. IO operations like println act on that world,\nand its state is carried over using bind, like other state monads.</p>\n<p>Here&#39;s a version of our expression evaluator that logs directly to standard out,\ninstead of collecting the log as a list of strings:</p>\n<pre><code>def evalIO : Expr → OptionT IO Int\n  | .num n =&gt; pure n\n  | .add a b =&gt; do\n    let x ← evalIO a\n    let y ← evalIO b\n    IO.println s!&quot;adding {x} and {y}&quot;\n    pure (x + y)\n  | .div a b =&gt; do\n    let x ← evalIO a\n    let y ← evalIO b\n    IO.println s!&quot;dividing {x} by {y}&quot;\n    OptionT.mk (pure (safeDiv x y))</code></pre>\n<p>The only unusual construct here is OptionT, which is a <em>monad transformer</em>\nthat helps us compose Option (for propagating failure from safe division)\nwith the IO Monad <a href=\"#footnote-4\">[4]</a>.</p>\n<p>The IO monad also supports throw for Python-like exception behavior,\nbut in this example we use Option explicitly; exceptions are a matter of\nprogramming preference, and using them inside library functions like eval\ndoesn&#39;t feel right to me.</p>\n<h2 id=\"monad-laws-in-lean\">Monad laws in Lean</h2>\n<p>Just like in Haskell, monads in Lean should obey <a href=\"https://lean-lang.org/doc/reference/latest/Functors___-Monads-and--do--Notation/Laws/\" rel=\"nofollow ugc noopener\">certain laws</a>.\nThose are:</p>\n<p><strong>Left identity</strong>: wrapping a value in pure and immediately passing it to\nf with bind should be equivalent to just calling f on the value:</p>\n<pre><code>pure v &gt;&gt;= f       =    f v</code></pre>\n<p><strong>Right identity</strong>: extracting a value from a computation and immediately\nwrapping it with pure again should not change the computation:</p>\n<pre><code>m &gt;&gt;= pure         =    m</code></pre>\n<p><strong>Associativity</strong>: the grouping of operations doesn&#39;t matter, as long as their\norder remains the same:</p>\n<pre><code>(m &gt;&gt;= f) &gt;&gt;= g    =    m &gt;&gt;= (fun v =&gt; f v &gt;&gt;= g)</code></pre>\n<p>Let&#39;s see how Option obeys these laws.</p>\n<p>For left identity, pure v is some v and the bind implementation\nmatches some x to next x, which is equivalent to f v.</p>\n<p>For right identity, m &gt;&gt;= pure just rewraps a some value in pure,\nleaving none alone - this is equivalent to keeping things as they are.</p>\n<p>For associativity, if m is none then both sides are none. If m\nis some v, the left side is f v &gt;&gt;= g, and the right side reduces to\nthe same, so again they are equivalent.</p>\n<p>While Lean doesn&#39;t enforce that a Monad instance obeys these laws, it has\na separate type class called LawfulMonad which <em>does</em> require Lean proofs;\nthis is useful for Lean&#39;s main use case - proving theorems about programs,\nexpressed through its powerful type system. But this is a topic for another\nday.</p>\n<hr />\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#footnote-reference-1\">[1]</a></td><td>We&#39;ve replaced some n by pure n in the .num case; technically this isn&#39;t necessary, but it will be useful later in the post when we examine other types implementing Monad.</td></tr></tbody></table></div>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#footnote-reference-2\">[2]</a></td><td>This is explored in Philip Wadler&#39;s classical paper &quot;The essence of functional programming&quot;.</td></tr></tbody></table></div>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#footnote-reference-3\">[3]</a></td><td>Except also happens to implement Monad.</td></tr></tbody></table></div>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#footnote-reference-4\">[4]</a></td><td>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.</td></tr></tbody></table></div>","headings":[{"level":1,"text":"Monads in Lean","id":"monads-in-lean"},{"level":2,"text":"Motivating example - evaluating expressions","id":"motivating-example-evaluating-expressions"},{"level":2,"text":"Option as a Monad in expression evaluation","id":"option-as-a-monad-in-expression-evaluation"},{"level":2,"text":"Monads for modeling side effects","id":"monads-for-modeling-side-effects"},{"level":2,"text":"Logging computations - an example of the writer monad","id":"logging-computations-an-example-of-the-writer-monad"},{"level":2,"text":"State monad","id":"state-monad"},{"level":2,"text":"IO monad","id":"io-monad"},{"level":2,"text":"Monad laws in Lean","id":"monad-laws-in-lean"}]}}