Frequent Links
Type class
In computer science, a type class is a type system construct that supports ad hoc polymorphism. 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 first appeared in the Haskell programming language,^{[1]} and were originally conceived as a way of implementing overloaded arithmetic and equality operators in a principled fashion.^{[2]}^{[3]} In contrast with the "eqtypes" of Standard ML, overloading the equality operator through the use of type classes in Haskell does not require extensive modification of the compiler frontend or the underlying type system.^{[4]}
Since their creation, many other applications of type classes have been discovered.
Contents
Overview
The programmer defines a type class 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:
class Eq a where (==) :: a > a > Bool (/=) :: a > a > Bool
This 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 member
in the following way:
member :: (Eq a) => a > [a] > Bool member y [] = False member y (x:xs) = (x == y)  member y xs
The function member
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. (Note: Haskell =>
can be called a 'class constraint'.)
A programmer can make any type t
a member of a given type class C
by using an instance declaration that defines implementations of all of C
's methods for the particular type t
. For instance, if a programmer defines a new data type t
, they may then make this new type an instance of Eq
by providing an equality function over values of type t
in whatever way they see fit. Once they have done this, they may use the function member
on [t]
, that is, lists of elements of type t
.
Note that type classes are different from classes in objectoriented programming languages. In particular, 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, note that the type of member
as specified above would be the parametrically polymorphic type a > [a] > Bool
were it not for the type class constraint "(Eq a) =>
".
Higherkinded polymorphism
A type class need not take a type variable of kind <math>*</math>, 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:
class Monad m where (>>=) :: m a > (a > m b) > m b return :: a > m a
The fact that m is applied to a type variable indicates that it has kind * > *, i.e. it takes a type and returns a type.
Multiparameter type classes
Type classes permit multiple type parameters, and so type classes can be seen as relations on types.^{[5]} 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^{[citation needed]}, multiparameter type classes support calling different implementations of a method depending on the types of multiple arguments, and indeed return types. They are more efficient than multimethods because they do not involve searching for the method to call on every call at runtime: the method to call is stored in the dictionary of the type class instance, just as with singleparameter type classes.
Haskell code that uses multiparameter type classes is not portable, as this feature is not part of the Haskell 98 standard. The popular Haskell implementations, GHC and Hugs, support multiparameter 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.^{[6]}^{[7]} 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, general monads m
which carry a state parameter of type s
satisfy the type class constraint MonadState s m
. In this constraint, there is a functional dependency m > s
. This means that for a given monad, the state type accessible from this interface is uniquely determined. This aids the compiler in type inference, as well as aiding the programmer in typedirected programming.
Simon PeytonJones has objected to the introduction of functional dependencies in Haskell on grounds of complexity.^{[8]}
Type class instances as implicit parameters
This section does not cite any references or sources. (January 2012) 
Implicit parameters used to implement type classes
Scala supports type classes whose instances or "dictionaries" are just ordinary values in the language, rather than a completely separate kind of entity.^{[9]} While these instances are by default supplied by finding appropriate instances in scope to be used as the implicit actual parameters for explicitlydeclared implicit formal parameters, the fact that they are ordinary values means that they can be supplied explicitly, to resolve ambiguity. This can be used to avoid issues such as incoherent and inconsistent instances that can occur when doing advanced Haskell development. Coq (version 8.2 onwards) also supports type classes by inferring the appropriate instances.^{[10]} Recent versions of Agda 2 also provide a similar feature, called "instance arguments".^{[11]}
Other approaches to operator overloading
In Standard ML, the mechanism of "equality types" corresponds roughly to Haskell's builtin type class Eq
, but all equality operators are derived automatically by the compiler. The programmer's control of the process is limited to designating which type components in a structure are equality types and which type variables in a polymorphic type range over equality types.
SML's and OCaml's modules and functors can play a role similar to that of Haskell's type classes, the principal difference being the role of type inference, which makes type classes suitable for ad hoc polymorphism.^{[12]} The object oriented subset of OCaml is yet another approach which is somewhat comparable to the one of type classes.
Related notions
An analogous notion for overloaded data (implemented in GHC) is that of type family.^{[13]}
See also
 Polymorphism (computer science) (other kinds of polymorphism)
 Haskell programming language (the language in which type classes were first designed)
 Operator overloading (one application of type classes)
 Monad (functional programming) (
Monad
is an example of a type class)  Concepts (C++) (a similar idea mooted, but not yet part of the language)
 Rust (programming language) (traits in Rust are very similar to type classes)
References
 ^ "Type classes, first proposed during the design of the Haskell programming language, ..." —John Garrett Morris (2013), "Type Classes and Instance Chains: A Relational Approach"
 ^ Kaes, Stefan (March 1988). "Parametric overloading in polymorphic programming languages". Proc. 2nd European Symposium on Programming Languages.
 ^ Wadler, Philip; Stephen Blott (January 1989). "How to make adhoc polymorphism less ad hoc". Proc. 16th ACM Symposium on Principles of Programming Languages.
 ^ Appel, Andrew; David MacQueen (June 1991). "Standard ML of New Jersey". Proc. 3rd International Symposium on Programming Language Implementation and Logic Programming.
 ^ Haskell' page MultiParamTypeClasses.
 ^ Mark Jones. Type Classes with Functional Dependencies. From Proc. 9th European Symposium on Programming. March, 2000.
 ^ Haskell' page FunctionalDependencies.
 ^ http://www.haskell.org//pipermail/haskellprime/2006February/000289.html
 ^ Oliveira, Bruno; Adriaan Moors; Martin Odersky (2010). "Type Classes as Objects and Implicits" (PDF). OOPSLA.
 ^ A Gentle Introduction to Type Classes and Relations in Coq
 ^ "Modelling Type Classes With Instance Arguments".
 ^ Dreyer, Derek; Robert Harper; Manuel M.T. Chakravarty (April 2006). "Modular Type Classes".
 ^ http://www.haskell.org/haskellwiki/GHC/Type_families
 Simon Peyton Jones, Mark Jones, Erik Meijer. Type classes: an exploration of the design space. From Proc. ACM SIGPLAN Haskell Workshop. May, 1997.
External links
 A Gentle Introduction to Haskell, Version 98, chapter 5. Type Classes and Overloading. June 2000.
 Advanced Functional Programming course at Utrecht University, 74 lecture slides on Advanced Type Classes. 20050607.
 Implementing, and Understanding Type Classes. [1]. 20141113.
