Type class
Encyclopedia
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
Type classes first appeared in the Haskell programming language
, 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 require extensive modification of the compiler frontend or the underlying type system.
Since their creation, many other applications of type classes have been discovered.
class Eq a where
() :: a -> a -> Bool
), and
member :: (Eq a) => a -> [a] -> Bool
member y [] = False
member y (x:xs) = (x y) || member y xs
The function
A programmer can make any type
Note that type classes are different from classes
in object-oriented programming languages. In particular,
Type classes are closely related to parametric polymorphism. For example, note that the type of
Higher-kinded polymorphism
A type class need not take a type variable of kind
*, 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.
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
array types, for example.)
Not only do type classes permit multiple type parameters, they also permit functional dependencies between those type parameters. 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
Haskell code that uses multi-parameter type classes is not portable, as this feature is not part of the Haskell 98 standard. The popular Haskell implementations GHC and Hugs
support multi-parameter type classes.
Other approaches to operator overloading
In Standard ML
, the mechanism of "equality types" corresponds roughly to Haskell's built-in type class
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.
See also
External links
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a type class is a type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
construct that supports ad-hoc polymorphism
Ad-hoc polymorphism
In programming languages, ad-hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument to...
. This is achieved by adding constraints to type variables in parametrically polymorphic
Parametric polymorphism
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...
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
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
, 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
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the 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.
Since their creation, many other applications of type classes have been discovered.
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 classEq 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 class Eq if there are functions named (
), and (/=), of the appropriate types, defined on it." (Note: Haskell's 'maps-to' operator, -> , is 'right associative'. In other words, a -> a -> Bool is read as a -> (a -> Bool).) 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 class. (Note: Haskell => can be called a 'class constraint'.)A programmer can make any type
t a member of a given 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 lists of elements of type t.Note that type classes are different from classes
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
in object-oriented 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) =>".Higher-kinded polymorphism
A type class need not take a type variable of kind
Kind (type theory)
In the area of mathematical logic and computer science known as type theory, a kind is the type of a type constructor or, less commonly, the type of a higher-order type operator...
*, 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.
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
Glasgow Haskell Compiler
The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...
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 unboxedUnboxing
Unboxing is the unpacking of new products, especially hi-tech consumer products. The whole process is captured on video and later uploaded to the Internet. The term has been labeled a new form of "geek porn."...
array types, for example.)
Not only do type classes permit multiple type parameters, they also permit functional dependencies between those type parameters. 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
Monads in functional programming
In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model...
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 type-directed programming.Haskell code that uses multi-parameter type classes is not portable, as this feature is not part of the Haskell 98 standard. The popular Haskell implementations GHC and Hugs
Hugs
Hugs , also Hugs 98, is a bytecode interpreter for the functional programming language Haskell. Hugs is the successor to Gofer, and was originally derived from Gofer version 2.30b. Hugs and Gofer were originally developed by Mark P. Jones, now a professor at Portland State University.Hugs comes...
support multi-parameter type classes.
Other approaches to operator overloading
In Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...
, the mechanism of "equality types" corresponds roughly to Haskell's built-in 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.
See also
- Polymorphism (computer science) (other kinds of polymorphism)
- Haskell programming languageHaskell (programming language)Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
(the language in which type classes were first designed) - Operator overloadingOperator overloadingIn object oriented computer programming, operator overloading—less commonly known as operator ad-hoc polymorphism—is a specific case of polymorphism, where different operators have different implementations depending on their arguments...
(one application of type classes) - Monads in functional programmingMonads in functional programmingIn functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model...
(Monadis an example of a type class) - C++0x conceptsConcepts (C++)Concepts and the related notion of axioms were an extension to C++'s template system proposed for C++0x. They were designed to improve compiler diagnostics and to allow programmers to codify in the program some formal properties of templates that they write...
(a similar idea mooted, but not yet part of the language)
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. 2005-06-07.