Type class

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.

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. class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool 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 * ( * is also known as Type in the latest Glasgow Haskell Compiler (GHC) release), meaning that the kind of Eq is Eq :: Type -> Constraint 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: elem :: Eq a => a -> [a] -> Bool elem y [] = False elem y (x:xs) = (x == y) || elem y xs 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 => ". class Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b 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: Monad :: (Type -> Type) -> Constraint sum :: Num a => [a] -> a can be intuitively treated as a function that implicitly accepts an instance of Num : sum_ :: Num_ a -> [a] -> a The instance Num_ a is essentially a record that contains the instance definition of Num 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 more flexible; different instances of Num Int can be passed. In contrast, type classes enforce the so-called coherence 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. As an example, an ordered set (of type Set a ) requires a total ordering on the elements (of type a ) to function. This can be evidenced by a constraint Ord 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 of Ord a to functions that operate on the set may lead to incorrect results (or crashes). Thus, enforcing coherence of Ord a in this particular scenario is crucial. Instances (or "dictionaries") in Scala type classes are just ordinary values in the language, rather than a completely separate kind of entity. 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 a syntactic sugar for implicit parameters. This is an example taken from the Cats documentation: // A type class to provide textual representation trait Show[A] { def show(f: A): String } // A polymorphic function that works only when there is an implicit // instance of Show[A] available def log[A](a: A)(implicit s: Show[A]) = println(s.show(a)) // An instance for String implicit val stringShow = new Show[String] { def show(s: String) = s } // The parameter stringShow was inserted by the compiler. scala> log("a string") a string Rocq (formerly named Coq), version 8.2 onward, also supports type classes by inferring the appropriate instances. Recent versions of Agda 2 also provide a similar feature, called "instance arguments". using std::convertible_to; // equivalent to std::equality_comparable template concept EqualityComparable = requires (T a, T b) { { a == b } -> convertible_to ; { a != b } -> convertible_to ; }; // using concept EqualityComparable: template nodiscard constexpr bool isEqual(const T& x, const T& y) noexcept { return x == y; } In Go, an interface can be seen as a type class, and is roughly equivalent to a C++ concept. In Java and C#, interfaces are similar to type classes, defining an "interface" of methods to implement (see Java interfaces). In Clean typeclasses are similar to Haskell, but have a slightly different syntax. Rust supports traits, which are a limited form of type classes with coherence, and can also be seen as similar to interfaces. Mercury has typeclasses, although they are not exactly the same as in Haskell. In Scala, type classes are a programming 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. The proof 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374871590 under CC BY-SA 4.0; modifications have been made.