Skip to main content

Polymorphism

Introduction

Some functions act on elements of different types, independently of the precise shape of the elements. This is known as polymorphism. The topic is introduced in the video "Polymorphism - Introduction" on Canvas.

Example: the type family of lists

Let's look at the datatype of lists. We have seen in Section 3.3 of our textbook that lists can be filled with elements of different types:

Prelude> :t ['a', 'b', 'c']   -- a list of characters
['a', 'b', 'c'] :: [Char]
Prelude> :t [False, True, True, True] -- a list of Booleans
[False, True, True, True] :: [Bool]
Prelude> :t ["foo", "bar"] -- a list of lists of characters, aka, a list of strings
["foo", "bar"] :: [[Char]]

For any type a, we can form the type [a]. Its elements are lists of elements of type a.

How to build lists

There are two ways of creating a list:

  1. The empty list is a list, [].
  2. To a given list xs we can prepend an element x, written x:xs.

The empty list

Firstly, for any type a, there is the empty list of elements of a:

Prelude> :t []
[] :: [a]

Here, a in [] :: [a] is a type variable, which can be instantiated with any type. For instance, a can be set to be Integer, the type of integer numbers in GHC:

Prelude> :t [] :: [Integer]
[] :: [Integer] :: [Integer]

In this example, we did not use type inference, but instead type checking: we suggest to ghci that [] should have type [Integer], and ask ghci to confirm, which it does. Similarly, ghci is happy to confirm that [] has type [Char]:

Prelude> :t [] :: [Char]
[] :: [Char] :: [Char]

Or:

Prelude> :t [] :: [[Char]]
[] :: [[Char]] :: [[Char]]

Or, for that matter,

Prelude> :t [] :: [[[[[[[Char]]]]]]]
[] :: [[[[[[[Char]]]]]]] :: [[[[[[[Char]]]]]]]

Exercise

For each of these examples, what is the type that the variable a is instantiated with?


Explanation: Watch the video "Polymorphism: empty list []" on Canvas.


Adding an element to a list

There is also a way to build a new list from a smaller one, by adding a new element at the beginning:

Prelude> :t (:)
(:) :: a -> [a] -> [a]

The operator : is an infix operator; that means that it is used between its two arguments (similar to the symbol "+" for addition):

Prelude> :t False:[True, False]
False:[True, False] :: [Bool]

We can evaluate the expression False:[True, False]:

Prelude> False:[True, False]
[False,True,False]

It is crucial that in the expression x:xs, where x :: a, xs :: [a], for the same a. The following fails:

Prelude> 'a':[True, False]

<interactive>:11:6: error:
• Couldn't match expected type 'Char' with actual type 'Bool'
• In the expression: True
In the second argument of '(:)', namely '[True, False]'
In the expression: 'a' : [True, False]

<interactive>:11:12: error:
• Couldn't match expected type 'Char' with actual type 'Bool'
• In the expression: False
In the second argument of '(:)', namely '[True, False]'
In the expression: 'a' : [True, False]

Exercise

Read the error message in the example above, and explain in your own words what it means.


Explanation: Watch the video "Polymorphism: consing (:)" on Canvas.


Polymorphism

A function whose type contains one (or several) variables is called polymorphic. The functions [] and (:) are examples of polymorphic functions.

Here is an example of a function whose type contains two type variables:

Prelude> :t zip
zip :: [a] -> [b] -> [(a, b)]

Quiz time

Test your understanding by taking this quiz. Don't worry, it is not marked, and you can take it as many times as you want.

Exercises:

  1. Explain, in your own words, what the function zip does. In the expression zip ['x', 'y'] [False], what are the type variables a and b of zip :: [a] -> [b] -> [(a, b)] instantiated by?
  2. Find out the types of the following functions. Decide if they are polymorphic.
    1. fst
    2. (++)
    3. not
    4. head
    5. tail
    6. id
  3. Find a polymorphic function in the GHC standard library whose type contains 3 type variables or more.
  4. Read Section 3.7 of Programming in Haskell. Compare the types of the examples given there with the types ghci indicates. (Note: some of the types that ghci shows use "type classes" - you will learn about these in the next lesson.)

Summary:

  1. A polymorphic function is a function whose type contains type variables (which are typically called a, b, etc.).
  2. When applying a polymorphic function to an input, the type variables are suitably instantiated, e.g., for (++) : [a] -> [a] -> [a] applied to [True, False] and [False, False], Haskell instantiates a to Bool.