Parametric polymorphism
In programming languages and type theory, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In programming languages and type theory, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed. Parametrically polymorphic functions and data types are sometimes called generic functions and generic datatypes, respectively, and they form the basis of generic programming.
Parametric polymorphism may be contrasted with ad hoc polymorphism. Parametrically polymorphic definitions are uniform: they behave identically regardless of the type they are instantiated at. In contrast, ad hoc polymorphic definitions are given a distinct definition for each type.
Thus, ad hoc polymorphism can generally only support a limited number of such distinct types, since a separate implementation has to be provided for each type. The usual theoretical device for studying parametric polymorphism is system F, which extends simply typed lambda calculus with quantification over types.
It is possible to write functions that do not depend on the types of their arguments. For example, the identity function \mathsf{id}(x) = x simply returns its argument unmodified. This naturally gives rise to a family of potential types, such as \mathsf{Int} \to \mathsf{Int} , \mathsf{Bool} \to \mathsf{Bool} , \mathsf{String} \to \mathsf{String} , and so on.
Parametric polymorphism allows \mathsf{id} to be given a single, most general type by introducing a universally quantified type variable: \mathsf{id} : \forall \alpha. \alpha \to \alpha The polymorphic definition can then be instantiated by substituting any concrete type for \alpha , yielding the full family of potential types. The identity function is a particularly extreme example, but many other functions also benefit from parametric polymorphism.
For example, an \mathsf{append} function that concatenates two lists does not inspect the elements of the list, only the list structure itself. Therefore, \mathsf{append} can be given a similar family of types, such as [ \mathsf{Int}] \times [\mathsf{Int}] \to [\mathsf{Int}] , [ \mathsf{Bool}] \times [\mathsf{Bool}] \to [\mathsf{Bool}] , and so on, where [T] denotes a list of elements of type T . The most general type is therefore \mathsf{append} : \forall \alpha.
[\alpha] \times [\alpha] \to [\alpha] which can be instantiated to any type in the family. Parametrically polymorphic functions like \mathsf{id} and \mathsf{append} are said to be parameterized over an arbitrary type \alpha . Both \mathsf{id} and \mathsf{append} are parameterized over a single type, but functions may be parameterized over arbitrarily many types.
For example, the \mathsf{fst} and \mathsf{snd} functions that return the first and second elements of a pair, respectively, can be given the following types: \begin{aligned} \mathsf{fst} & : \forall \alpha. \forall \beta. \alpha \times \beta \to \alpha \\ \mathsf{snd} & : \forall \alpha. \forall \beta. \alpha \times \beta \to \beta \end{aligned} In the expression \mathsf{fst}((3, \mathsf{true})) , \alpha is instantiated to \mathsf{Int} and \beta is instantiated to \mathsf{Bool} in the call to \mathsf{fst} , so the type of the overall expression is \mathsf{Int} . The syntax used to introduce parametric polymorphism varies significantly between programming languages.
For example, in some programming languages, such as Haskell, the \forall \alpha quantifier is implicit and may be omitted. Other languages require types to be instantiated explicitly at a parametrically polymorphic function's call sites, either at all sites or alternatively at least sufficient to allow type inference to determine the rest.
In 1985, Luca Cardelli and Peter Wegner recognized the advantages of allowing bounds on the type parameters. Many operations require some knowledge of the data types, but can otherwise work parametrically. For example, to check whether an item is included in a list, we need to compare the items for equality.
In Standard ML, type parameters of the form a are restricted so that the equality operation is available, thus the function would have the type a × a list → bool and a can only be a type with defined equality. In Haskell, bounding is achieved by requiring types to belong to a type class; thus the same function has the type \mathrm{Eq} \, \alpha \, \Rightarrow \alpha \, \rightarrow \left[\alpha \right] \rightarrow \mathrm{Bool} in Haskell.
In most object-oriented programming languages that support parametric polymorphism, parameters can be constrained to be subtypes of a given type (see the articles Subtype polymorphism and Generic programming).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378822151 under CC BY-SA 4.0; modifications have been made.