Make wrong data impossible to write
Much of programming is deciding how to represent things. A library book has a title, an author and a year. A shape is a circle, or a rectangle, or a triangle, each with its own measurements. A search tree is either empty or a node with a key and two smaller trees. If the representation is sloppy, say a shape stored as a type tag string and four numbers of which some are ignored, then every function that uses it must check for nonsense, and some function eventually forgets.
Lean gives you two tools to represent data exactly. Structures bundle several values together: this and that and that. Inductive types list alternatives: this or that or that, where each alternative can carry its own data, and where an alternative can contain values of the very type being defined, which is how lists and trees are built. Between them they describe almost any data you will meet, and with pattern matching you take them apart again, with the compiler checking that you have handled every alternative.
These are not features bolted onto Lean. They are the heart of it: Nat, List, Option, Bool, even the logical connectives "and" and "or" of lesson 8, are all inductive types defined in Lean's own library, and every structure is an inductive type with a single alternative.
Structures
Definition— Structure
A structure is a type whose values have named fields. It is declared with structure Name where followed by one field per line, name : Type, optionally with a default value, name : Type := value. Lean generates a constructor, Name.mk, that builds a value from its fields, and a function for each field, Name.field, that reads it.
structure Book where
title : String
author : String
year : Nat
onLoan : Bool := false
deriving Repr, BEq
def Book.age (b : Book) (now : Nat) : Nat := now - b.year
def Book.label (b : Book) : String :=
let status := if b.onLoan then "on loan" else "on the shelf"
s!"{b.title} ({b.author}, {b.year}), {status}"
def achebe : Book := { title := "Things Fall Apart", author := "Chinua Achebe", year := 1958 }
def cervantes : Book := ⟨"Don Quixote", "Miguel de Cervantes", 1605, true⟩
#eval achebe
#eval achebe.title
#eval achebe.age 2026
#eval cervantes.label
#eval { achebe with onLoan := true }.label
#eval achebe == { achebe with onLoan := false }
#check Book.mk{ title := "Things Fall Apart", author := "Chinua Achebe", year := 1958, onLoan := false }
"Things Fall Apart"
68
"Don Quixote (Miguel de Cervantes, 1605), on loan"
"Things Fall Apart (Chinua Achebe, 1958), on loan"
true
Book.mk (title author : String) (year : Nat) (onLoan : Bool) : BookThere are two ways to build a Book. The structure instance notation { title := …, author := …, year := … } names each field, in any order, and may leave out fields with defaults (onLoan here). The anonymous constructor ⟨…⟩ (type \< and \>) lists the fields positionally; it is shorter, and common for small structures such as points, but a reader has to know the field order.
To "change" a field, you make a new value: { achebe with onLoan := true } is a copy of achebe with one field replaced. The original is untouched, as everything in Lean is. That sounds expensive, but it is not usually: Lean reuses the memory of a value that nothing else refers to any more, a technique lesson 7 explains.
Dot notation
Book.age is an ordinary function whose first explicit parameter is a Book. Because its name starts with Book., Lean lets you call it as achebe.age 2026: when you write x.f and x has type T, Lean looks for T.f and passes x as the first argument of type T. That is how "Lean".length became String.length "Lean" in lesson 1. Dot notation is the closest thing Lean has to methods, and it is how almost all Lean libraries are organised: functions on lists are List.something, on strings String.something, and you call them with a dot.
deriving
The line deriving Repr, BEq asks Lean to write two instances for you: Repr, which lets #eval display a Book, and BEq, which defines == field by field. Other commonly derived classes are DecidableEq (equality you can use in proofs as well as programs), Hashable (for hash maps), Ord (for sorting) and Inhabited (a default value). Lesson 5 explains what these classes are; for now, add deriving Repr to anything you want to look at with #eval.
Inductive types and pattern matching
Definition— Inductive type
An inductive type is declared by listing its constructors, the only ways to make a value of the type. Each constructor may take arguments, and those arguments may have the type being defined. Every value of an inductive type was built by exactly one constructor, and pattern matching asks which one, binding names to its arguments.
Alternatives that carry data
inductive Shape where
| circle (radius : Float)
| rectangle (width height : Float)
| triangle (a b c : Float) -- the lengths of the three sides
deriving Repr
namespace Shape
def area : Shape → Float
| circle r => 3.141592653589793 * r * r
| rectangle w h => w * h
| triangle a b c =>
-- Heron's formula
let s := (a + b + c) / 2
Float.sqrt (s * (s - a) * (s - b) * (s - c))
def name (s : Shape) : String :=
match s with
| circle _ => "circle"
| rectangle w h => if w == h then "square" else "rectangle"
| triangle .. => "triangle"
end Shape
def shapes : List Shape := [.circle 1, .rectangle 3 4, .rectangle 2 2, .triangle 3 4 5]
def main : IO Unit := do
for s in shapes do
IO.println s!"{s.name}: area {s.area}"circle: area 3.141593
rectangle: area 12.000000
square: area 4.000000
triangle: area 6.000000A Shape is a circle or a rectangle or a triangle, and each carries exactly the numbers it needs. There is no way to make a circle with a width or a triangle with two sides.
The program shows the two ways to write a function by pattern matching. area is defined by equations: after the type Shape → Float, each line starting with | handles one constructor. name uses an explicit match expression on its parameter, which is the same thing written differently; use whichever reads better. In a pattern, a name such as r binds the constructor's argument, _ matches anything without naming it, and .. stands for all the remaining arguments.
namespace Shape … end Shape puts the definitions inside it under the name Shape, so area is really Shape.area, and dot notation lets us write s.area. Inside the namespace, the constructors can be written without the prefix (circle rather than Shape.circle). Outside, when Lean already knows the expected type, a leading dot is enough: in shapes, .circle 1 means Shape.circle 1 because the list is declared to hold Shapes.
Enumerations, nested patterns and matching several values
An inductive type whose constructors take no arguments is an enumeration. This program models a robot on a grid that receives a list of moves:
inductive Dir where
| north | east | south | west
deriving Repr, BEq
inductive Move where
| forward (steps : Nat)
| turnLeft
| turnRight
structure Robot where
x : Int := 0
y : Int := 0
facing : Dir := .north
deriving Repr
def Dir.right : Dir → Dir
| .north => .east
| .east => .south
| .south => .west
| .west => .north
def Dir.left (d : Dir) : Dir := d.right.right.right
def Robot.step (r : Robot) (m : Move) : Robot :=
match m, r.facing with
| .turnLeft, d => { r with facing := d.left }
| .turnRight, d => { r with facing := d.right }
| .forward n, .north => { r with y := r.y + n }
| .forward n, .south => { r with y := r.y - n }
| .forward n, .east => { r with x := r.x + n }
| .forward n, .west => { r with x := r.x - n }
def route : List Move := [.forward 3, .turnRight, .forward 2, .turnRight, .turnRight, .forward 5]
def main : IO Unit := do
let finish := route.foldl Robot.step {}
IO.println (repr finish)
IO.println s!"Ended at ({finish.x}, {finish.y})"{ x := -3, y := 3, facing := Dir.west }
Ended at (-3, 3)match m, r.facing with matches two values at once, and each pattern line gives a pattern for each, separated by a comma. Lean tries the lines from top to bottom and takes the first that fits. Note how compactly the six cases express the rules; the equivalent nest of ifs would be twice as long and easy to get wrong.
Three smaller points. Turning left is three right turns, which saves writing a second table. In r.y + n, n is a Nat and r.y an Int; Lean inserts the conversion from Nat to Int for you (a coercion, shown as ↑n if you hover over it). And route.foldl Robot.step {} starts from the robot with all default fields, {}, and feeds it each move in turn: foldl is the functional way to run a loop that updates a value, and you will see it constantly.
When you forget a case
Suppose that, in a file called err.lean, Dir.right forgot the west case:
inductive Dir where
| north | east | south | west
def Dir.right : Dir → Dir
| .north => .east
| .east => .south
| .south => .westLean refuses the definition:
err.lean:5:2: error: Missing cases:
westThis is not a warning you can ignore, as it is in some languages: a function in Lean must return a value for every input, so a match that misses a constructor is an error. When you add a constructor to a type in a large program, the compiler lists every function that needs updating. Experienced programmers lean on this deliberately, and avoid catch-all _ patterns on types that are likely to grow, so that the compiler can do that work for them.
Recursive types: lists, trees and numbers
A constructor's arguments may have the type being defined. That is what the word inductive refers to: values are built up step by step from simpler values of the same type. Lean's own library defines lists, optional values and even the natural numbers this way (simplified slightly here; the real definitions also work for types in every universe, a detail lesson 5 mentions):
inductive Nat where
| zero : Nat
| succ (n : Nat) : Nat
inductive List (α : Type) where
| nil : List α
| cons (head : α) (tail : List α) : List α
inductive Option (α : Type) where
| none : Option α
| some (val : α) : Option αA natural number is either zero or the successor of a natural number, so 3 is succ (succ (succ zero)). (The compiler stores Nat as a machine integer or a big number, not as a chain of succs; the definition is what proofs reason about, and the efficient representation is what programs run on.) A list is either empty, [], or an element in front of a list, x :: xs. List α and Option α are parameterised: α is a type, so there are lists of numbers, lists of strings and lists of lists.
Option is how Lean says "there may be no value". Where Java or C would return null or -1, a Lean function returns Option α: some x when there is an answer and none when there is not. Because Option Nat is a different type from Nat, you cannot forget to handle the missing case; the type checker will not let you add 1 to an Option Nat.
Here is a binary search tree, defined from scratch:
/-- A binary search tree of natural numbers. -/
inductive Tree where
| leaf
| node (left : Tree) (key : Nat) (right : Tree)
deriving Repr
namespace Tree
def insert (t : Tree) (k : Nat) : Tree :=
match t with
| leaf => node leaf k leaf
| node l x r =>
if k < x then node (l.insert k) x r
else if x < k then node l x (r.insert k)
else t -- already present
def toList : Tree → List Nat
| leaf => []
| node l x r => l.toList ++ [x] ++ r.toList
def depth : Tree → Nat
| leaf => 0
| node l _ r => 1 + max l.depth r.depth
def contains (t : Tree) (k : Nat) : Bool :=
match t with
| leaf => false
| node l x r => if k < x then l.contains k else if x < k then r.contains k else true
end Tree
def main : IO Unit := do
let t := [50, 30, 70, 20, 40, 60, 80, 30].foldl Tree.insert .leaf
IO.println t.toList
IO.println s!"depth {t.depth}, has 40: {t.contains 40}, has 45: {t.contains 45}"
let firstEven := t.toList.find? (fun n => n % 20 == 0 && n > 40)
match firstEven with
| some n => IO.println s!"first multiple of 20 above 40: {n}"
| none => IO.println "none found"
if let some n := t.toList.find? (· > 100) then
IO.println s!"found {n}"
else
IO.println "nothing above 100"[20, 30, 40, 50, 60, 70, 80]
depth 3, has 40: true, has 45: false
first multiple of 20 above 40: 60
nothing above 100The functions on Tree call themselves on the subtrees: recursion follows the shape of the data. A leaf has no subtrees, so it is the base case; a node has two, so toList and depth recurse into both and insert and contains into one. Lean accepts these definitions without complaint because each recursive call is on a piece of its argument, which guarantees that the recursion ends. The next lesson is about recursion that is not so obviously finite.
At the end, List.find? returns an Option Nat, and the program handles both cases: once with a full match, once with if let, which matches one pattern and falls back to else otherwise. A question mark at the end of a function name, as in find?, is a Lean convention meaning "returns an Option".
Modelling data the way Lean programmers do
A few habits separate data types that help you from data types that fight you.
Make illegal states unrepresentable. If a value can be in one of several situations, use an inductive type with one constructor per situation, each carrying only the data that situation has. A payment that is either pending, paid (receipt : String) or refunded (reason : String) is better than a structure with a status string and two optional fields, because nothing can then be "paid" without a receipt. Ask of every structure you write: are there combinations of field values that make no sense? If so, an inductive type is probably hiding inside it.
Use structures for data that always comes together, and extend them when one kind of record is a richer version of another:
structure Point where
x : Float
y : Float
structure Station extends Point where
name : StringA Station has the fields x, y and name, and s.toPoint gives back its Point part. This is composition of records, not object-oriented inheritance: there are no virtual methods and no subtyping beyond that projection.
Give long types a short name with abbrev, as in abbrev Grid := List (List Nat). An abbrev is completely transparent: a Grid is a list of lists everywhere. When you want a genuinely separate type, say metres that must never be mixed up with seconds, wrap the value in a one-field structure instead.
Follow the naming conventions. Types and structures are UpperCamelCase (Shape, Robot); functions, fields and constructors are lowerCamelCase (area, onLoan, turnLeft). Functions about a type live in its namespace, so that dot notation finds them. Functions that return an Option end in ?, and functions that can fail with a crash (rare, and lesson 7 explains when they are acceptable) end in !.
Derive what you need, and no more. deriving Repr costs nothing and makes debugging pleasant. Derive BEq, Hashable or Ord when you need to compare, hash or sort values of the type, and think about whether the derived, field-by-field behaviour is really what equality means for your data.
Common misconceptions
Misconception
"{ b with year := 2000 } changes b." It builds a new value; b is unchanged and anything that refers to it still sees the old year. In practice the copy is often free, because Lean updates values in place when nothing else refers to them (lesson 7), but semantically there is never mutation.
Misconception
"A catch-all _ case makes a match safer." It makes the match compile, but it also stops the compiler from telling you when a new constructor needs handling. Use _ for values whose alternatives you genuinely do not care about, and list constructors explicitly when each one deserves a decision.
Misconception
"Structures and inductive types are different kinds of thing." A structure is an inductive type with exactly one constructor, plus conveniences: field names, projections, default values, the with update syntax. You can pattern match on a structure with its constructor, | ⟨title, author, year, onLoan⟩ => …, just as on any other inductive type.
Misconception
"Option is just Lean's name for null." A null can hide in any reference in Java or C; an Option appears only where the type says so, and the type checker makes you deal with none before you can use the value inside. That difference, absence made visible in types, is the point.
Exercises
Use the definitions from the lesson. Work each answer out by hand, then check it with #eval.
1. Structures, inductive types and pattern matching
Warm-upComputationalWith Book, Book.age and achebe defined as in the lesson, what is { achebe with year := 1959 }.age 2026?
2. Structures, inductive types and pattern matching
CoreComputationalUsing the robot program from the lesson, a robot starts at the default position (0, 0) facing north and follows [.turnLeft, .forward 4, .turnLeft, .forward 1]. Where does it end? Answer as (x, y).
3. Structures, inductive types and pattern matching
Warm-upComputationalWhat does Shape.name (.rectangle 5 5) return? (Quotation marks are optional.)
4. Structures, inductive types and pattern matching
CoreComputationalUsing the Tree from the lesson, what is ([10, 20, 30, 40].foldl Tree.insert .leaf).depth?
5. Structures, inductive types and pattern matching
Warm-upComputationalWhat does #eval [3, 8, 1].find? (· > 5) show?
6. Structures, inductive types and pattern matching
CoreHumanYou add a constructor | hexagon (side : Float) to Shape but do not change Shape.area. What happens?
7. Structures, inductive types and pattern matching
CoreComputationalWhich of these are valid definitions of a Book, as declared in the lesson? List their letters.
- A:
{ author := "Jane Austen", title := "Pride and Prejudice", year := 1813 } - B:
⟨"Pride and Prejudice", "Jane Austen", 1813, false⟩ - C:
{ title := "Pride and Prejudice", year := 1813 } - D:
Book.mk "Pride and Prejudice" "Jane Austen" 1813 false - E:
⟨"Jane Austen", "Pride and Prejudice", "1813"⟩
Further reading and resources
- Functional Programming in Lean: structures, datatypes and patterns · David Thrane ChristiansenThe official book's first chapter covers structures, inductive types and pattern matching with more examples.
- Theorem Proving in Lean 4: Inductive TypesHow inductive types are defined in Lean's logic, and why they come with recursion and induction principles.
- The Lean Language ReferenceThe precise rules for structures, inductive types, deriving handlers and pattern matching.