Parametricity

Parametricity is a foundational principle in type theory and functional programming that describes how polymorphic functions behave uniformly across all possible type instantiations. When a function is parametric with respect to a type variable, it cannot inspect the concrete form of that type; instead, it must operate in a way that is agnostic to the type’s representation. This uniformity yields strong guarantees about program behavior, data abstraction, and modularity.

Historically, parametricity was formalized by John C. Reynolds in his 1983 work on types, abstraction, and polymorphism. The central result, known as the abstraction theorem, provides a relational interpretation of polymorphic terms: related inputs yield related outputs for every instantiation of the type variable. Peter Wadler popularized the corollary known as “theorems for free,” showing that a polymorphic type can entail concrete properties about implementations even without examining their code.

Consequences of parametricity include representation independence, where modules can expose abstract types without revealing implementations, and a variety of free-theorem results that constrain what polymorphic functions can do. In practice, languages like Haskell and ML exhibit parametricity for pure polymorphic types, enabling reasoning about program equivalence and data abstractions.

Limitations arise when language features weaken or defeat uniformity. Side effects, subtyping, or advanced features such as generalized algebraic data types, type families, or runtime type information can complicate or invalidate naive parametricity. Consequently, parametricity is often discussed in its restricted, well-typed, and pure form, and its exact statements depend on the language’s theory and features.

See also: abstract data types, free theorems, relational interpretation.