Research / 2025 –

Composing effects: monads and Kleisli arrows

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

Effectful pipelines as Kleisli arrows: the monad laws are exactly the category laws for arrow composition, which makes it possible to build a pipeline before any value exists, run it in a synchronous or an asynchronous monad, and refactor it without changing what it computes.

MonadsKleisli categoryProgram composition
3
monad laws, which are exactly the identity and associativity laws of Kleisli composition
14
ways to bracket a composition of five arrows; associativity makes them all equal
5 → 20
the running example: double, then add ten, built as an arrow before the input exists

A data pipeline is a chain of steps. Some steps are pure functions. Others may fail, wait on I/O, or log. If every step is written as a function from a plain value to a value in some context (possibly absent, possibly later), then three things become possible. The steps compose with one operator. The composite can be built before any input exists and run later. The composite can be regrouped, split or inlined without changing its meaning. All three follow from the monad laws. This article derives them from the definitions and then looks at two practical extensions: domain-specific operations, and pipelines written as nested lists with branches.

Monads

Monad. A monad on a category of types is a type constructor MM with two operations

ηA:A→MA(unit, written pure)(≫ ⁣=):MA→(A→MB)→MB(bind, written >>=)\begin{aligned} \eta_A &: A \to M A &&(\text{unit, written } \texttt{pure}) \\ (\gg\!=) &: M A \to (A \to M B) \to M B &&(\text{bind, written } \texttt{>>=}) \end{aligned}

satisfying, for all a:Aa : A, m:MAm : M A, f:A→MBf : A \to M B, g:B→MCg : B \to M C:

  1. left identity: η(a)≫ ⁣=f  =  f(a)\eta(a) \gg\!= f \;=\; f(a)
  2. right identity: m≫ ⁣=η  =  mm \gg\!= \eta \;=\; m
  3. associativity: (m≫ ⁣=f)≫ ⁣=g  =  m≫ ⁣=(λx. f(x)≫ ⁣=g)(m \gg\!= f) \gg\!= g \;=\; m \gg\!= (\lambda x.\, f(x) \gg\!= g)

The two smallest examples are enough for this article. The identity monad has MA=AM A = A, η=id\eta = \mathrm{id} and m≫ ⁣=f=f(m)m \gg\!= f = f(m). The option monad has MA=A+{⊥}M A = A + \lbrace \bot \rbrace, with ⊥≫ ⁣=f=⊥\bot \gg\!= f = \bot. In Lean, unit and bind are the two operations of the Monad class, written pure and >>=. The identity monad is a one-field structure, and the option monad is the built-in Option:

/-- The identity monad: a box that just holds a value. -/
structure Box (α : Type) where
  value : α
deriving Repr

instance : Monad Box where
  pure x   := ⟨x⟩            -- η
  bind m k := k m.value      -- ≫=

-- The option monad is Lean's `Option`: `none >>= f = none`.

/-- Functor map, derived from bind and unit. -/
def mapM' [Monad M] (f : α → β) (m : M α) : M β := m >>= (pure ∘ f)

#eval (mapM' (· + 10) (mapM' (· * 2) (pure 5 : Box Nat))).value  -- 20
#eval mapM' (· * 2) (none : Option Nat)                          -- none

-- the three laws hold for Box by unfolding the definitions
example (a : α) (f : α → Box β) : (pure a >>= f) = f a := rfl
example (m : Box α) : (m >>= pure) = m := rfl
example (m : Box α) (f : α → Box β) (g : β → Box γ) :
    ((m >>= f) >>= g) = (m >>= fun x => f x >>= g) := rfl

Functor map need not be primitive. It is derived from bind and unit:

map f m  =  m≫ ⁣=(η∘f).\mathrm{map}\, f\, m \;=\; m \gg\!= (\eta \circ f).

Map is a functor. With map defined this way, map id=id\mathrm{map}\,\mathrm{id} = \mathrm{id} and map(g∘f)=map g∘map f\mathrm{map}(g \circ f) = \mathrm{map}\,g \circ \mathrm{map}\,f.

Proof. map id m=m≫ ⁣=η=m\mathrm{map}\,\mathrm{id}\,m = m \gg\!= \eta = m by right identity. For composition, map g (map f m)=(m≫ ⁣=η∘f)≫ ⁣=η∘g=m≫ ⁣=(λx. η(fx)≫ ⁣=η∘g)\mathrm{map}\,g\,(\mathrm{map}\,f\,m) = (m \gg\!= \eta\circ f) \gg\!= \eta \circ g = m \gg\!= (\lambda x.\, \eta(f x) \gg\!= \eta\circ g) by associativity, and η(fx)≫ ⁣=η∘g=η(g(fx))\eta(f x) \gg\!= \eta \circ g = \eta(g(f x)) by left identity. So the result is m≫ ⁣=η∘(g∘f)=map(g∘f) mm \gg\!= \eta \circ (g \circ f) = \mathrm{map}(g\circ f)\,m. ∎

In the identity monad, mapping doubling and then adding ten over pure 5 holds the value 20, as the first #eval above checks. For Box the three laws hold by rfl: they are true by unfolding the definitions.

Kleisli arrows form a category

Kleisli arrow. For a monad MM, a Kleisli arrow from AA to BB is a function f:A→MBf : A \to M B. Two arrows compose by Kleisli composition (written >=>):

(f> ⁣ ⁣= ⁣ ⁣>g)(x)  =  f(x)≫ ⁣=g,f:A→MB,  g:B→MC.(f \mathrel{>\!\!=\!\!>} g)(x) \;=\; f(x) \gg\!= g, \qquad f : A \to M B,\; g : B \to M C .

The Kleisli category. Types as objects, Kleisli arrows as morphisms, ηA\eta_A as the identity on AA and >=> as composition form a category. That is, η> ⁣ ⁣= ⁣ ⁣>f=f\eta \mathrel{>\!\!=\!\!>} f = f, f> ⁣ ⁣= ⁣ ⁣>η=ff \mathrel{>\!\!=\!\!>} \eta = f, and (f> ⁣ ⁣= ⁣ ⁣>g)> ⁣ ⁣= ⁣ ⁣>h=f> ⁣ ⁣= ⁣ ⁣>(g> ⁣ ⁣= ⁣ ⁣>h)(f \mathrel{>\!\!=\!\!>} g) \mathrel{>\!\!=\!\!>} h = f \mathrel{>\!\!=\!\!>} (g \mathrel{>\!\!=\!\!>} h).

Proof. Pointwise. (η> ⁣ ⁣= ⁣ ⁣>f)(x)=η(x)≫ ⁣=f=f(x)(\eta \mathrel{>\!\!=\!\!>} f)(x) = \eta(x) \gg\!= f = f(x) by left identity. (f> ⁣ ⁣= ⁣ ⁣>η)(x)=f(x)≫ ⁣=η=f(x)(f \mathrel{>\!\!=\!\!>} \eta)(x) = f(x) \gg\!= \eta = f(x) by right identity. For associativity,

((f> ⁣ ⁣= ⁣ ⁣>g)> ⁣ ⁣= ⁣ ⁣>h)(x)=(f(x)≫ ⁣=g)≫ ⁣=h=f(x)≫ ⁣=(λy. g(y)≫ ⁣=h)=(f> ⁣ ⁣= ⁣ ⁣>(g> ⁣ ⁣= ⁣ ⁣>h))(x),\begin{aligned} ((f \mathrel{>\!\!=\!\!>} g) \mathrel{>\!\!=\!\!>} h)(x) &= (f(x) \gg\!= g) \gg\!= h \\ &= f(x) \gg\!= (\lambda y.\, g(y) \gg\!= h) \\ &= (f \mathrel{>\!\!=\!\!>} (g \mathrel{>\!\!=\!\!>} h))(x), \end{aligned}

where the middle step is the associativity law. ∎

The converse also holds, given one more condition. Suppose >=> and η\eta satisfy the category laws, and >=> commutes with precomposition by plain functions: (f∘h)> ⁣ ⁣= ⁣ ⁣>g=(f> ⁣ ⁣= ⁣ ⁣>g)∘h(f \circ h) \mathrel{>\!\!=\!\!>} g = (f \mathrel{>\!\!=\!\!>} g) \circ h. Then bind defined by m≫ ⁣=f=(const m> ⁣ ⁣= ⁣ ⁣>f)(∗)m \gg\!= f = (\mathrm{const}\, m \mathrel{>\!\!=\!\!>} f)(\ast) satisfies the monad laws. Left identity follows from const(η a)=η∘const a\mathrm{const}(\eta\,a) = \eta \circ \mathrm{const}\,a, and associativity uses the condition with h=const xh = \mathrm{const}\,x. Kleisli composition defined from a bind always satisfies this condition, since both sides send xx to f(h x)≫ ⁣=gf(h\,x) \gg\!= g, so the three monad laws and the three category laws are the same statement in two notations. The category form is the one a programmer uses, because it is about composing steps rather than about values.

A pure function f:A→Bf : A \to B becomes an arrow by postcomposing with the unit, η∘f\eta \circ f. Pure steps and effectful steps then live in the same category, and composing two lifted pure steps gives the lifted composite: (η∘f)> ⁣ ⁣= ⁣ ⁣>(η∘g)=η∘(g∘f)(\eta\circ f) \mathrel{>\!\!=\!\!>} (\eta\circ g) = \eta \circ (g \circ f), by left identity.

Lean’s core library defines >=> exactly as above. For any monad with a LawfulMonad instance, the category laws and the lifting law are short proofs:

-- continues the definitions above
-- Lean's core library already defines `f >=> g := fun x => f x >>= g`.
section
variable [Monad M] [LawfulMonad M]

theorem kleisli_id_left (f : α → M β) : (pure >=> f) = f := by
  funext x; simp [Bind.kleisliRight]

theorem kleisli_id_right (f : α → M β) : (f >=> pure) = f := by
  funext x; simp [Bind.kleisliRight]

theorem kleisli_assoc (f : α → M β) (g : β → M γ) (h : γ → M δ) :
    ((f >=> g) >=> h) = (f >=> (g >=> h)) := by
  funext x; simp only [Bind.kleisliRight, bind_assoc]; rfl

/-- Lifted pure steps compose to the lifted composite. -/
theorem kleisli_pure (f : α → β) (g : β → γ) :
    ((pure ∘ f : α → M β) >=> (pure ∘ g)) = pure ∘ (g ∘ f) := by
  funext x; simp [Bind.kleisliRight]
end

Staging: the arrow before the value

A monadic value m:MAm : M A is a computation that has already been given its input. A Kleisli arrow is a computation still waiting for one. This difference is useful in practice. A pipeline can be built, stored, passed around and extended as a first-class value, and nothing runs until it is applied.

A simple representation is a list of steps with a runner. In Lean the list is type-aligned: each step’s input type must match the previous step’s output type, so an arrow from AA to BB is a path of composable steps. Composition is list concatenation:

-- continues the definitions above
/-- An arrow is a list of steps (a type-aligned snoc list). -/
inductive Arrow (M : Type → Type) : Type → Type → Type 1 where
  | nil  : Arrow M α α                               -- η
  | snoc : Arrow M α β → (β → M γ) → Arrow M α γ     -- a >=> k

namespace Arrow
variable [Monad M]
def chain (a : Arrow M α β) (k : β → M γ) : Arrow M α γ := a.snoc k
def map (a : Arrow M α β) (f : β → γ) : Arrow M α γ := a.snoc (pure ∘ f)
/-- `f >=> g`: concatenate the step lists. -/
def compose (a : Arrow M α β) : Arrow M β γ → Arrow M α γ
  | nil      => a
  | snoc b k => (a.compose b).snoc k
/-- `η >=> k₁ >=> ⋯ >=> kₙ`, applied to `x`. -/
def run : Arrow M α β → α → M β
  | nil,      x => pure x
  | snoc a k, x => a.run x >>= k
end Arrow

/-- Built with no input, and for any monad. -/
def p [Monad M] : Arrow M Nat Nat := (Arrow.nil.map (· * 2)).map (· + 10)

#eval (p.run 5 : Box Nat).value  -- 20
  1. build
    empty arrow
    Arrow.nil
  2. step 1
    double
    fun x => x * 2
  3. step 2
    add ten
    fun x => x + 10
  4. run
    apply to 5
    5 → 10 → 20
  5. result
    M(20)
Fig. 1A staged arrow. The two steps are composed into one arrow before any input exists. Applying it to 5 yields the monadic value holding 20.

The runner starts from η(x)\eta(x) and folds bind over the steps. By left identity the result is (k1(x)≫ ⁣=k2)≫ ⁣=⋯(k_1(x) \gg\!= k_2) \gg\!= \cdots, and by associativity this left-nested bind equals (k1> ⁣ ⁣= ⁣ ⁣>⋯> ⁣ ⁣= ⁣ ⁣>kn)(x)(k_1 \mathrel{>\!\!=\!\!>} \cdots \mathrel{>\!\!=\!\!>} k_n)(x). The empty arrow runs as η\eta. In the identity monad, an implementation may unwrap each intermediate result and apply plain functions in a loop, wrapping only at the end. That is a valid optimisation, because in that monad m≫ ⁣=km \gg\!= k is just k(m)k(m).

One interface, two monads

The same builder works over an asynchronous monad whose values are “a result, later”. Its unit is “resolve now” and its bind is “when the result arrives, feed it to the next step”. A faithful model is continuation passing: a value of Later α is a procedure that will, at some point, hand an α to whatever callback it is given. Code written against pure, map and >>= does not change. The arrow p above is polymorphic in the monad, and only the choice of monad at the call site decides whether the pipeline completes synchronously or delivers its result later:

-- continues the definitions above
/-- "A result, later": continuation-passing over IO. -/
def Later (α : Type) := (α → IO Unit) → IO Unit

instance : Monad Later where
  pure x   := fun k => k x                  -- resolve now
  bind m f := fun k => m (fun a => f a k)   -- when a arrives, feed it to f

-- the same arrow `p`, now run in the asynchronous monad
#eval (p.run 5 : Later Nat) (fun r => IO.println r)   -- prints 20

-- the laws hold definitionally: bind never inspects the value
example (a : α) (f : α → Later β) : (pure a >>= f) = f a := rfl
example (m : Later α) : (m >>= pure) = m := rfl
example (m : Later α) (f : α → Later β) (g : β → Later γ) :
    ((m >>= f) >>= g) = (m >>= fun x => f x >>= g) := rfl

-- a later-of-a-later is its own type; nothing flattens it implicitly
#check (pure (pure 1 : Later Nat) : Later (Later Nat))

In Later, bind is a direct function call, so a chain of steps runs to completion at once unless one of the steps defers its callback.

Why the box matters

The laws for Later hold by rfl because its unit and bind never inspect the value they pass on. Not every asynchronous carrier has this property. Suppose a carrier’s unit and bind flatten any value that is itself a pending result, so that a pending result of a pending result cannot exist. Then bind and map coincide, since a callback’s result is flattened if it is pending and wrapped otherwise. Left identity also fails whenever the lifted value aa is itself pending: η(a)≫ ⁣=f\eta(a) \gg\!= f applies ff to the result inside aa, while f(a)f(a) applies ff to aa itself, and a function ff that reports whether its argument is pending tells the two apart. On such a carrier the laws hold only for pipelines whose intermediate values are never pending. A lawful asynchronous monad keeps the box, as Later does, so that M(MA)M(MA) stays distinct from MAMA. Later is also lazy: it does nothing until it is handed a callback. Staging gives the same laziness at the level of the whole pipeline in any monad, because an arrow does nothing until it is run.

Extending arrows, and failure

A domain-specific vocabulary (string operations, database operations, validation) can be added to the builder without leaving the category. Given operations φi:A×Pi→B\varphi_i : A \times P_i \to B, attach a method per operation. In Lean a method is a definition in the Arrow namespace, so a.trim means Arrow.trim a, and a tag records whether an operation is pure or already an arrow:

-- continues the definitions above
/-- A step is either a pure function or an arrow, with an explicit tag. -/
inductive Step (M : Type → Type) (α β : Type) where
  | fn    : (α → β) → Step M α β       -- lifted with η
  | arrow : (α → M β) → Step M α β     -- used as is

def Step.toK [Monad M] : Step M α β → α → M β
  | .fn f    => pure ∘ f
  | .arrow k => k

def Arrow.andThen [Monad M] (a : Arrow M α β) (s : Step M β γ) : Arrow M α γ :=
  a.snoc s.toK

-- a domain vocabulary: each operation is a method in the `Arrow` namespace
def Arrow.trim [Monad M] (a : Arrow M α String) := a.andThen (.fn String.trim)
def Arrow.append [Monad M] (s : String) (a : Arrow M α String) :=
  a.andThen (.fn (· ++ s))        -- the parameter is fixed when called
def Arrow.nonEmpty (a : Arrow Option α String) :=
  a.andThen (.arrow fun s => if s.isEmpty then none else some s)

#eval ((Arrow.nil.trim.nonEmpty.append "!").run "  hi " : Option String)  -- some "hi!"
#eval ((Arrow.nil.trim.nonEmpty.append "!").run "   " : Option String)    -- none

Each attached method postcomposes one Kleisli morphism: η∘φi(⋅,p)\eta \circ \varphi_i(\cdot, p) for a pure operation, or the operation itself if it is already an arrow. The parameters pp are fixed when the method is called, so the appended step is still a function of the current value alone. A pipeline made of extension methods is a composite of Kleisli arrows, and every law in this article applies to it unchanged.

Failure fits the same way, provided failure is a value in the monad. In the option monad:

-- continues the definitions above
def safeDiv (d : Nat) (x : Nat) : Option Nat := if d = 0 then none else some (x / d)
def add10 (x : Nat) : Option Nat := some (x + 10)

#eval (safeDiv 2 >=> add10) 8   -- some 14
#eval (safeDiv 0 >=> add10) 8   -- none

The add10 step is never run in the second case, because ⊥≫ ⁣=f=⊥\bot \gg\!= f = \bot.

Failure signalled by exceptions behaves differently, and the difference is about evaluation order. Consider a recovery combinator recover that returns its argument if reading it succeeds and a default otherwise, applied to pure 1 mapped through a step boom that throws. In a strict language where synchronous code fails by throwing, this cannot work. The exception is raised while the argument is being evaluated, before recover is called. In a monad whose bind runs each callback under a handler and turns an exception into a failed result, the same expression does work, because recover receives that failed result and can replace it. To make recovery work synchronously, either make failure a value (the option or either monad), or wrap the step in a combinator that catches the exception when the step is applied. Inspecting the result afterwards is too late. Lean’s pure code cannot throw at all, so it takes the first route: failure is an Except value, and recovery is a handler on that value.

-- continues the definitions above
-- failure as a value: `Except` carries it, `tryCatch` replaces it
def boom (_ : Nat) : Except String Nat := throw "boom"
def recover (d : α) (m : Except String α) : Except String α :=
  tryCatch m (fun _ => pure d)

#eval recover 0 (pure 1 >>= boom)   -- Except.ok 0

Trees of arrows

Long pipelines are easier to write as data. For steps of a single type A→MAA \to M A, a pipeline tree is the inductive type below. A branch maps labels to sub-trees and has an optional selector of its own:

-- continues the definitions above
/-- A pipeline tree over steps of type `α → M α`. -/
inductive Node (M : Type → Type) (α : Type) where
  | fn     : (α → α) → Node M α                  -- pure, lifted by η
  | arrow  : (α → M α) → Node M α                -- Kleisli, used as is
  | seq    : List (Node M α) → Node M α          -- a sequence
  | branch : List (String × Node M α) → Option (α → String) → Node M α

with the denotation

⟦f⟧=η∘f,⟦k⟧=k,⟦[n1,…,nr]⟧=⟦n1⟧> ⁣ ⁣= ⁣ ⁣>⋯> ⁣ ⁣= ⁣ ⁣>⟦nr⟧,⟦[ ]⟧=η,\llbracket f \rrbracket = \eta \circ f, \quad \llbracket k \rrbracket = k, \quad \llbracket [n_1, \dots, n_r] \rrbracket = \llbracket n_1 \rrbracket \mathrel{>\!\!=\!\!>} \cdots \mathrel{>\!\!=\!\!>} \llbracket n_r \rrbracket, \quad \llbracket [\,] \rrbracket = \eta, ⟦B⟧=λx.  ⟦B[π(x)]⟧(x),\llbracket B \rrbracket = \lambda x.\; \llbracket B[\pi(x)] \rrbracket (x),

where π\pi is the branch’s own selector if it has one and an inherited default otherwise, and a label with no entry denotes η\eta. The denotation transcribes directly into Lean, one equation per case:

-- continues the definitions above
variable [Monad M] (dflt : α → String) in
mutual
def Node.denote : Node M α → α → M α
  | .fn f          => pure ∘ f
  | .arrow k       => k
  | .seq ns        => denoteSeq ns
  | .branch bs sel => fun x => denoteAt bs ((sel.getD dflt) x) x
def denoteSeq : List (Node M α) → α → M α        -- ⟦[]⟧ = η
  | []      => pure
  | n :: ns => n.denote >=> denoteSeq ns
def denoteAt : List (String × Node M α) → String → α → M α
  | [],           _   => pure                    -- missing label: η
  | (l, n) :: bs, lab => if l = lab then n.denote else denoteAt bs lab
end

Flattening. Any two pipeline trees with the same left-to-right sequence of leaves (and no branches) denote the same arrow. In particular, every nesting of a sequence is equivalent to its flat form.

Sketch. Induction on the tree. A nested sequence denotes the composite of its children. Associativity lets the inner composite be re-bracketed into the outer one, and the identity laws remove empty sequences. ∎

When every step has type A→MAA \to M A, the arrows form a monoid under >=> with unit η\eta. A branch-free pipeline tree is then a bracketed word in the free monoid on its steps, and its meaning depends only on the flattened word. With heterogeneous types the same statement holds in the free category, where a sequence is a path of composable steps. Five steps can be bracketed in 14 ways (the Catalan number C4C_4), and all 14 run the same computation:

/-- Number of ways to bracket a composition of `n + 1` arrows (Catalan). -/
def bracketings : Nat → Nat
  | 0     => 1
  | n + 1 => (List.finRange (n + 1)).foldl
      (fun s (i : Fin (n + 1)) => s + bracketings i * bracketings (n - i)) 0
  decreasing_by all_goals (have := i.isLt; omega)
#eval bracketings 4   -- 14

A branch is itself a Kleisli arrow. It reads the current value, picks a sub-pipeline and runs it on that value. A tree with branches therefore still denotes one arrow, and flattening applies inside each branch and around it. This is where a monad is strictly stronger than composing fixed steps: the choice of the next step depends on an earlier result.

Worked example, with parity as the default selector:

-- continues the definitions above
def parity (x : Nat) : String := if x % 2 = 0 then "even" else "odd"

def tree [Monad M] : Node M Nat :=
  .seq [.fn (· * 2), .seq [.fn (· + 10),
    .branch [("even", .seq [.fn (· / 2)]), ("odd", .seq [.fn (3 * · + 1)])] none]]

#eval (tree.denote parity 5 : Box Nat).value   -- 10   (5 → 10 → 20 → even → 10)
#eval (tree.denote parity 2 : Box Nat).value   -- 7    (2 →  4 → 14 → even →  7)
  1. input
    5
  2. map
    double
    5 → 10
  3. map
    add ten
    10 → 20
  4. branch
    parity: even
    parity 20 = "even"
  5. map
    halve
    20 → 10
Fig. 2The nested tree above, read as one composed arrow. Brackets disappear under associativity. The branch is an arrow that chooses its sub-pipeline from the current value.

Refactoring, costs and open questions

The laws are what make the following rewrites safe, for any lawful monad:

  • Inlining and extraction. Replacing a named sub-pipeline with its steps, or the reverse, is associativity.
  • Splitting and regrouping. Cutting a pipeline into stages that are built in different modules, then joined, is associativity again. Adding or removing a no-op stage is the identity law.
  • Map fusion. Two consecutive pure steps can be merged into one, map g∘map f=map(g∘f)\mathrm{map}\,g \circ \mathrm{map}\,f = \mathrm{map}(g \circ f), which saves one bind per pair.
  • Absorbing pure steps. By left identity, (η∘f)> ⁣ ⁣= ⁣ ⁣>k=k∘f(\eta\circ f) \mathrel{>\!\!=\!\!>} k = k \circ f, so a pure preprocessing step can be folded into the next arrow, and the reverse.

None of these rewrites needs to know which monad will run the pipeline. That is why one pipeline can be written once and handed to a synchronous or an asynchronous runner.

Costs. With the snoc-list Arrow above, appending a step is O(1)O(1), so building nn steps is O(n)O(n), and compose costs time linear in the length of its second argument. Running costs nn step applications and nn binds. Interpreting a tree costs time linear in the number of nodes visited, plus one selector call and one scan of the branch’s labels per branch taken. In Later, each bind adds one closure and one call. Any scheduling cost comes from steps that defer their callback.

Limitations and open questions.

  • Without static types, a pure step and an arrow cannot be told apart from their values, so a builder needs an explicit tag such as Step. Mapping an arrow yields M(MB)M(MB) instead of MBMB, and binding a pure function is ill-typed. In Lean the types rule out both. The Node tree above is homogeneous. A heterogeneous tree is an indexed family like Arrow, defined mutually with its list of labelled cases, in which a branch from α to β holds sub-trees from α to β. A missing label can then no longer denote η, so such a branch also needs a default sub-tree.
  • The laws are equations between the values computed. Effects the monad tracks, such as logging in a writer monad, satisfy them exactly. Side effects hidden inside a function lifted with η are outside the model, and the laws say nothing about them.
  • Branch selectors see only the current value. A selector that reads outside state makes the branch a different arrow on every run, and equational reasoning then has to include that state in the monad.
  • Which other effects (cancellation, streaming, retry) can be given lawful units and binds that share this interface, and which need a weaker structure such as an applicative or an arrow in the sense of Hughes, is the question I am working on next.