Controlling Polymorphism Using Type Classes

Recall that we call a function or data type polymorphic if it is parameterized by one or more type variables. Examples include [a] or Maybe a. We also called such parameterized types type constructors or type functions because Maybe is not a type at all. To obtain a concrete type, we need to specify a concrete type we want to substitute for the type variable a. A Maybe Int stores maybe an Int value, a Maybe Char stores maybe a Char value, and so on.

The polymorphic functions and data types we have seen so far,

• List a
• [a]
• Maybe a
• map
• head
• tail
• ...,

all have one thing in common: they do not care at all about what type we pass as the argument a. We can build a list of Ints, a list of Bools, a list of functions, a list of lists of trees of Maybe values, and so on.

Such polymorphic data types and functions are clearly the most flexible, exactly because they work with any types we could substitute for the type variables. However, they are also extremely restricted in what they can do with the values of this substituted type. Consider a list of type [a]. Any function

f :: [a] -> b

cannot really do very much with the elements of type a stored in the list. That's exactly because a can be any type. f cannot add two values in the list together, because that works only for numbers and we might call f on a list of functions, of type [c -> d]. In this case, we substitute the type c -> d for a. How would we add two such functions? f cannot apply the functions in the list to some argument either, because we may call f on a list of Ints, of type [Int], and Int's cannot be applied to other values. Anything interesting we might be tempted to do with the elements of f's argument list doesn't work because we don't know anything about the type a. As a result, f can drop some elements of the list, make copies of some elements in the list, but it cannot inspect the elements in f in any way; it treats them as opaque entities. That's clearly very constraining because there is only so much we can do without inspecting the arguments of a function.¹

To implement more interesting functions, we need a mechanism to say, "This functions works for any list of type [a], but a can't just be any type; it needs to satisfy some constraints." For example, to sort a list, we require that the elements in the list can be compared. To add the elements in a list together, we require that the list elements are numbers. To search for a specific element in a list, we need to support equality testing between elements of type a. Haskell's mechanism to express these types of constraints is type classes. They are the topic of this chapter.

---

1. Taking this argument further, we can argue that a function f :: [a] -> b cannot be defined at all. That's because b is also a type variable, one that we do not know anything about. f would have to be able to produce a value of any type b from a list of values of any other type a. That's simply not possible. If we change the type of f to [a] -> a, then such functions does exist. Such a function would be able to return any of the elements in the given list. It cannot do anything else, but it can do that. ↩