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

Eq

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.

Derived Instances

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 y1 = x0 == x1 && y0 == y1

Note that the derived instance above is a very common case: equality for an ADT requires having the same constructor (in this case, Pair), and equal components.

Automatically Derived Instances

The pattern above happens so much that Haskell will automatically generate Eq instances, cf.

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

In fact, the Prelude shows that even derived instance declarations such as

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

can often be automatically derived:

class Eq a where .... deriving instance (Eq a, Eq b) => Eq (a,b)

This is a lot to ponder, but we won't take a closer look at any more deriving instance clauses in this course.

Number Types

Numeric types are described by the Num class:

class Num a where (+), (-), (*) :: a -> a -> a negate :: a -> a abs :: a -> a signum :: a -> a ...

Num is the basis of a hierarchy of various numeric types. For example, Int and Integer are instances of the Integral subclass of Num, and Float and Double are instances of the Fractional subclass of Num.

We will not delve much into this numerical tower, but you can learn more by reading the documentation, this tutorial, or by using the :info command to poke around:

> :info Num ... > :info Fractional ... > :info Int ...

Ord

Haskell's Prelude defines an Ord type class:

class (Eq a) => Ord a where compare :: a -> a -> Ordering (<), (<=), (>), (>=) :: a -> a -> Bool max, min :: a -> a -> a ...

The documentation identifies compare as a minimal complete definition, meaning that default implementations are set up in a way such that all other members can be (and are) implemented in terms of compare.

*Exercise 7.1 Read the documentation on Ord, and then provide a parsimonious instance of Ord for suitably type-constrained instances of Pair.

Enum

Haskell provides concise syntax for enumerating values of enumerable types:

> [1..10] [1,2,3,4,5,6,7,8,9,10] > ['a'..'z'] "abcdefghijklmnopqrstuvwxyz" > [2,4..10] [2,4,6,8,10] > ['a','e'..'u'] "aeimqu"

The Enum type class describes types that can be enumerated (i.e. indexed from 0 to n-1):

class Enum a where toEnum :: Int -> a fromEnum :: a -> Int ...

Show

The Show class describes types whose values can be converted to Strings:

class Show a where show :: a -> String ...

As we have seen, Haskell can auto-generate Show instances:

data Pair x y = Pair x y deriving (Eq, Show) > Pair "Hello" 161 Pair "Hello" 161

Exercise 7.2 Instead of deriving the default Show instance for Pair, define one that produces the following:
> Pair "Hello" 161 ( "Hello" , 161 )

Read

The Read class is complementary to Show:

class Read a where read :: String -> a ...

The read function parses a String to produce a value of the given type. Together, reading and showing values allow programs to interact with the outside world (e.g. Strings from user input, the file system, and network requests). We will have much more to say about parsing and the outside world later.

Looking Ahead

Much of the expressiveness of Haskell comes from a particularly well designed set of type classes. In this lecture, we saw several type classes that describe "simple" kinds of data. In the rest of the course, we will explore type classes that describe more complex data, as well as recurring patterns of computation.