Type Classes

If you have programmed in Java before, you are hopefully familiar with interfaces. If you have programmed in Rust or Go before, you should be familiar with traits. In Java, Rust or Go, we would say that a type implements an interface or trait. In Haskell, we say that a type is an instance of a type class. That's merely a change in terminology. The concept is exactly the same in all of these languages.

Let's look at interfaces in Java. An interface specifies a list of methods. To implement such an interface, a class needs to provide implementations for all the methods in the interface. Similarly, a trait in Go or Rust specifies a list of functions. To implement this trait for some type, we need to provide implementations of all functions in the trait for this type.

In Haskell, we define a type class by defining a bunch of type signatures of functions that types in this type class need to support. That's the same as specifying a bunch of methods in an interface without providing implementations for them. To make a type an instance of this type class, we need to provide implementations of all of these functions for this type.

Let's use some examples to motivate and develop two commonly used type classes in Haskell. Assume we want to implement the elem function that reports whether a given list contains a given element. This function does in fact exist as part of the standard library, but we'll develop it from scratch. If we ask whether the list [1, 2, 3] contains the element 2, the answer is yes (True):

GHCi

>>> 2 `elem` [1,2,3]
True

The element 4 is not in this list:

GHCi

>>> 4 `elem` [1,2,3]
False

If we wanted the elem function to work only for lists of Ints, here is how we would implement it:

elem :: Int -> [Int] -> Bool
elem q = containsQ
  where
    containsQ []                 = False
    containsQ (x:xs) | x == q    = True
                     | otherwise = containsQ xs

This says that that the query element q is not contained in the empty list. If the list is non-empty, that is, it is of the form x:xs, then if x == q, then q is clearly part of the list. If x /= q, then x:xs contains q if and only if xs contains q, so we call containsQ xs recursively.

Now, implementing an elem function only for integer lists is silly. Clearly, our implementation does not use the fact that the list elements are integers at all. The only property of the list elements that the function relies on is that we can test whether any given list element equals q. So, we would like to implement a much more widely applicable version of elem that allows us to test whether any list of type [a], a list of as, contains a particular value of type a. Here's what this would look like:

elem :: a -> [a] -> Bool
elem q = containsQ
  where
    containsQ []                 = False
    containsQ (x:xs) | x == q    = True
                     | otherwise = containsQ xs

The problem is that this doesn't work:

GHCi

>>> :{
  | elem :: a -> [a] -> Bool
  | elem q = containsQ
  |   where
  |     containsQ []                 = False
  |     containsQ (x:xs) | x == q    = True
  |                      | otherwise = containsQ xs
  | :}

<interactive>:66:26: error:
    • No instance for (Eq a) arising from a use of ‘==’
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            elem :: forall a. a -> [a] -> Bool
    • In the expression: x == q
      In a stmt of a pattern guard for
                     an equation for ‘containsQ’:
        x == q
      In an equation for ‘containsQ’:
          containsQ (x : xs)
            | x == q = True
            | otherwise = containsQ xs

Since a can be any type, Haskell cannot possibly guess when we want to consider two elements of type a to be equal. It is our responsibility to implement an appropriate equality test for values of type a. We can group all types that support equality tests together to form a class of types, the type class Eq. Our elem function will work for any type a that is a member of this type class or, in Haskell speak, is an instance of this type class.

That's what the error message above tells us, once we know how to read it. The current type signature elem :: a -> [a] -> Bool claims that elem should work for any type; no constraints whatsoever. The compiler looks at the implementation of elem and realizes that on the second-last line, we use x == q as a pattern guard. It concludes that a cannot just be any type: it must support equality tests, it must be an instance of Eq. The error message "No instance for (Eq a) arising from the use of ==" says that according to our type signature, the type a is not required to be an instance of Eq, but the use of the == operator in the expression x == q requires a to be an instance of Eq. Thus, we have a problem. The error message even says how we can get rid of the error: "Possible fix: add (Eq a) to the context of the type signature [...]." So let's do that:

elem :: Eq a => a -> [a] -> Bool
elem q = containsQ
  where
    containsQ []                 = False
    containsQ (x:xs) | x == q    = True
                     | otherwise = containsQ xs

Now our function compiles:

GHCi

>>> :{
  | elem :: Eq a => a -> [a] -> Bool
  | elem q = containsQ
  |   where
  |     containsQ []                 = False
  |     containsQ (x:xs) | x == q    = True
  |                      | otherwise = containsQ xs
  | :}

We'll talk about the syntax for imposing constraints on the argument types of functions shortly. For now, let's look at how we define type classes.