Course contentsShow
← Computer Science
Lesson 2010 of 2,87245. Type Systems and SemanticsFree lesson

Type Variables and Unification

How type inference uses type variables and unification to solve type equations.

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:

  1. Generate constraints: When analyzing f x, if f has type α → β and x has type Int, you get the constraint: α = Int
  2. Unify types: The unification algorithm matches these patterns together
  3. Substitute: Once α = Int is determined, replace α with Int everywhere

Example Flow

let id = λx. x
  • Initially: id :: α → β, and x :: α returns x :: α
  • 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.