Personal tools

Polymorphism

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Examples)
Line 1: Line 1:
 
[[Category:Glossary]]
 
[[Category:Glossary]]
A value is polymorphic if, depending on the context where it's used, it can take on more than one type.
+
A value is polymorphic if, depending on the context where it's used, it can take on more than one type. Polymorphism is widespread in Haskell and is a key feature of its type system.
   
There are different kinds of polymorphism.
+
Most polymorphism in Haskell falls into one of two broad categories: [[#Parametric polymorphism|''parametric'']] polymorphism and [[#Ad-hoc polymorphism|''ad-hoc'']] polymorphism.
   
#[[Parametric polymorphism]]; mostly found in functional languages
+
=== Parametric polymorphism ===
#[[Ad-hoc polymorphism]] or overloading
 
#[[Inclusion polymorphism]]; mostly found in object oriented languages
 
   
== Examples ==
+
Parametric polymorphism refers to when the type of a value contains type variables (denoted in Haskell by names starting with a lowercase letter in types) with no constraints (e.g. class constraints; see [[#Ad-hoc polymorphism|below]]) on them. Then the value may adopt any type that results from substituting those variables with concrete types.
<haskell>
 
foldr :: (a -> b -> b) -> b -> [a] -> b
 
</haskell>
 
The type of <hask>foldr</hask> involves unrestricted type variables, so it is a parametrically polymorphic [[function]]. When actually used, it may take on any of a variety of types, for example:
 
<haskell>
 
:: (Char -> Int -> Int) -> Int -> String -> Int -- a = Char, b = Int (note String = [Char])
 
:: (String -> String -> String) -> String -> [String] -> String -- a = b = String
 
</haskell>
 
Numeric literals are overloaded (i.e. subject to ad-hoc polymorphism):
 
<haskell>
 
1 :: (Num t) => t
 
</haskell>
 
The difference is that the type variable here is constrained – it must be an instance of <hask>Num</hask>.
 
   
== References ==
+
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.
  +
  +
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 a finite number of types because it, or a value it uses, has been given a separate definition for each of those types. In many languages this is called overloading, and in Haskell it 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.
  +
  +
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.
  +
  +
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.
  +
  +
=== Other kinds of polymorphism ===
  +
  +
There are several more exotic flavours of polymorphism that are implemented in some extensions to Haskell, e.g. [[rank-N polymorphism]] 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 ==
 
*[http://citeseer.nj.nec.com/cardelli85understanding.html On Understanding Types, Data Abstraction, and Polymorphism (1985)], by Luca Cardelli, Peter Wegner in ACM Computing Surveys.
 
*[http://citeseer.nj.nec.com/cardelli85understanding.html On Understanding Types, Data Abstraction, and Polymorphism (1985)], by Luca Cardelli, Peter Wegner in ACM Computing Surveys.
   

Revision as of 21:25, 4 September 2012

A value is polymorphic if, depending on the context where it's used, it can take on more than one type. 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

1 Parametric polymorphism

Parametric polymorphism refers to when the type of a value contains type variables (denoted in Haskell by names starting with a lowercase letter in types) with no constraints (e.g. class constraints; see below) on them. Then the value may adopt any type that results from substituting those variables with concrete types.

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.

2 Ad-hoc polymorphism

Ad-hoc polymorphism refers to when a value is able to adopt any one of a finite number of types because it, or a value it uses, has been given a separate definition for each of those types. In many languages this is called overloading, and in Haskell it 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. 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.

3 Other kinds of polymorphism

There are several more exotic flavours of polymorphism that are implemented in some extensions to Haskell, e.g. rank-N polymorphism 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.

4 Further reading