One function, many types
In lesson 4 you wrote length : List α → Nat, and it worked on lists of numbers and lists of strings alike. That is parametric polymorphism: the function does the same thing whatever α is, because it never looks inside the elements.
Many useful functions do need to look inside. Summing a list needs addition; finding the largest element needs a comparison; printing needs a way to turn each element into text. Addition on Nat and addition on Float are different operations, and there is no addition at all on Bool. What we want is to write total once, for "any type that has an addition and a zero", and have the compiler pick the right addition at each use. Lean's answer, borrowed from Haskell and much extended, is type classes: a class names an interface (Add, Ord, ToString), an instance implements it for one type, and a function can require instances in its signature.
The second half of this lesson goes further. In Lean, a type can mention a value: Vector Int 3 is the type of integer vectors of length exactly 3, and Fin 8 is the type of natural numbers below 8. These are dependent types, and they let the compiler check facts that other languages check at run time, or not at all: that two vectors you are adding have the same length, that an index is in bounds, that a divisor is not zero. Dependent types are what make Lean a proof assistant, and they are equally useful in everyday code.
Implicit arguments and polymorphism
Definition— Implicit argument
A parameter in braces, {α : Type}, is implicit: callers do not write it, and Lean works it out from the other arguments. A parameter in square brackets, [Add α], is instance-implicit: callers do not write it either, and Lean finds it by searching the instances it knows. Writing @f makes every argument of f explicit, which is occasionally needed and often useful with #check.
def swap {α β : Type} (p : α × β) : β × α := (p.2, p.1)
def firstOr {α : Type} (xs : List α) (fallback : α) : α :=
match xs with
| [] => fallback
| x :: _ => x
structure Pair (α : Type) where
first : α
second : α
deriving Repr
def Pair.map {α β : Type} (f : α → β) (p : Pair α) : Pair β :=
⟨f p.first, f p.second⟩
#check @swap
#eval swap (1, "one")
#eval firstOr ["Accra", "Lima"] "nowhere"
#eval firstOr ([] : List String) "nowhere"
#eval (Pair.mk 3 4).map (· * 10)
#eval (Pair.mk "Seoul" "Quito").map String.length
#check Pair
#check Nat
#check Type@swap : {α β : Type} → α × β → β × α
("one", 1)
"Accra"
"nowhere"
{ first := 30, second := 40 }
{ first := 5, second := 5 }
Pair (α : Type) : Type
Nat : Type
Type : Type 1swap takes two types, α and β, and then a pair. The types come first because the type of the pair depends on them. When you call swap (1, "one"), Lean sees a Nat × String, solves α := Nat and β := String, and fills them in. firstOr ([] : List String) "nowhere" needs the ascription because an empty list on its own says nothing about its element type.
Pair is a parameterised structure: Pair Nat and Pair String are different types, built from the same definition. #check Pair shows that Pair is itself a function, from a type to a type.
The last two lines touch on something that is usually invisible. Nat is a value of type Type; Type is a value of type Type 1; and so on up a ladder of universes. The ladder exists to avoid a paradox (a type of all types, including itself, makes the logic inconsistent, much as Russell's paradox did for naive set theory). In everyday programming you write Type and never think about it; library code is written for every universe at once, which is why you will see Type u and Sort u in library signatures. Propositions, which lesson 8 is about, live in a special universe of their own, Prop.
In lessons 3 and 4 some definitions used α without declaring it. Lean then adds {α : Type}, or the universe-polymorphic {α : Type u}, for you; this is called auto-bound implicits. It is convenient in small files, but many projects, Mathlib among them, turn it off so that a misspelt name is reported as an error rather than silently becoming a new type variable.
Type classes and instances
structure Vec2 where
x : Float
y : Float
instance : Add Vec2 where
add a b := ⟨a.x + b.x, a.y + b.y⟩
instance : HMul Float Vec2 Vec2 where
hMul k v := ⟨k * v.x, k * v.y⟩
instance : OfNat Vec2 0 where
ofNat := ⟨0, 0⟩
instance : ToString Vec2 where
toString v := s!"({v.x}, {v.y})"
/-- Works for any type with addition and a zero: Nat, Int, Float, Vec2, ... -/
def total {α : Type} [Add α] [OfNat α 0] (xs : List α) : α :=
xs.foldl (· + ·) 0
class Describe (α : Type) where
describe : α → String
plural : String := "things"
instance : Describe Vec2 where
describe v := s!"a vector to {v}"
plural := "vectors"
instance : Describe Nat where
describe n := if n % 2 == 0 then s!"the even number {n}" else s!"the odd number {n}"
plural := "numbers"
instance : Describe Bool where
describe b := if b then "yes" else "no"
def describeAll {α : Type} [Describe α] (xs : List α) : String :=
s!"{xs.length} {Describe.plural α}: " ++ ", ".intercalate (xs.map Describe.describe)
def main : IO Unit := do
let moves : List Vec2 := [⟨1, 2⟩, ⟨3, -1⟩, 2.0 * Vec2.mk 0.5 0.5]
IO.println (total moves)
IO.println (total [1, 2, 3, 4])
IO.println (total [0.5, 0.25])
IO.println (describeAll moves)
IO.println (describeAll [7, 10])
IO.println (describeAll [true, false])(5.000000, 2.000000)
10
0.750000
3 vectors: a vector to (1.000000, 2.000000), a vector to (3.000000, -1.000000), a vector to (1.000000, 1.000000)
2 numbers: the odd number 7, the even number 10
2 things: yes, noThe first four instances teach Vec2 to behave like a number.
Add Vec2defines+. In Lean,a + bis notation forHAdd.hAdd a b, and anAdd αinstance provides the common case where both sides and the result have the same type.HMul Float Vec2 Vec2definesk * vfor aFloattimes aVec2, giving aVec2. TheHstands for heterogeneous: the operands may have different types. This is how Lean allows scaling a vector by a number without any special support in the language.OfNat Vec2 0says what the numeral0means as aVec2. This is the class that the error in lesson 1, "failed to synthesizeOfNat String 42", was about: every numeral in Lean is resolved throughOfNat, so your own types can have numerals too.ToString Vec2letsIO.printlnand string interpolation print a vector.
total then works for every type that has Add and OfNat … 0 instances, our Vec2 included. At each call, Lean looks at the element type, finds the instances, and passes them to total as hidden arguments. No instance, no call: total [true, false] is a compile-time error, because Lean finds no Add Bool.
Describe is a class of our own. A class declaration looks like a structure, with fields that instances must provide; plural has a default, which the Bool instance does not override, hence "2 things". Describe.plural α names the type explicitly because plural takes no argument from which Lean could infer it. In everyday Lean code you mostly use the standard classes and write instances of them for your types; defining a new class is appropriate when you have a genuinely new interface that several types will implement.
Deriving the standard classes
For many classes, Lean can write the instance for you. A derived Ord on a structure compares field by field, which for software versions is exactly right:
structure Version where
major : Nat
minor : Nat
patch : Nat
deriving Repr, BEq, Ord
instance : ToString Version where
toString v := s!"{v.major}.{v.minor}.{v.patch}"
/-- The largest element of a list, for any type with an ordering. -/
def largest {α : Type} [Ord α] : List α → Option α
| [] => none
| x :: xs => some (xs.foldl (fun best y => if compare y best == .gt then y else best) x)
def releases : List Version := [⟨2, 9, 1⟩, ⟨2, 12, 0⟩, ⟨2, 10, 3⟩, ⟨1, 40, 7⟩]
#eval compare (Version.mk 2 9 1) (Version.mk 2 10 3)
#eval (largest releases).map toString
#eval largest ["kiwi", "mango", "apple"]
#eval largest ([] : List Nat)
#eval (releases.mergeSort (fun a b => compare a b != .gt)).map toStringOrdering.lt
some "2.12.0"
some "mango"
none
["1.40.7", "2.9.1", "2.10.3", "2.12.0"]compare a b returns an Ordering: .lt, .eq or .gt. Because the fields are numbers, 2.9.1 comes before 2.10.3, which string comparison would get wrong. largest works for versions and strings alike, and returns none for an empty list rather than crashing.
Dependent types in everyday code
In most languages, types and values live in separate worlds. In Lean, a type can be computed from a value, and a function's result type can depend on its argument. Here is what that buys a programmer:
/-- The dot product of two vectors of the same length `n`. -/
def dot {n : Nat} (a b : Vector Int n) : Int :=
(a.zipWith (· * ·) b).foldl (· + ·) 0
def u : Vector Int 3 := #v[1, 2, 3]
def w : Vector Int 3 := #v[4, -5, 6]
#check u
#eval dot u w
#eval u[2]
/-- A position on an 8 × 8 board: each coordinate is a `Fin 8`, a number below 8. -/
structure Square where
file : Fin 8
rank : Fin 8
deriving Repr
def Square.name (s : Square) : String :=
s!"{"abcdefgh".toList[s.file]!}{s.rank.val + 1}"
#eval (Square.mk 4 3).name
#eval ((7 : Fin 8) + 3)
/-- Indexing with a proof: the caller must show `i < a.size`. -/
def middle (a : Array String) (h : 0 < a.size) : String :=
a[a.size / 2]'(by omega)
#eval middle #["Oslo", "Cairo", "Dhaka"] (by decide)
/-- A natural number together with a proof that it is positive. -/
def PosNat := { n : Nat // 0 < n }
def share (total : Nat) (people : PosNat) : Nat := total / people.val
#eval share 100 ⟨7, by decide⟩
/-- The type of the result depends on the value of the argument. -/
def Setting (numeric : Bool) : Type := if numeric then Nat else String
def defaultSetting : (numeric : Bool) → Setting numeric
| true => (8080 : Nat)
| false => "localhost"
#eval (defaultSetting true : Nat)
#eval (defaultSetting false : String)u : Vector Int 3
12
3
"e4"
2
"Cairo"
14
8080
"localhost"Take it piece by piece.
Vector α n is an array whose length n is part of its type. (It is a structure holding an Array and a proof that the array's size is n.) dot demands two vectors of the same n, so calling it with vectors of different lengths is not a run-time error but a type error. Here are two mistakes, at lines 6 and 7 of a file lengths.lean that begins with the definitions of dot and u:
#eval dot u #v[(1 : Int), 2]
#eval u[3]lengths.lean:6:12: error: Application type mismatch: The argument
#v[1, 2]
has type
Vector Int 2
but is expected to have type
Vector Int 3
in the application
dot u #v[1, 2]
lengths.lean:7:6: error: failed to prove index is valid, possible solutions:
- Use `have`-expressions to prove the index is valid
- Use `a[i]!` notation instead, runtime check is performed, and 'Panic' error message is produced if index is not valid
- Use `a[i]?` notation instead, result is an `Option` type
- Use `a[i]'h` notation instead, where `h` is a proof that index is valid
⊢ 3 < 3The second error is the other half of the idea. Indexing a[i] in Lean requires a proof that i is in bounds. For a Vector and a literal index, Lean proves it automatically (u[2] above needed 2 < 3); for u[3] the goal 3 < 3 is false, and Lean says so. The message lists your choices, which are worth memorising: a[i]! checks at run time and panics (prints an error and returns a default value) if i is out of range; a[i]? returns an Option; and a[i]'h uses a proof h that you supply. In middle, the caller provides a proof h that the array is non-empty, and by omega turns it into a proof that a.size / 2 < a.size.
Fin n is the type of natural numbers below n: a number paired with a proof that it is less than n. A chess square's coordinates are Fin 8s, so an off-board square cannot even be written. Arithmetic on Fin n wraps around modulo n, which is why 7 + 3 is 2. Wherever a Nat is expected, a Fin n is converted automatically to its value.
Subtypes, written { x : T // P x }, pair a value with a proof of a property: PosNat is the type of positive naturals, and share can divide without fear because its divisor carries a proof that it is not zero. The anonymous constructor ⟨7, by decide⟩ supplies the value and the proof; by decide proves 0 < 7 by computation.
defaultSetting has a result type that depends on its argument: Setting true reduces to Nat, and Setting false to String. This is the feature that gives "dependent types" their name. You will not write functions like this every day, but you use the idea constantly: the type of Vector.zipWith depends on the length n, and the type of a[i]'h depends on the proof h.
How instances are found, and how professionals use them
When Lean meets [Add α] with α := Vec2, it runs instance resolution: a search through all instances in scope for one whose type matches Add Vec2. Instances can themselves require instances (an Ord (α × β) instance needs Ord α and Ord β), so the search can chain several steps, and Lean caches what it finds. If the search fails you get the "failed to synthesize" error you have already seen; set_option trace.Meta.synthInstance true shows the whole search when you need to debug one. Once found, an instance is just a structure of functions passed as a hidden argument, and the compiler usually specialises generic code for the instances it is called with, so total on Nats runs as fast as a hand-written Nat sum.
Some practical guidance:
- Prefer standard classes. If your type has an addition, give it
Add, not a method calledplus; then+,total,List.sumand every other generic function work with it for free. - One instance per type and class. Lean allows several, picking by priority and recency, but code that depends on which of two competing instances wins is fragile. If you need two orderings of the same type, pass the comparison as an ordinary function argument, as
mergeSortdoes. - Use dependent types where they pay.
Fin nfor indices,Vectorwhen lengths really are fixed, subtypes for invariants that many functions rely on. Do not encode every property in types: the proofs have to be written somewhere, and the!and?forms are perfectly respectable for indices you have just checked. Experienced Lean programmers move a property into a type when that saves more proof work than it costs, and lessons 9 and 10 show the other route, proving properties after the fact.
Common misconceptions
Misconception
"A type class is like a class in Java or Python." It is closer to a Java interface or a Rust trait, and differs from both: an instance is found by type at compile time, not by looking at an object at run time, and instances can be written for types you did not define, such as Describe Bool above. Classes hold no state and there is no inheritance of fields.
Misconception
"Dependent types mean I have to prove everything." You choose. a[i]! and a[i]? need no proof; Vector, Fin and subtypes are tools for the places where a guarantee is worth a little proof effort, and that effort is often a single by omega or by decide.
Misconception
"Fin 8 arithmetic will stop at 7." It wraps around: (7 : Fin 8) + 3 = 2. If you want saturating or checked arithmetic, convert to Nat and handle the boundary yourself.
Misconception
"Derived instances always do the right thing." They do the field-by-field thing. A derived BEq on a structure with a floating-point field inherits the quirks of float equality, and a derived Ord compares fields in declaration order, so declaring patch before major would sort versions wrongly. Read what you derive.
Exercises
Use the definitions from the lesson, and check your answers in the editor.
1. Polymorphism, type classes and dependent types
Warm-upComputationalWith swap from the lesson, what does #eval swap (swap (1, "one")) show?
2. Polymorphism, type classes and dependent types
Warm-upHumanIn def total {α : Type} [Add α] [OfNat α 0] (xs : List α) : α, what does [Add α] mean?
3. Polymorphism, type classes and dependent types
CoreComputationalWith the Describe class and describeAll from the lesson, what does #eval describeAll [3] show? (Quotation marks are optional.)
4. Polymorphism, type classes and dependent types
CoreComputationalWhat is the value of (5 : Fin 6) + 4?
5. Polymorphism, type classes and dependent types
Warm-upComputationalWith dot from the lesson, what is dot #v[2, 0, 1] #v[3, 5, -4]?
6. Polymorphism, type classes and dependent types
CoreComputationalInside def f (a : Array Nat) : … :=, with no other hypotheses, which of these expressions does Lean accept? List their letters.
- A:
a[0]! - B:
a[0]? - C:
a[0] - D:
if h : 0 < a.size then a[0] else 0 - E:
a.getD 0 0
7. Polymorphism, type classes and dependent types
CoreHumanGiven v : Vector Int 3 and t : Vector Int 4, what happens with dot v t?
Further reading and resources
- Functional Programming in Lean: Type Classes · David Thrane ChristiansenThe official book's chapter on type classes and its later chapters on dependent types for programmers.
- Theorem Proving in Lean 4: Dependent Type Theory and Type ClassesUniverses, dependent function types, implicit arguments and instance resolution, from the logical side.
- How to make ad-hoc polymorphism less ad hoc · Philip Wadler and Stephen Blott · 1989The paper that introduced type classes, for Haskell; Lean's are a descendant.