Type class (computer science)

Type classes are a functional programming construct for implementing ad hoc polymorphism . Type classes were developed for the Haskell language. In principle, they are similar to the concept of interfaces , but have nothing to do with the classes of object-oriented programming .

history

Type classes were originally designed to systematically overload mathematical operators. The approach turned out to be very versatile, so that it can quickly be used for other things, such as B. Monads used. Nowadays, type classes are one of the most important tools of the Haskell language and are used in almost all areas, mostly for defining interfaces or generalizing libraries.

introduction

Type classes define functions that can be called for each instance of the type class. You can create an instance for each type by defining the functions of the type class for that type. A simple example is the operator (==)that checks two variables for equality. (In Haskell, operators are the same as functions and are not dealt with separately, but they are used in infix notation ) The associated type class Eq(from eq uality) is defined as follows:

1 class Eq a where
2   (==) :: a -> a -> Bool
3   (/=) :: a -> a -> Bool
4 
5   a == b = not (a /= b)
6   a /= b = not (a == b)

The class defines two functions, each of which has two variables of type a, the parameter of the type class, as arguments: (==)is an operator that (/=)checks two variables for equality, the operator checks for inequality. Its symbol is derived from the mathematical sign . In addition to the definition of the operators (lines 2 and 3), in which their type is specified, you can also specify a standard implementation of the operators. This is e.g. B. useful when some functions are potentially redundant, but a specific implementation is more efficient for certain instances. In the case of , both functions are defined by the other, so it is sufficient to implement only one. ${\ displaystyle \ neq}$ Eq

To define an instance of a type class, write the following (here using the example of type Bool):

1 instance Eq Bool where
2   True  == True  = True
3   False == False = True
4   _     == _     = False

The instance only overloads the function (==). As described above, the check for inequality is automatically defined as the negation of equality. With the definition of the instance, the equality check can now also be used for Boolean values.

The trick is that you don't need to know what data type it is in order to apply a function of a type class to it. It is sufficient that an instance of the type class is available. This information can be added in Haskell via an extension of the type system. Here, for example, the function nub: It removes duplicates from a list. The only known thing about the elements of the list is that they are instances of the type class Eq. This is Eq acommunicated via the context before the type signature:

1 nub :: Eq a => [a] -> [a]
2 nub []     = []
3 nub (x:xs) = x : nub (filter (/= x) xs)

Usage examples

Type classes are used in the Haskell language for many purposes, such as: B .:

Show: Definition of a function showwhich, like the method toString()in Java , can represent a value as a string.
Read: Definition of a function readwith which values can be parsed and packed into a data type.
Monad: Cross-type syntax for monads

implementation

There are several ways to implement type classes. The original implementation of type classes and used in most implementations, including the Glasgow Haskell Compiler , is explained below.

Typically, type classes are implemented by replacing each type class with a data type. It contains the individual methods of the type class as fields. If a function now needs an instance of a type class for one of the parameters, an object of the data type belonging to the desired type class is transferred, which represents the instance. In this way, no expansion of the existing type system is required for the final code. You can imagine this using the example of the class mentioned above Eq:

The type class Eqis Eqtranslated into a data type . (A different name may be used in a real implementation) This takes the type to be instantiated as a type parameter and has the fields of the type classes as methods:

data Eq a = Eq (a -> a -> Bool) (a -> a -> Bool)

A variable of the type is now Eqgenerated for each instance :

1 instanceEqBool :: Eq Bool
2 instanceEqBool = Eq eqBool (\a b -> not (eqBool a b)) where
3   eqBool True  True  = True
4   eqBool False False = True
5   eqBool _     _     = False
6 
7 -- hier noch ein weiteres Beispiel: Der Einheitstyp ()
8 instanceEqUnit :: Eq ()
9 instanceEqUnit = Eq (\_ _ -> True) (\_ _ -> False)

If a function now Eq aneeds the context , this is Eq atranslated into an additional parameter of the type . The required methods are then called from this parameter. If a function called from this function also needs the context, it is transferred. The type system guarantees that the transferred functions are of the correct type:

1 nub :: Eq a => [a] -> [a]
2 -- wird zu
3 nub :: Eq a -> [a] -> [a]
4 nub _           []     = []
5 nub (Eq _ (/=)) (x:xs) = x : nub (filter (/= x) xs)

Individual evidence

^ Philip Wadler, Stephen Blott: How to make ad-hoc polymorphism less ad hoc. ( Postscript ) University of Glasgow, October 1988, accessed May 19, 2011 .

[1] Philip Wadler, Stephen Blott: How to make ad-hoc polymorphism less ad hoc. ( Postscript ) University of Glasgow, October 1988, accessed May 19, 2011 .