Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Parametricity and free theorems

Parametric polymorphism constrains implementations because a function that works for every type cannot secretly depend on operations unavailable for an arbitrary type. Parametricity turns that uniformity into formal reasoning principles.

Consider a total pure function with type

$$f:\forall A.\ A\to A.$$

For an arbitrary $A$, the function receives one $A$ and has no type-specific operation that can manufacture a different $A$. Apart from nontermination or effects excluded by the model, the only possible result is therefore its input. The type strongly constrains the implementation.

A richer example is

$$f:\forall A.\forall B.\ (A\to B)\to\operatorname{List}(A)\to\operatorname{List}(B).$$

Uniformity implies that $f$ cannot inspect the representation of $A$ or $B$; it can only rearrange structure and use the supplied function to obtain $B$ values.

Such consequences derived largely from a polymorphic type are called free theorems. Formally, relational parametricity states that polymorphic functions preserve appropriate relations between different type instantiations.

Parametricity is valuable because types become more than compatibility checks: sufficiently general polymorphic types can reveal semantic properties of programs before their implementations are inspected.