CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2015

Home Policies Lectures Notes Labs

---

Piazza

Lecture 5: Polymorphism

Haskell has an expressive type system, which supports several kinds of polymorphism, i.e., ways to define and name functions so that the same function (or the same name) can meaningful at multiple types. This facilitates rich libraries and common vocabularies.

Polymorphic ADTs

Type variables can also be used to define polymorphic abstract data types, e.g.,

data Pair x y = Pair x y

In this case, we can have, e.g.,

Pair 1 "one" :: Pair Int String

or

Pair "one" 1.0 :: Pair String Double

Note here that these values are associated with types that do not have type variables. This is not a coincidence. All of the inhabited types of Haskell, i.e., all of the types for which there are values, cannot have type variables.

Type variables always begin with a lower-case letter, which distinguishes them from type constructors, which are either begin with upper-case letters, or in the binary case, can be infix-operators (cf., (:)).

Indeed, a moment's reflection on the list type that we've been using all along is that it amounts to the following, module a bit of syntactic sugar:

data List x = Null | Cons x (List x)

Polymorphic functions

Polymorphic ADTs naturally give rise to polymorphic functions, whose types include type variables. Consider, e.g., the definition of length for a list:

length [] = 0 length (_:as) = 1 + length as

What is the type of length? Well, in any specific context, it depends on the type of the list that it's going to be applied to. If we're applying length to a [Int], then length will have type [Int] -> Int, whereas if we're applying it to a [Double], it has type [Double] -> Int. But what is the type of length at its definition, the type inferred by Haskell? We can find out using the :t command in the interpreter:

> :t length length :: [a] -> Int

Here, the type means that length can take as input a list over any type, and compute its length.

Now, what about the type of map? You might guess, based on the notion that map takes a function and a list and returns a list, that it's type is

map :: (a -> a) -> [a] -> [a]

As it turns out, this is not as general as it could be. The actual type of map is:

> :t map map :: (a -> b) -> [a] -> [b]

Let's see an example. By way of preamble, if we have an ordinary binary function f, we can turn it into an infix operator by enclosing it in backquotes, e.g., `f`. This is often done for the div function, which performs integral division,

> 5 `div` 2 2

But another reason to use backquotes is to set up a binary function for a section based on fixing its second argument. Here's an example:

> map (`replicate` '*') [1,2,3] ["*","**","***"]

Let's take a moment to understand this. The replicate function is defined in Data.List, and exported from there to the Prelude, like most list functions. It takes an Int and a value (of any type), and then builds a list with the given number of instances of that value. Thus, replicate 3 'a' reduces to ['a','a','a'], which is just "aaa". The section (`replicate` '*') might be more easily understood by introducing a temporary function:

stars :: Int -> String stars n = replicate n '*'

And then proceeding to the (all-but inevitable) η-reduction.

The stars function builds a string of asterisks of the given length, i.e., stars 5 reduces to "*****".

Inferring the type of a complex polymorphic function can be tricky. It's often useful when you're getting started, to define the function first without a type ascription, and then to let Haskell infer the type itself via the :t command in the interpreter. This type can then be cut-and-pasted back into the source. Still, remember that you are responsible for top-level type ascriptions in delivered code, so they must go there. And also make sure you understand the type!

Type classes

Haskell has another type of polymorphism, via type classes. If you're familiar with object oriented programming, the name here might be a bit misleading, suggesting that Haskell has a class system analogous to that of Java or C++. That's not actually the case. Haskell's type classes are more analogous to the notion of interface from Java, or protocol from Objective-C or Swift.

The kind of functional polymorphism we considered in the previous section is very much a monomorphic kind of polymorphism, in that while these functions may take different types of arguments, there is only one implementation, only one way of "doing it." That's not always enough. Let's consider a simple issue: the equality predicate (==). We'll want to be able to use equality as a binary predicate on values of very different types. Just one way of "doing" equality won't work. We need another mechanism:

class Eq a where (==), (/=) :: a -> a -> Bool x /= y = not (x == y) x == y = not (x /= y)

This defines the type class Eq, which contains two functions, equality (==), and inequality (/=). The declaration says that any type a which is an instance of the Eq type class must have binary predicates (==) and (/=), i.e., functions of type a -> a -> Bool. In addition, this class declaration provides default definitions of (==) and (/=). It should be apparent that we can't successfully use both default definitions at the same time! But the effect is that an instance declaration need only define one, and we get a definition of the other “for free.” E.g., recalling our definition of Dollar from Lecture 3:

data Dollar = Mill Integer instance Eq Dollar where Mill x == Mill y = x == y

type classes interact with the type system via constraints on the types of free variables in a type expression. For example, consider the Data.List function elem, which determines whether a value occurs in a list: > 3 `elem` [1,2,3,2,3,4] True

It's easy to implement elem via a natural recursion:

elem _ [] = False elem x (a:as) | x == a = True | otherwise = elem x as

or, more concisely

elem _ [] = False elem x (a:as) = (x == a) || elem x as

relying on the left-biased definition of (||).

But it should be clear that the definition of elem relies on the list elements supporting an equality test. How is this reflected in the type of elem. Via a type constraint:

> :t elem elem :: Eq a => a -> [a] -> Bool

What this type constraint means is that elem can be used at type a -> [a] -> Bool whenever a is an instance of the Eq type class.

Beginning with GHC 7.10, elem has an even more general type:

> :t elem elem :: (Eq a, Foldable t) => a -> t a -> Bool

Note here that the list type is an instance of the Foldable type class, and that if we need to include multiple constraints, they're "tupled." We'll have more to say about Foldable later.

One of the novel features of Haskell is that of derived instances. Here, a simple declaration will illustrate what's going on:

instance (Eq x, Eq y) => Eq (Pair x y) where Pair x0 y0 == Pair x1 y2 = x0 == x1 && y0 == y1

Derived type classes are a powerful feature of Haskell, which enable us to add instances of polymorphic algebraic types to type classes. Here's a simple example that hints at much more:

instance (Eq a, Eq b) => Eq (a,b) where (a0,b0) == (a1,b1) = a0 == a1 && b0 == b1

Note here that this is a very common case: equality for an ADT requires having the same constructor (in this case, Pair), and equal components. This pattern happens so much that Haskell allows us to derive Eq instances, cf.

data Pair x y = Pair x y deriving (Eq,Show)

As this example hints, Show is a type class too. Much of the expressiveness of Haskell comes from a particularly well designed set of type classes, which we will explore in the rest of the course.

---

© 2009–2015 Ravi Chugh, Stuart A. Kurtz
Last modified: December 30, 2015