# Difference between revisions of "Polymorphism"

Benmachine (talk | contribs) (→Other kinds of polymorphism) |
Benmachine (talk | contribs) m |
||

(8 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

[[Category:Glossary]] | [[Category:Glossary]] | ||

− | A value is polymorphic if | + | A value is polymorphic if there is more than one type it can have. Polymorphism is widespread in Haskell and is a key feature of its type system. |

Most polymorphism in Haskell falls into one of two broad categories: [[#Parametric polymorphism|''parametric'']] polymorphism and [[#Ad-hoc polymorphism|''ad-hoc'']] polymorphism. | Most polymorphism in Haskell falls into one of two broad categories: [[#Parametric polymorphism|''parametric'']] polymorphism and [[#Ad-hoc polymorphism|''ad-hoc'']] polymorphism. | ||

Line 6: | Line 6: | ||

=== Parametric polymorphism === | === Parametric polymorphism === | ||

− | Parametric polymorphism refers to when the type of a value contains type variables | + | Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) ''type variables'', so that the value may adopt any type that results from substituting those variables with concrete types. |

+ | |||

+ | In Haskell, this means any type in which a type variable, denoted by a name in a type beginning with a lowercase letter, appears without constraints (i.e. does not appear to the left of a <tt>=></tt>). In Java and some similar languages, generics (roughly speaking) fill this role. | ||

For example, the function <hask>id :: a -> a</hask> contains an unconstrained type variable <hask>a</hask> in its type, and so can be used in a context requiring <hask>Char -> Char</hask> or <hask>Integer -> Integer</hask> or <hask>(Bool -> Maybe Bool) -> (Bool -> Maybe Bool)</hask> or any of a literally infinite list of other possibilities. Likewise, the empty list <hask>[] :: [a]</hask> belongs to every list type, and the polymorphic function <hask>map :: (a -> b) -> [a] -> [b]</hask> may operate on any function type. Note, however, that if a single type variable appears multiple times, it must take the same type everywhere it appears, so e.g. the result type of <hask>id</hask> must be the same as the argument type, and the input and output types of the function given to <hask>map</hask> must match up with the list types. | For example, the function <hask>id :: a -> a</hask> contains an unconstrained type variable <hask>a</hask> in its type, and so can be used in a context requiring <hask>Char -> Char</hask> or <hask>Integer -> Integer</hask> or <hask>(Bool -> Maybe Bool) -> (Bool -> Maybe Bool)</hask> or any of a literally infinite list of other possibilities. Likewise, the empty list <hask>[] :: [a]</hask> belongs to every list type, and the polymorphic function <hask>map :: (a -> b) -> [a] -> [b]</hask> may operate on any function type. Note, however, that if a single type variable appears multiple times, it must take the same type everywhere it appears, so e.g. the result type of <hask>id</hask> must be the same as the argument type, and the input and output types of the function given to <hask>map</hask> must match up with the list types. | ||

Line 14: | Line 16: | ||

=== Ad-hoc polymorphism === | === Ad-hoc polymorphism === | ||

− | Ad-hoc polymorphism refers to when a value is able to adopt any one of | + | Ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types. For example, the <tt>+</tt> operator essentially does something entirely different when applied to floating-point values as compared to when applied to integers – in Python it can even be applied to strings as well. Most languages support at least some ad-hoc polymorphism, but in languages like C it is restricted to only built-in functions and types. Other languages like C++ allow programmers to provide their own overloading, supplying multiple definitions of a single function, to be disambiguated by the types of the arguments. In Haskell, this is achieved via the system of [[type class]]es and class instances. |

Despite the similarity of the name, Haskell's type classes are quite different from the classes of most object-oriented languages. They have more in common with interfaces, in that they specify a series of methods or values by their type signature, to be implemented by an instance declaration. | Despite the similarity of the name, Haskell's type classes are quite different from the classes of most object-oriented languages. They have more in common with interfaces, in that they specify a series of methods or values by their type signature, to be implemented by an instance declaration. | ||

So, for example, if my type can be compared for equality (most types can, but some, particularly function types, cannot) then I can give an instance declaration of the <hask>Eq</hask> class. All I have to do is specify the behaviour of the <hask>==</hask> operator on my type, and I gain the ability to use all sorts of functions defined using that operator, e.g. checking if a value of my type is present in a list, or looking up a corresponding value in a list of pairs. | So, for example, if my type can be compared for equality (most types can, but some, particularly function types, cannot) then I can give an instance declaration of the <hask>Eq</hask> class. All I have to do is specify the behaviour of the <hask>==</hask> operator on my type, and I gain the ability to use all sorts of functions defined using that operator, e.g. checking if a value of my type is present in a list, or looking up a corresponding value in a list of pairs. | ||

+ | |||

+ | Unlike the overloading in some languages, overloading in Haskell is not limited to functions – <tt>minBound</tt> is an example of an overloaded ''value'', so that when used as a <tt>Char</tt> it will have value <tt>'\NUL'</tt> while as an <tt>Int</tt> it might be <tt>-2147483648</tt>. | ||

+ | |||

+ | Haskell even allows class instances to be defined for types which are themselves polymorphic (either ad-hoc or parametrically). So for example, an instance can be defined of <tt>Eq</tt> that says "if <tt>a</tt> has an equality operation, then <tt>[a]</tt> has one". Then, of course, <tt><nowiki>[[a]]</nowiki></tt> will automatically also have an instance, and so complex compound types can have instances built for them out of the instances of their components. | ||

You can recognise the presence of ad-hoc polymorphism by looking for ''constrained'' type variables: that is, variables that appear to the left of <hask>=></hask>, like in <hask>elem :: (Eq a) => a -> [a] -> Bool</hask>. Note that <hask>lookup :: (Eq a) => a -> [(a,b)] -> Maybe b</hask> exhibits both parametric (in <hask>b</hask>) and ad-hoc (in <hask>a</hask>) polymorphism. | You can recognise the presence of ad-hoc polymorphism by looking for ''constrained'' type variables: that is, variables that appear to the left of <hask>=></hask>, like in <hask>elem :: (Eq a) => a -> [a] -> Bool</hask>. Note that <hask>lookup :: (Eq a) => a -> [(a,b)] -> Maybe b</hask> exhibits both parametric (in <hask>b</hask>) and ad-hoc (in <hask>a</hask>) polymorphism. | ||

Line 29: | Line 35: | ||

== Further reading == | == Further reading == | ||

− | *[http:// | + | *[http://lucacardelli.name/Papers/OnUnderstanding.A4.pdf On Understanding Types, Data Abstraction, and Polymorphism (1985)], by Luca Cardelli, Peter Wegner in ACM Computing Surveys. |

+ | |||

+ | *[http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf On Understanding Data Abstraction, Revisited (2009)], by William R. Cook in OOPSLA 2009. | ||

*[http://en.wikipedia.org/wiki/Type_polymorphism Type polymorphism] at Wikipedia | *[http://en.wikipedia.org/wiki/Type_polymorphism Type polymorphism] at Wikipedia |

## Latest revision as of 00:50, 21 January 2015

A value is polymorphic if there is more than one type it can have. Polymorphism is widespread in Haskell and is a key feature of its type system.

Most polymorphism in Haskell falls into one of two broad categories: *parametric* polymorphism and *ad-hoc* polymorphism.

## Contents

### Parametric polymorphism

Parametric polymorphism refers to when the type of a value contains one or more (unconstrained) *type variables*, so that the value may adopt any type that results from substituting those variables with concrete types.

In Haskell, this means any type in which a type variable, denoted by a name in a type beginning with a lowercase letter, appears without constraints (i.e. does not appear to the left of a `=>`). In Java and some similar languages, generics (roughly speaking) fill this role.

For example, the function `id :: a -> a`

contains an unconstrained type variable `a`

in its type, and so can be used in a context requiring `Char -> Char`

or `Integer -> Integer`

or `(Bool -> Maybe Bool) -> (Bool -> Maybe Bool)`

or any of a literally infinite list of other possibilities. Likewise, the empty list `[] :: [a]`

belongs to every list type, and the polymorphic function `map :: (a -> b) -> [a] -> [b]`

may operate on any function type. Note, however, that if a single type variable appears multiple times, it must take the same type everywhere it appears, so e.g. the result type of `id`

must be the same as the argument type, and the input and output types of the function given to `map`

must match up with the list types.

Since a parametrically polymorphic value does not "know" anything about the unconstrained type variables, it must behave the same regardless of its type. This is a somewhat limiting but extremely useful property known as parametricity.

### Ad-hoc polymorphism

Ad-hoc polymorphism refers to when a value is able to adopt any one of several types because it, or a value it uses, has been given a separate definition for each of those types. For example, the `+` operator essentially does something entirely different when applied to floating-point values as compared to when applied to integers – in Python it can even be applied to strings as well. Most languages support at least some ad-hoc polymorphism, but in languages like C it is restricted to only built-in functions and types. Other languages like C++ allow programmers to provide their own overloading, supplying multiple definitions of a single function, to be disambiguated by the types of the arguments. In Haskell, this is achieved via the system of type classes and class instances.

Despite the similarity of the name, Haskell's type classes are quite different from the classes of most object-oriented languages. They have more in common with interfaces, in that they specify a series of methods or values by their type signature, to be implemented by an instance declaration.

So, for example, if my type can be compared for equality (most types can, but some, particularly function types, cannot) then I can give an instance declaration of the `Eq`

class. All I have to do is specify the behaviour of the `==`

operator on my type, and I gain the ability to use all sorts of functions defined using that operator, e.g. checking if a value of my type is present in a list, or looking up a corresponding value in a list of pairs.

Unlike the overloading in some languages, overloading in Haskell is not limited to functions – `minBound` is an example of an overloaded *value*, so that when used as a `Char` it will have value `'\NUL'` while as an `Int` it might be `-2147483648`.

Haskell even allows class instances to be defined for types which are themselves polymorphic (either ad-hoc or parametrically). So for example, an instance can be defined of `Eq` that says "if `a` has an equality operation, then `[a]` has one". Then, of course, `[[a]]` will automatically also have an instance, and so complex compound types can have instances built for them out of the instances of their components.

You can recognise the presence of ad-hoc polymorphism by looking for *constrained* type variables: that is, variables that appear to the left of `=>`

, like in `elem :: (Eq a) => a -> [a] -> Bool`

. Note that `lookup :: (Eq a) => a -> [(a,b)] -> Maybe b`

exhibits both parametric (in `b`

) and ad-hoc (in `a`

) polymorphism.

### Other kinds of polymorphism

There are several more exotic flavours of polymorphism that are implemented in some extensions to Haskell, e.g. rank-N types and impredicative types.

There are some kinds of polymorphism that Haskell doesn't support, or at least not natively, e.g. inclusion polymorphism and subtyping, common in OO languages, where values of one type can act as values of another type.

## Further reading

- On Understanding Types, Data Abstraction, and Polymorphism (1985), by Luca Cardelli, Peter Wegner in ACM Computing Surveys.

- On Understanding Data Abstraction, Revisited (2009), by William R. Cook in OOPSLA 2009.

- Type polymorphism at Wikipedia