Subclasses
Next let's implement a sorting function, say Merge Sort. Its type signature
should be [a] -> [a]. It takes as input a list of as and produces another
list of as containing the same elements in sorted order. But clearly, we
cannot sort just any list. To do so, we need to have an ordering on values of
type a; we need to be able to compare two values of type a. We wouldn't be
able to sort a list of binary trees, for example. So we need to constrain a to
be a type with an ordering. This is expressed by the Ord type class:
class Ord a where
{-# MINIMAL compare | (<=) #-}
compare :: a -> a -> Ordering
compare x y | x == y = EQ
| x <= y = LT
| otherwise = GT
(<) :: a -> a -> Bool
x < y = compare x y == LT
(>) :: a -> a -> Bool
x > y == compare x y == GT
(<=) :: a -> a -> Bool
x <= y = compare x y /= GT
(>=) :: a -> a -> Bool
x >= y = compare x y /= LT
max :: a -> a -> a
max x y = if y > x then y else x
min :: a -> a -> a
min x y = if y < x then y else x
data Ordering = LT | EQ | GT
This says that an orderable type must support a whole bunch of operations.
compare x y tells us whether x < y, x == y or x > y by returning LT,
EQ or GT, a value of type Ordering. The standard comparison operators
(<), (>), (<=), and (>=) must also be supported, as do taking the
maximum and minimum of two values. The MINIMAL annotation says that an
instance definition can get away with providing only an implementation of
compare or (<=). All functions have default implementations that use the
implementation of compare or (<=).
For example, it makes sense to be able to order banner numbers:
instance Ord BannerNumber where
compare (B x) (B y) = compare x y
And now we can do things like
>>> :{
| instance Ord BannerNumber where
| compare (B x) (B y) = compare x y
| :}
>>> B 1 < B 2
True
>>> B 1 >= B 2
False
>>> B 3 >= B 3
True
>>> compare (B 5) (B 4)
GT
If you tried to compile the above definition of the Ord type class, you'd run
into trouble, and I hope you noticed why while reading through the definition:
The default implementation of compare uses x == y to test whether x and
y are equal, in which case compare x y returns EQ. This requires the type
a to support equality testing, that is, a must be an instance of Eq.
However, nothing in the definition of the Ord type class says that we make
this assumption. So the compiler complains.
Just as for function definitions, the way to fix this is to impose constraints
on the types that can be instances of Ord. The complete definition of the
Ord type class is
class Eq a => Ord a where
{-# MINIMAL compare | (<=) #-}
compare :: a -> a -> Ordering
compare x y | x == y = EQ
| x <= y = LT
| otherwise = GT
(<) :: a -> a -> Bool
x < y = compare x y == LT
(>) :: a -> a -> Bool
x > y == compare x y == GT
(<=) :: a -> a -> Bool
x <= y = compare x y /= GT
(>=) :: a -> a -> Bool
x >= y = compare x y /= LT
max :: a -> a -> a
max x y = if y > x then y else x
min :: a -> a -> a
min x y = if y < x then y else x
Remember that the type constraint Eq a => on a function signature says that
the function is applicable to an argument of any type a as long as a is an
instance of Eq. Similarly, you should read this definition of Ord as, "a
is an instance of Ord if it is an instance of Eq and implements all of the
functions that are part of the Ord type class."
So, if we want to make a type an instance of Ord, we also need to make it an
instance of Eq. Thankfully, our BannerNumber type was already an instance of
Eq, so our instance definition for Ord BannerNumber was accepted. If we
hadn't defined Eq BannerNumber, then the compiler would have complained.
Since we can make a type a an instance of Ord only if is is also an instance
of Eq, we have the guarantee that any type that is an instance of Ord is
also an instance of Eq. The compiler knows that, so it allows us to be a
bit terser in specifying type class constraints. For example, the following
function compiles just fine:
maxFirstDifferent :: Ord a => a -> a -> a -> a
maxFirstDifferent x y z | x == y = max x z
| otherwise = max x y
This function relies on being able to equality test elements of type a
(x == y) and on having a max function. The former is provided by the Eq
type class, the latter by the Ord type class. Yet, we don't have the
constraint (Eq a, Ord a) in the function's type signature, only Ord a. If we
had provided the constraint (Eq a, Ord a), the function would also have
compiled. There is nothing wrong with imposing both constraints, but the Eq a
constraint is redundant, as it is implied by the Ord a constraint.
The formal terminology is that that Ord is a subclass of Eq. This
terminology can be justified in many different ways, each equally valid. First,
the term "class" is mostly just a different word for "set". When we talk about
the type class Eq, we mean the class of all types that support equality tests,
that is, the set of all such types. Since every type that belongs to the Ord
class also belongs to the Eq class, the Ord class is a subset of the Eq
class, it is a subclass. Another way of looking at this is that every type in
the Ord class also supports all the functions defined in the Eq class,
because to make this type an instance of Ord, we need to also make it an
instance of Eq. We need to implement all the functions in both the Eq and
Ord classes for this type. In object-oriented languages, an instance of a
subclass supports all the methods of all its superclasses. Moreover, an instance
of the subclass can be used wherever an instance of the superclass is expected,
just as we can provide a type that is an instance of Ord wherever a type is
expected that is an instance of Eq. So the notion of subclasses in Haskell
aligns perfectly with the notion of subclasses in object-oriented languages,
except that classes in object-oriented languages are types, and in Haskell they
are collections of types.
The common terminology between Haskell type classes and classes in object-oriented languages goes even further in that some Haskell programmers call the functions declared in type classes methods.