### Type classes and qualified types

In mathematics and in most programming languages, + and - denote addition and subtraction; but what should their types be? Of course, we want to be able to add both integers and floating-point numbers, but these two functions correspond to completely different machine operations; we may also want to define arithmetic on new types, such as complex or rational numbers.

To better understand the problem, consider a function to add the elements of a list of integers to an accumulator. Assuming that + only means integer addition we could define

```add :: Int -> [Int] -> Int
```

As long as there are elements in the list, we add them to the accumulator and call the function recursively; when the list is empty the accumulator holds the result.

But this function makes perfect sense also for floats (or rationals, or complex numbers, or ...) and we would like to use it at those types, too. One could imagine an ad hoc solution just for the arithmetic operators, but we prefer a general solution.

A first step is to introduce the following struct type:

```struct Num a where
(+), (-), (*) :: a -> a -> a
```

A value of type Num Int has three fields, defining addition, subtraction and multiplication, respectively, on integers. (Of course, we can construct an object of this type using any three functions of the prescribed type, but the intention is to supply the standard arithmetic operators.) Similarly, a value of type Num Float defines the corresponding operators for floating-point numbers.

Assume that we have properly defined struct value numInt :: Num Int. We can then define

```add :: Int -> [Int] -> Int
```

Of course, the first argument in the recursive call now looks horrible; it would be silly to write integer addition in this way. But it has now become easy to generalize the code by abstracting out the Num object as an argument:

```add :: Num a -> a -> [a] -> a
add d acc (x : xs) = add d (d.(+) x acc) xs
add d acc [] = acc
```

This version of add can be used for lists of any type of objects for which we can define the arithmetic operators, at the expense of passing an extra argument to the function.

The final step that gives an acceptable solution is to let the compiler handle the Num objects. We do this by declaring Num to be a type class, loosely following the terminology introduced in Haskell:

```typeclass Num
```

For any such type, its selectors can be used without the dot notation identifying a struct value from which to select. Whenever a selector of a type class occurs in a function body, the compiler does the following:

• adds an extra parameter of the type class to the function;
• changes the selector occurrences in the function body to a selection from that parameter.
• wherever the function is used, adds an object of the proper type as an extra argument.
• changes the type of the function to be a qualified type; the type class occurs as a constraint after \\.

With Num defined as a type class, our running example becomes

```add :: a -> [a] -> a \\ Num a
```

As a convenience, the declaration of the struct type and the type class declaration can be combined into one single declaration:

```typeclass Num a where
(+), (-), (*) :: a -> a -> a
```

To use function add to sum a list of integers, we would like to write e.g. add 0 [1, 7, 4]. The compiler must now insert the extra argument numInt, a struct value with selectors for the three arithmetic operators at type Int. However, since there might be several objects of type Num Int defined, we must indicate in instance declarations the objects that are to be used at different types.

```instance numInt :: Num Int
```
An instance declaration is essentially just a type signature flagged with the additional information that the corresponding value is available for automatic argument insertion by the compiler. For convenience, an instance declaration and its struct value definition can also be combined into one declaration. As an example, here is an instance of Num for rational numbers:
```data Rational = Rat Int Int

instance numRat :: Num Rational where
Rat a b + Rat c d = Rat (a*d + b*c) (b*d)
Rat a b + Rat c d = Rat (a*d - b*c) (b*d)
Rat a b * Rat c d = Rat (a*c) (b*d)
```

This definition should be improved by reducing the fractions using Euclid's algorithm, but we omit that. We just note that the arithmetic operators in the right hand sides are at type Int; thus the compiler will insert the proper operations from the instance numInt, avoiding the overhead of extra parameters.

This solution combines ease of use and flexibility with type security. A possible disadvantage is inefficiency; an extra parameter is passed around. To address this, the user may add a specific type signature; if the user assigns the type Int -> [Int] -> Int to add, giving up flexibility, the compiler will not add the extra parameter, instead inserting integer operations directly into the function body.

Several type classes, including Num, are defined in the Prelude, together with instances for common cases.

The compiler must be able to select the proper object of a type class to use whenever a function with a qualified type is used; this choice is guided by the context of the function application. In certain cases ambiguites can occur; these are resolved using default declarations.

Normally, the combined declaration forms are used both for type classes and instances. Separate typeclass declaration of a struct type can only be done in the module where the struct type is defined.

#### Subtyping constraints

Also subtyping relations may be used as constraints in qualified types. As a simple example, consider the function

```twice f x = f (f x)
```

Obviously, twice has a polymorphic type. At first, it seems that the type should be

```(a -> a) -> a -> a
```
However, it can be assigned the more general type
```twice :: (a -> b) -> a -> b \\ b < a
```
Types with subtype constraints will never be assigned by the compiler through type inference, but can be accepted in type-checking.