Lecture 6: 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

Type variables always begin with a lower-case letter, which distinguishes them from type constructors, which 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)

We haven't seen the Maybe type before, but it's a very simple type which is used to package either zero or one value of a given type, and so is useful for dealing with situations where we want to return "no result."

data Maybe a = Nothing | Just a

Exercise 6.1 We have occasionally implemented functions that crash with exceptions on certain inputs. It is often preferable, instead, to denote "errors" explicitly using Maybe rather than implicitly with failure. Identify some functions that fall into this category and re-implement "safer" versions of them.

Apple aficionados might note that "optionals" are Swiftese for Maybe. Part of what makes Maybe nice is that Haskell provides (through general means) facilities that reduce the overhead involved in dealing with Maybe-wrapped types, which we'll learn later in the quarter. In Swift, similar facilities are provided, albeit through means specific to optional-wrapped types. There's more here in Haskell to steal, and all but inevitable that it will eventually be stolen. Implicit in this discussion is a rationale for learning Haskell now, because even it if doesn't become your favorite language, knowing it will enable you to anticipate how your favorite language will evolve, and how to use those features once they do appear.

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

Note that infix operators defined in this way can participate in Haskell's precedence and associativity system, e.g.,

> :t div class (Real a, Enum a) => Integral a where ... div :: a -> a -> a ... -- Defined in ‘GHC.Real’ infixl 7 `div`

I.e., `div` associates to the left at precedence level 7, which happens to be the associativity and precedence of multiplication (*) and floating-point division (/), as you should expect.

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 '*'

which can be transformed to

stars n = (`replicate` '*') n

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

stars = (`replicate` n)

Note here that it's tempting to think that we can eliminate the parentheses, but we can't. In this context, they're not just indicating grouping, but in fact are an essential part of Haskell's syntax for representing sections.

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

An old-school (at least, old-school in the Haskell context) approach to this is to use the library function flip f y x = f x y, and then rewrite our way to an η-reduction via

stars n = replicate n '*' stars n = flip replicate '*' n stars = flip replicate '*'

Note that the Haskell code-improvement tool hlint will always suggest replacing “sections via flip” with actual sections.

*Exercise 6.2 What is the type of the occurrence of map in the following?

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

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!