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.