Haskell: the Basics of Type Classes

One thing that we've seen already in Haskell programs is type
classes. Today, we're going to try to take our first look real look
at them in detail - both how to use them, and how to define them. This still isn't the entire picture around type-classes; we'll come back for another look at them later. But this is a beginning - enough to
really understand how to use them in basic Haskell programs, and enough to give us the background we'll need to attack Monads, which are the next big topic.

Type classes are Haskell's mechanism for managing parametric polymorphism. Parametric polymorphism
is a big fancy term for code that works with type parameters. The idea of type classes is to provide a
mechanism for building constrained polymorphic functions: that is, functions whose type involves a type parameter, but which needs some constraint to limit the types that can be used to instantiate it, to specify what properties its type parameter must have. In essence, it's doing very much the same thing that parameter type declarations let us do for the code. Type declarations let us say "the value of this parameter can't be just any value - it must be a value which is a member of this particular type"; type-class declarations let us say "the type parameter for instantiating this function can't be just any type - it must be a type which is a member of this type-class."

The type declarations in Haskell let us do this in a very flexible way, derived from something called the Curry-Howard isomorphism, which shows that type systems for lambda calculus are isomorphic to inference systems in some logic. The simply-typed lambda calculus has a type system related to simple propositional logic; Haskell, with its type variables, has a type system derived from first order predicate logic.

In fact, in Haskell, when you declare a type with a type variable, in the logic of the type
system, you've implicitly quantified the type with a universal quantifier. So a type "a -> b" in
Haskell is actually implicitly understood to mean: (∀ a,b : a → b).

If you think back to predicate logic, you might recall that "such that" constructions like "∀ x such that x ∈ S: T(x) → U(x)" are not really primitives in the logic - they're just a shorthand for a logical implication: ∀ x : (x ∈ T) → (T(x) → U(x)). That's exactly what Haskell does with type-classes - it writes that as predicate (e.g., "Num(x)) with an implication symbol ("=>"). The reason for the separate implication symbol is
basically just to visually distinguish the part of the type that is a constraint on the type variables. So when you write something like "(Eq a) => a -> a -> Bool", what your really saying is "For all types a such that a is in Eq, this function has type "a -> a -> Bool".

Enough theory - let's look at how we really use these things. Suppose we wanted to write a function
that added a list of values. Without using type classes, you might try to write it as:

addValues :: [a] -> a
addValues v:vs = v + (addValues vs)
addValues v:[] = v

If you were to try to compile that function, you'd get a compile error: it uses the "+" operation on values of type a, but the type declaration says that it works on any type a. What we need to do is specify a type constraint that supports addition - like Num:

>addValues :: Num a => [a] -> a
>addValues (v:[]) = v
>addValues (v:vs) = v + (addValues vs)

What we've done is chosen the appropriate type predicate for selecting types that we can use in the function. And there's something important about that: the Haskell prelude and standard libraries define a lot of type classes. If you're not defining a type-class for something very specific to your application, there's a good chance that there's already a suitable type-class in the libraries, and you should use the library one, rather than defining your own. Your code will be much more portable and reusable if you take advantage of the type classes in the standard libraries.

Whether you're only going to use library classes, or define your own, you'll still need to be able to read type-class declarations, and read and write instances.

A type-class declaration consists of two basic parts: the first is a declaration of what operations (methods) an instance of the class must support; and the second is a set of default implementations of those methods.

For example here's the declaration for the type-class Ord, which is the class of all
ordered types:

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

    compare x y | x == y    = EQ
                | x <= y    = LT
                | otherwise = GT

    x <= y  = compare x y /= GT
    x <  y  = compare x y == LT
    x >= y  = compare x y /= LT
    x >  y  = compare x y == GT

    -- Note that (min x y, max x y) = (x,y) or (y,x)
    max x y | x <= y    =  y
            | otherwise =  x
    min x y | x <= y    =  x
            | otherwise =  y

The first line declares the name of the class being declared, and any constraints on what types can be instances of this class. The constraints are other type classes that a type must be an instance of before it can be made an instance of the new type. In the case of Ord, it says
"(Eq a) => Ord a", which means before a type can be an instance of Ord,
it must also be an instance of Eq. The type variable a will be used throughout the class definition to refer to an instance of type-class Ord.

After the declaration line, there are a list of function-type declarations. These declare the
methods that must be implemented in order to be an instance of the class. (We'll get to how
functions are made into type-class methods when we look at the instance declarations.)

What this says is: for a type to be an instance of Ord, it must first be an instance of Eq; and to be an instance of Ord, it needs to provide implementations
of methods for compare, <, <=, >, >=, max, and min. It then provides some default implementations - if an instance declaration doesn't specify an implementation of a method for its type, then the default from the class declaration will be used. There's one interesting thing to note about the default methods: a default method can use any operation specified on the type-class, or required by the class constraint. The default methods do not have to make sense together. If you were to use Ord without providing an implementation of either <= or compare, you'd wind up the Ord operations all being infinite loops! The default implementation of compare is written in terms of <=; and the default implementation of <= is written in terms of compare.

So what would a type-instance of class Ord look like? Let's try putting together the beginnings of an implementation of surreal numbers..

>-- A surreal number is a number with two sets of surreals:
>--    a left set which contains elements less than it, and
>--    a right set which contains elements greater than it. 
>-- By definition, zero is the surreal with both sets empty.
>
>data Surreal = Surreal [Surreal] [Surreal] deriving (Eq, Show)
>srZero = Surreal [] []
>srPlusOne = Surreal [srZero] []
>srMinusOne = Surreal [] [srZero]
>srPlusOneHalf = Surreal [srZero] [srPlusOne]

Then, we implement the basic ordering operations on surreal numbers. We don't do anything special - just implement them as perfectly normal functions. As a reminder, here's the definition of ≤ for surreal numbers:

Given two surreal numbers x = {X_L|X_R} and y = {Y_L|Y_R}, x ≤ y if and only if:

1. ¬∃x_i∈X_L : y ≤ x_i, and
2. ¬∃y_i∈Y_R : y_i ≤ x

>srleq :: Surreal -> Surreal -> Bool
>srleq x@(Surreal [] []) y@(Surreal [] []) = True
>srleq x@(Surreal xl xr) y@(Surreal yl yr) = 
>      (all (\yi -> not (srleq yi x))  yr) &&
>      (all (\xi -> not (srleq y xi)) xl)

Now, we can bind these functions into the type-class class method,
so that they'll be used for surreal numbers:

>instance Ord (Surreal) where
>   x <= y  = srleq x y

The where clause of the instance declaration contains
a perfectly normal list of function declarations. The only reason for separating the function declarations from the instance declaration is
because it allowed us to write the type declaration, and it made the
code clearer to have a separate declaration of the ≤ operation (with the explanation of what ≤ means for surreal numbers) than it would have to
put the implementation in-line.

With that declaration, we can now use all of the comparison operations defined in Ord on our surreal numbers:

*Main> srZero <= srPlusOne
True
*Main> srZero <= srMinusOne
False
*Main> srPlusOneHalf > srZero
True
*Main> srPlusOneHalf < srPlusOne
True
*Main> srMinusOne <= srZero
True
*Main> compare srZero srMinusOne
GT
*Main>