Incomputer science, atype class is atype system construct that supportsad hoc polymorphism in aprogramming language. This is achieved by adding constraints to type variables inparametrically polymorphic types. Such a constraint typically involves a type classT and atype variablea, and means thata can only be instantiated to a type whose members support the overloaded operations associated withT.
Type classes were first implemented in the languageHaskell after first being proposed byPhilip Wadler andStephen Blott as an extension toeqtypes inStandard ML,[1][2] and were originally conceived as a way of implementingoverloaded arithmetic and equality operators in a principled fashion.[3][2]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 thecompiler frontend or the underlying type system.[4]
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 classEq intended to contain types that admit equality would be declared in the following way:
classEqawhere(==)::a->a->Bool(/=)::a->a->Bool
wherea is one instance of the type classEq, anda defines the function signatures for 2 functions (the equality and inequality functions), which each take 2 arguments of typea and return a Boolean.
The type variablea haskind ( is also known asType in the latestGlasgow Haskell Compiler (GHC) release),[5] meaning that the kind ofEq is
Eq::Type->Constraint
The declaration may be read as stating a "typea belongs to type classEq if there are functions named(==), and(/=), of the appropriate types, defined on it". A programmer could then define a functionelem (which determines if an element is in a list) in the following way:
elem::Eqa=>a->[a]->Boolelemy[]=Falseelemy(x:xs)=(x==y)||elemyxs
The functionelem has the typea -> [a] -> Bool with the contextEq a, which constrains the types whicha can range over to thosea which belong to theEq type class. (Haskell=> can be called a 'class constraint'.)
Any typet can be made a member of a given type classC by using aninstance declaration that defines implementations of all ofC's methods for the given typet. For example, if a new data typet is defined, this new type can be made an instance ofEq by providing an equality function over values of typet in any way that is useful. Once this is done, the functionelem can be used on[t], that is, lists of elements of typet.
Type classes are different fromclasses inobject-oriented programming languages. Specifically,Eq is not a type: there is no such thing as avalue of typeEq.
Type classes are closely related toparametric polymorphism. For example, the type ofelem as specified above would be the parametrically polymorphic typea -> [a] -> Bool were it not for the type class constraint "Eq a =>".
A type class need not take a type variable ofkindType 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 asMaybe, rather than data constructors such asJust). An example is theMonad class:
classMonadmwherereturn::a->ma(>>=)::ma->(a->mb)->mb
Thatm is applied to a type variable indicates that it has kindType -> Type, i.e., it takes a type and returns a type, the kind ofMonad is thus:
Monad::(Type->Type)->Constraint
Type classes permit multiple type parameters, and so type classes can be seen as relations on types.[6] For example, in theGHCstandard library, the classIArray expresses a general immutable array interface. In this class, the type class constraintIArray a e means thata is an array type that contains elements of typee. (This restriction on polymorphism is used to implementunboxed array types, for example.)
Likemultimethods,[citation needed] 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;[7]: minute 25:12 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 andHugs, support multi-parameter type classes.
In Haskell, type classes have been refined to allow the programmer to declare functional dependencies between type parameters—a conceptinspired from relational database theory.[8][9] 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 generalmonadm which carries a state parameter of types satisfies the type class constraintMonad.State s m. In this constraint, there is a functional dependencym -> s. This means that for a given monadm of type classMonad.State, the state type accessible fromm is uniquely determined. This aids the compiler intype inference, as well as aiding the programmer intype-directed programming.
Simon Peyton Jones has objected to the introduction of functional dependencies in Haskell on grounds of complexity.[10]
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:
sum::Numa=>[a]->a
can be intuitively treated as a function that implicitly accepts an instance ofNum:
sum_::Num_a->[a]->a
The instanceNum_ a is essentially a record that contains the instance definition ofNum a. (This is in fact how type classes are implemented under the hood by the Glasgow Haskell Compiler.)
However, there is a crucial difference: implicit parameters are moreflexible; different instances ofNum Int can be passed. In contrast, type classes enforce the so-calledcoherence property, which requires that there should only be one unique choice of instance for any given type. The coherence property makes type classes somewhat antimodular, which is why orphan instances (instances that are defined in a module that neither contains the class nor the type of interest) are strongly discouraged. However, coherence adds another level of safety to a language, providing a guarantee that two disjoint parts of the same code will share the same instance.[11]
As an example, an orderedset (of typeSet a) requires atotal ordering on the elements (of typea) to function. This can be evidenced by a constraintOrd a, which defines a comparison operator on the elements. However, there can be numerous ways to impose a total order. Since set algorithms are generally intolerant of changes in the ordering once a set has been constructed, passing an incompatible instance ofOrd a to functions that operate on the set may lead to incorrect results (or crashes). Thus, enforcing coherence ofOrd a in this particular scenario is crucial.
Instances (or "dictionaries") inScala type classes are just ordinary values in the language, rather than a completely separate kind of entity.[12][13] While these instances are by default supplied by finding appropriate instances in scope to be used as the implicit parameters for explicitly-declared implicit formal parameters, that they are ordinary values means that they can be supplied explicitly, to resolve ambiguity. As a result, Scala type classes do not satisfy the coherence property and are effectively asyntactic sugar for implicit parameters.
This is an example taken from the Cats documentation:[14]
// A type class to provide textual representationtraitShow[A]{defshow(f:A):String}// A polymorphic function that works only when there is an implicit// instance of Show[A] availabledeflog[A](a:A)(implicits:Show[A])=println(s.show(a))// An instance for StringimplicitvalstringShow=newShow[String]{defshow(s:String)=s}// The parameter stringShow was inserted by the compiler.scala>log("a string")astring
Rocq (formerly namedCoq), version 8.2 onward, also supports type classes by inferring the appropriate instances.[15] Recent versions ofAgda 2 also provide a similar feature, called "instance arguments".[16]
InStandard ML, the mechanism of "equality types" corresponds roughly to Haskell's built-in type classEq, 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 andOCaml'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 forad hoc polymorphism.[17]The object oriented subset ofOCaml is yet another approach which is somewhat comparable to the one of type classes.
An analogous notion for overloaded data (implemented inGHC) is that oftype family.[18]
InC++, notablyC++20, has support for type classes using "concepts". As an illustration, the above mentioned Haskell example of typeclassEq would be written as
usingstd::convertible_to;template<typenameT>conceptEqual=requires(Ta,Tb){{a==b}->convertible_to<bool>;{a!=b}->convertible_to<bool>;};// using concept Equal:template<EqualT>[[nodiscard]]constexprboolisEqual(constT&x,constT&y)noexcept{returnx==y;}
InClean typeclasses are similar to Haskell, but have a slightly differentsyntax.
Rust supportstraits, which are a limited form of type classes with coherence, and can also be seen as similar tointerfaces.[19]
Mercury has typeclasses, although they are not exactly the same as in Haskell.[further explanation needed]
InScala, type classes are aprogramming idiom that can be implemented with existing language features such as implicit parameters, not a separate language feature per se. Because of the way they are implemented in Scala, it is possible to explicitly specify which type class instance to use for a type at a particular place in the code, in case of ambiguity. However, this is not necessarily a benefit as ambiguous type class instances can be error-prone.
Theproof assistant Rocq has also supported type classes in recent versions. Unlike in ordinary programming languages, in Rocq, any laws of a type class (such as the monad laws) that are stated within the type class definition, must be mathematically proved of each type class instance before using them.
Type fromData.Kind appeared in version 8 of the Glasgow Haskell Compiler".