Parametric polymorphism is a type system feature that allows functions not to require any specific type if that type is irrelevant.
There’s definitely a class of use cases that require knowing the type or interface of values and there are only two options there: code duplication or some form of ad hoc polymorphism (generics, interfaces, ML functors…). However, there’re also lots of use cases where logic for different types is exactly the same.
For example, most collections (lists, trees etc.) don’t care about the values they contain.
Consider this function for calculating the length of a linked list (pseudocode):
function length list =
case list of
| [] → 0
| (head : tail) → 1 + (length tail)
The head variable—actual item—is not used by that function at all and could be omitted. If the language knows that and can express a “list of anything” type, both length [1, 2, 3] and length ["foo", "bar", "baz"] will type check. The type of such function would be like length : α list→int where α is a type variable that can be substituted for anything.
The cost of this kind of polymorphism is always zero, both at compile time and at execution time, so there are no possible reasons to force a naturally polymorphic function to a concrete type.
The cost of this kind of polymorphism is always zero
Depending on the implementation, the compiler may have to do monomorphization, which can take a lot more time (see C++ template compile times). That would also expand the size of the final binary, which could result in more L1 cache misses (depending on the usage of the function). Everything has a cost!
One reason I like parametric polymorphism so much is that it needs neither effort to use it nor guidelines for using it. :)
Everything in programming gets guidelines eventually…
Parametric polymorphism is a type system feature that allows functions not to require any specific type if that type is irrelevant.
There’s definitely a class of use cases that require knowing the type or interface of values and there are only two options there: code duplication or some form of ad hoc polymorphism (generics, interfaces, ML functors…). However, there’re also lots of use cases where logic for different types is exactly the same.
For example, most collections (lists, trees etc.) don’t care about the values they contain.
Consider this function for calculating the length of a linked list (pseudocode):
The
headvariable—actual item—is not used by that function at all and could be omitted. If the language knows that and can express a “list of anything” type, bothlength [1, 2, 3]andlength ["foo", "bar", "baz"]will type check. The type of such function would be likelength : α list→intwhereαis a type variable that can be substituted for anything.The cost of this kind of polymorphism is always zero, both at compile time and at execution time, so there are no possible reasons to force a naturally polymorphic function to a concrete type.
Depending on the implementation, the compiler may have to do monomorphization, which can take a lot more time (see C++ template compile times). That would also expand the size of the final binary, which could result in more L1 cache misses (depending on the usage of the function). Everything has a cost!
The cost of monomorphization is identical to the cost of having a separate implementation for each type — since that’s what it is.