In computer science, a type class is a type system construct that supports ad hoc polymorphism in a programming language. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T. Type classes were first implemented in the language Haskell after first being proposed by Philip Wadler and Stephen Blott as an extension to eqtypes in Standard ML, and were originally conceived as a way of implementing overloaded arithmetic and equality operators in a principled fashion. In contrast with the "eqtypes" of Standard ML, overloading the equality operator through the use of type classes in Haskell does not need extensive modification of the compiler frontend or the underlying type system.
Overview Type classes are defined by specifying a set of function or constant names, together with their respective types, that must exist for every type that belongs to the class. In Haskell, types can be parameterized; a type class Eq intended to contain types that admit equality would be declared in the following way:
where a is one instance of the type class Eq, and a defines the function signatures for 2 functions (the equality and inequality functions), which each take 2 arguments of type a and return a Boolean. The type variable a has kind ∗ {\displaystyle *} ( ∗ {\displaystyle *} is also known as Type in the latest Glasgow Haskell Compiler (GHC) release), meaning that the kind of Eq is
The declaration may be read as stating a "type a belongs to type class Eq if there are functions named (==), and (/=), of the appropriate types, defined on it". A programmer could then define a function elem (which determines if an element is in a list) in the following way:
The function elem has the type a -> [a] -> Bool with the context Eq a, which constrains the types which a can range over to those a which belong to the Eq type class. (Haskell => can be called a 'class constraint'.) Any type t can be made a member of a given type class C by using an instance declaration that defines implementations of all of C's methods for the given type t. For example, if a new data type t is defined, this new type can be made an instance of Eq by providing an equality function over values of type t in any way that is useful. Once this is done, the function elem can be used on [t], that is, lists of elements of type t. Type classes are different from classes in object-oriented programming languages. Specifically, Eq is not a type: there is no such thing as a value of type Eq. Type classes are closely related to parametric polymorphism. For example, the type of elem as specified above would be the parametrically polymorphic type a -> [a] -> Bool were it not for the type class constraint "Eq a =>".
Higher-kinded polymorphism A type class need not take a type variable of kind Type but can take one of any kind. These type classes with higher kinds are sometimes called constructor classes (the constructors referred to are type constructors such as Maybe, rather than data constructors such as Just). An example is the Monad class:
That m is applied to a type variable indicates that it has kind Type -> Type, i.e., it takes a type and returns a type, the kind of Monad is thus:
Multi-parameter type classes Type classes permit multiple type parameters, and so type classes can be seen as relations on types. For example, in the GHC standard library, the class IArray expresses a general immutable array interface. In this class, the type class constraint IArray a e means that a is an array type that contains elements of type e. (This restriction on polymorphism is used to implement unboxed array types, for example.) Like multimethods, multi-parameter type classes support calling different implementations of a method depending on the types of multiple arguments, and indeed return types. Multi-parameter type classes do not require searching for the method to call on every call at runtime; rather the method to call is first compiled and stored in the dictionary of the type class instance, just as with single-parameter type classes. Haskell code that uses multi-parameter type classes is not portable as of the Haskell 98 standard, which is not the newest standard. The popular Haskell implementations, GHC and Hugs, support multi-parameter type classes.
Functional dependencies In Haskell, type classes have been refined to allow the programmer to declare functional dependencies between type parameters—a concept inspired from relational database theory. That is, the programmer can assert that a given assignment of some subset of the type parameters uniquely determines the remaining type parameters. For example, a general monad m which carries a state parameter of type s satisfies the type class constraint Monad.State s m. In this constraint, there is a functional dependency m -> s. This means that for a given monad m of type class Monad.State, the state type accessible from m is uniquely determined. This aids the compiler in type inference, as well as aiding the programmer in type-directed programming. Simon Peyton Jones has objected to the introduction of functional dependencies in Haskell on grounds of complexity.
Type classes and implicit parameters Type classes and implicit parameters are very similar in nature, although not quite the same. A polymorphic function with a type class constraint such as:
can be intuitively treated as a function that implicitly accepts an instance of Num:
… excerpt ends here. Continue reading the full article.
