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

Hindley-Milner Type System

Introduction to the foundational type inference algorithm used in ML and Haskell.

Hindley-Milner Type System

What You'll Learn

You'll discover the elegant algorithm that lets languages like ML and Haskell automatically figure out types without requiring you to write them explicitly.

The Core Idea

The Hindley-Milner type system (often called HM) is a powerful type inference algorithm that can determine the most general type for any expression in your program automatically. It's the secret sauce behind languages like ML, Haskell, and OCaml that let you write code without type annotations yet still get strong compile-time type safety.

Think of it like a detective solving a puzzle: given clues from how you use a variable (applying it as a function, adding it to a number, etc.), HM deduces what type it must be.

How It Works

HM uses three key techniques working together:

  1. Type variables: It starts by assigning unknown type variables (like α, β) to expressions whose types aren't immediately obvious.

  2. Constraint generation: As it analyzes your code, it builds equations based on how values are used. If you add two things, they must both be numbers. If you pass something to a function, the types must match.

  3. Unification: It solves these equations to find the most general type that satisfies all constraints. If a function works for any type, it stays polymorphic.

For example, a function that returns its input unchanged would get type α → α (any type to that same type), not just Int → Int.

Why It Matters

HM gives you the best of both worlds: the brevity of dynamic typing with the safety of static typing. You write clean code without clutter, and the compiler catches type errors before runtime.

Key Takeaway: The Hindley-Milner type system automatically infers the most general types for your programs through constraint generation and unification, enabling powerful static type checking without explicit annotations.