polymertype

Polymertype is a concept in programming language theory describing a type that can stand for more than one concrete type. Polymorphic types enable generic programming by allowing definitions to operate on values of different types without being rewritten for each type.

There are several forms of polymorphism. Parametric polymorphism uses type variables to describe functions or data structures that are uniformly applicable to any type, as in the classic identity function whose type can be written as forall a. a -> a. Ad-hoc polymorphism refers to overloading, where the same name can have different implementations depending on the type of its arguments. Subtype polymorphism arises in object-oriented settings when a value of a subclass type can be treated as a value of its superclass type. In formal type systems, a polymorphic type often takes the form of a polytype, representing types that can be instantiated with multiple concrete types.

Formal representation often uses universal quantification, as in System F, where a polytype may be written as forall a. a -> a. In practical languages, type systems implement let-polymorphism (as in Hindley-Milner) that generalizes type variables at let-bindings, subject to restrictions such as the value restriction in some call-by-value languages. Some languages also support impredicative polymorphism, which allows quantification over polymorphic types but increases complexity and is typically avoided in mainstream languages.

Examples in modern languages include parametric polymorphism in Haskell and ML through generic functions and data types, Java and C# generics, and TypeScript generics. Polymorphic types enhance code reuse and abstraction, enabling data structures like lists, trees, and maps to be written once and used with many types, while also introducing considerations around type safety, compilation strategies, and potential runtime costs.

See also: polymorphism, type system, parametric polymorphism, ad-hoc polymorphism, Hindley-Milner type system, System F.