Lean and its type theory — chapter 3
We know the recursor already, here are more details.
Recall: for an inductive type α, a function α → β is defined with the recursor α.rec. Pattern matching is a more convenient way to write it: one branch per constructor, each prefixed by |.
def factorial : ℕ → ℕ
| 0 => 1
| n + 1 => (n + 1) * factorial n
Lean checks automatically:
exhaustiveness: every constructor is covered,
termination: factorial n is on a smaller argument.
def MyNat.double : MyNat → MyNat
| .zero => .zero
| .succ n => .succ (.succ (MyNat.double n))
def MyNat.toNat : MyNat → ℕ
| .zero => 0
| .succ n => MyNat.toNat n + 1
#eval2 (MyNat.double (.succ .zero)).toNat -- 2
2
m.toNat means MyNat.toNat m.
Pattern matching is translated into the recursor for the kernel, and into running code for #eval.
inductive List (α : Type u) where
| nil : List α -- written []
| cons (a : α) (l : List α) :
List α -- written a :: l
#eval[1, 2, 3] (1 :: 2 :: 3 :: [] : List ℕ) -- [1, 2, 3]
[1, 2, 3]
A list is empty, or a first element followed by a list. [1, 2, 3] is notation for 1 :: 2 :: 3 :: [].
infixr:67 " :: " => List.cons -- Lean's core library syntax "[" term,* "]" : term -- simplified macro_rules | `([]) => `(List.nil) | `([$a]) => `(List.cons $a List.nil) | `([$a, $as,*]) => `(List.cons $a [$as,*])
infixr makes :: a right-associative infix operator with binding power 67, so 1 :: 2 :: [] is 1 :: (2 :: []). syntax declares the bracket form, macro_rules rewrites it, one element at a time, into List.cons and List.nil (more in chapter 1.7).
One branch per constructor; the pattern _ matches anything. match does the same inside a term.
def length' {α : Type*} : List α → ℕ
| [] => 0
| _ :: xs => 1 + length' xs
def isEmpty' {α : Type*} (l : List α) : Bool :=
match l with
| [] => true
| _ :: _ => false
A recursive call is structural if its argument is a part of the input: an argument of the constructor that built it.
def fib : ℕ → ℕ
| 0 => 0
| 1 => 1
| n + 2 => fib n + fib (n + 1)
example : fib 3 = 2 := rfl
n + 2 is succ (succ n); its parts are succ n = n + 1 and n. Both calls are structural.
fib computes by ι: fib 3 ⟶ fib 1 + fib 2 ⟶ 1 + (fib 0 + fib 1) ⟶ 1 + (0 + 1).
def loop (n : ℕ) : ℕ := loop n + 1 is rejected. It would give loop 0 = loop 0 + 1; subtract loop 0: 0 = 1.
fib (n + 2) needs two earlier values; Nat.rec hands over only one. By hand: carry the pair (fib n, fib (n + 1)).
α × β: the structure of pairs (a, b), with fields p.1 : α and p.2 : β (chapter 1.4).
def fibPair (n : ℕ) : ℕ × ℕ :=
Nat.rec (0, 1) (fun _ p => (p.2, p.1 + p.2)) n
example : fibPair 10 = (55, 89) := rfl
Lean's own translation of fib carries the values at all smaller arguments (later in this deck).

#check @MyNat.rec omits the case names zero, succ.

T.rec has no body; the kernel knows it only by its ι-rules. With R := T.rec f₁ … fₘ:
R (c₁ b₁ … bₗ r₁ … rₖ) ⟶ f₁ b₁ … bₗ r₁ … rₖ (R r₁) … (R rₖ)
List.recList.rec : {motive : List α → Sort u} →
motive [] → -- case nil
((head : α) → (tail : List α) →
motive tail → -- recursive argument
motive (head :: tail)) → -- case cons
(t : List α) → motive t
nil has no arguments; cons has head : α and the recursive argument tail : List α, so its case gets motive tail.
Computation: List.rec n c (a :: l) ⟶ c a l (List.rec n c l)
Read as a proof, motive tail is the induction hypothesis.
casesOn

casesOn t z s only asks which constructor built t. It is MyNat.rec z (fun n _ => s n) t; for ℕ: Nat.casesOn.
Lean first writes the patterns of fib with constructors: 0 is zero, 1 is succ zero, n + 2 is succ (succ n). Then it splits from the outside in:
fun x => Nat.casesOn x (case 0) -- x = zero
(fun m => Nat.casesOn m (case 1) -- x = succ m, m = zero
(fun n => (case n + 2))) -- x = succ (succ n)
So 1 is read in two steps: the outer split finds succ, the inner one finds zero. #print fib.match_1 shows exactly this term.
Every leaf must be reached by a pattern. Without the line for 1: "Missing cases: (Nat.succ Nat.zero)".
inductive BinTree where
| leaf : BinTree
| node (l : BinTree) (a : ℕ) (r : BinTree) : BinTree

BinTree is the type of all finite binary trees; each element is one tree.
leaf: a single leaf, no number. node l a r: root a, subtrees l, r.
All leaves are the same term .leaf; only their positions differ.
def BinTree.height : BinTree → ℕ
| .leaf => 0
| .node l _ r => max l.height r.height + 1
example : BinTree.leaf.height = 0 := rfl
example : (BinTree.node .leaf 4 .leaf).height = 1 := rfl
example : (BinTree.node .leaf 3
(.node .leaf 4 .leaf)).height = 2 := rfl
l and r are parts of .node l _ r: both calls are structural.

Cantor's enumeration of ℕ × ℕ: pairIndex m n is the position of (m, n).
No argument shrinks in both calls. The pair (m + n, m), diagonal and position, does.
Pairs are compared lexicographically: (a, b) < (c, d) iff a < c, or a = c and b < d.
def pairIndex : ℕ → ℕ → ℕ
| 0, 0 => 0
| 0, n + 1 => pairIndex n 0 + 1
| m + 1, n => pairIndex m (n + 1) + 1
termination_by m n => (m + n, m)
decreasing_by all_goals (rw [Prod.lex_defn:ℕ⊢ (n + 0, n).1 < (0 + n.succ, 0).1 ∨ (n + 0, n).1 = (0 + n.succ, 0).1 ∧ (n + 0, n).2 < (0 + n.succ, 0).2]n:ℕ⊢ (n + 0, n).1 < (0 + n.succ, 0).1 ∨ (n + 0, n).1 = (0 + n.succ, 0).1 ∧ (n + 0, n).2 < (0 + n.succ, 0).2m:ℕn:ℕ⊢ (m + (n + 1), m).1 < (m.succ + n, m.succ).1 ∨
(m + (n + 1), m).1 = (m.succ + n, m.succ).1 ∧ (m + (n + 1), m).2 < (m.succ + n, m.succ).2; omegaAll goals completed! 🐙)
def logb (b n : ℕ) : ℕ :=
if h : 2 ≤ b ∧ b ≤ n then 1 + logb b (n / b)
else 0
termination_by?Try this:
[apply] termination_by n
decreasing_by exact Nat.div_lt_self (byb:ℕn:ℕh:2 ≤ b ∧ b ≤ n⊢ 0 < n omegaAll goals completed! 🐙) h.1
termination_by? prints the measure Lean found: n. On ℕ the order is <. Lean cannot prove n / b < n by itself; decreasing_by gives the proof.
def log2 (n : Nat) : Nat :=
if 2 ≤ n then 1 + log2 (n / 2) else 0
example (n : ℕ) : fib (n + 2) = fib n + fib (n + 1) :=
rfl
example : log2 16 = 4 := by⊢ log2 16 = 4 simp [log2]All goals completed! 🐙
Structural recursion computes, so rfl works. Well-founded recursion does not: use the equation lemma log2.eq_1, via rw [log2], unfold log2 or simp [log2].
fib (n + 2) needs fib (n + 1) and fib n, the recursor hands over only one value. Lean's translation passes a table of all smaller values (Nat.brecOn; #print fib shows it). Carrying the pair by hand, as in fibPair, also makes #eval fast:
#eval fib 30 -- 0.6 s #eval fib 32 -- 1.7 s: about 7 million calls #eval (fibPair 32).1 -- immediate: 32 steps #eval (fibPair 10000).1 -- immediate, 2090 digits
#eval runs fib as written: every call makes two more, so the time grows like fib n itself, by a factor of about 1.6 per step.
The same works with a Prop-valued motive: a proof may use the statement for all smaller arguments, here two steps back.
theorem fib_pos : (n : ℕ) → 0 < fib (n + 1)
| 0 =>⊢ 0 < fib (0 + 1) by⊢ 0 < fib (0 + 1) decideAll goals completed! 🐙
| 1 =>⊢ 0 < fib (1 + 1) by⊢ 0 < fib (1 + 1) decideAll goals completed! 🐙
| n + 2 =>n:ℕ⊢ 0 < fib (n + 2 + 1) byn:ℕ⊢ 0 < fib (n + 2 + 1)
have h := fib_pos nn:ℕh:0 < fib (n + 1)⊢ 0 < fib (n + 2 + 1) -- two steps back
show 0 < fib (n + 1) + fib (n + 2)n:ℕh:0 < fib (n + 1)⊢ 0 < fib (n + 1) + fib (n + 2)
omegaAll goals completed! 🐙
MyTree is a type; its elements are trees. Every path ends in a leaf.
inductive MyTree where
| leaf (a : ℕ) : MyTree
| node (f : ℕ → MyTree) : MyTree

leaf a: the tree that is a single leaf, carrying the number a.
node f: the tree whose root has the subtrees f 0, f 1, f 2, …
In the type ℕ → MyTree of f, MyTree stands right of →. Accepted.
inductive Bad where | mk (f : Bad → False) : Bad -- error: (kernel) arg #1 of 'Bad.mk' has a non positive -- occurrence of the datatypes being declared
Strict positivity: in argument types of constructors, the type occurs only right of →. In the type Bad → False of f, Bad stands left of →.
If Lean accepted it, we would have mk and, by pattern matching | .mk f => f, its inverse unmk. Then:
example (Bad : Type) (mk : (Bad → False) → Bad)
(unmk : Bad → (Bad → False)) : False := byBad:Typemk:(∀ (a : Bad), False) → Badunmk:∀ (a a : Bad), False⊢ False
have neg : Bad → False := fun b => unmk b bBad:Typemk:(∀ (a : Bad), False) → Badunmk:∀ (a a : Bad), Falseneg:∀ (a : Bad), False⊢ False
have b : Bad := mk negBad:Typemk:(∀ (a : Bad), False) → Badunmk:∀ (a a : Bad), Falseneg:∀ (a : Bad), Falseb:Bad⊢ False
exact neg bAll goals completed! 🐙
Read in sets, the declared type X satisfies X = F(X):
declaration | equation |
|---|---|
|
|
|
|
|
|
X only right of →: F is monotone. The stages ∅ ⊆ F(∅) ⊆ F(F(∅)) ⊆ …, continued transfinitely, reach a fixed point: a set that is the type.
X → ∅ has one element if X = ∅, none otherwise: no solution, Bad ↔ ¬Bad.
With X → Bool instead: X would contain its power set. Cantor.
Proved for inductive types: Aczel 1977, Dybjer 1991; for the CIC: Werner 1997; for Lean, checked in Lean: Con-Leche (Breitner).
Pattern matching: one branch per constructor; Lean checks that every case is covered.
Recursion must terminate. Structural recursion calls itself on parts of the argument and becomes the recursor.
Well-founded recursion needs a measure that decreases; it is used through its equation lemmas, not rfl.
The recursor of a type has one case per constructor, with a value of the motive for every recursive argument.
Pattern matching becomes casesOn; structural recursion passes the values at all smaller arguments (brecOn, Project 7).
Constructors must be strictly positive.