Type Variables and Unification
You'll learn how type inference solves the puzzle of unknown types by using placeholders and matching patterns.
The Core Idea
When a type system infers types automatically (like in Hindley-Milner), it doesn't immediately know what type every expression has. Instead, it uses type variables as placeholders (often written as α, β, or 'a, 'b) to represent "unknown types we'll figure out later."
Unification is the algorithm that solves these puzzles. It takes two types (which may contain type variables) and tries to find a substitution—a mapping from type variables to concrete types—that makes them equal.
How It Works
Think of unification like solving algebra equations, but for types instead of numbers:
- Generate constraints: When analyzing
f x, iffhas typeα → βandxhas typeInt, you get the constraint:α = Int - Unify types: The unification algorithm matches these patterns together
- Substitute: Once
α = Intis determined, replaceαwithInteverywhere
Example Flow
let id = λx. x
- Initially:
id :: α → β, andx :: αreturnsx :: α - Constraint: return type
βmust equalα - Unification discovers:
β = α - Final type:
id :: α → α(polymorphic identity function)
When multiple constraints exist, unification processes them systematically, building up a complete substitution that satisfies all equations simultaneously.
Key Takeaway: Type variables act as placeholders for unknown types, and unification is the pattern-matching algorithm that solves type equations by finding substitutions that make different type expressions equal.