From Wikipedia, the free 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 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. Thus, type class constraints implement a form of bounded polymorphism.

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.^[1] Since then, many other applications of type classes have been discovered.

Contents 1 Overview 2 Higher-kinded polymorphism 3 Multi-parameter type classes 4 Other approaches to operator overloading 4.1 Standard ML 5 See also 6 References 7 External links

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. A 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 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, for each type a with the additional constraint that a is in Eq.

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, she may then make this new type an instance of Eq by providing an equality function over values of type t in whatever way she sees fit. Once she has done this, she may use the function member on lists of elements of type t.

Note that type classes are different from classes in object-oriented programming languages. In particular, Eq is not a type: there is no such thing as a value of type Eq. Thus the Haskell approach to a generic sorting function as outlined here is distinct from the subtyping-based approach used in object-oriented programming. 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) =>").

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.)

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 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 support multi-parameter type classes.

In Standard 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 modules and functors can play a role similar to that of Haskell's type classes, the principle difference being the role of type inference, which makes type classes suitable for ad hoc polymorphism.^[2]

• Polymorphism (computer science) (other kinds of polymorphism)
• Haskell programming language (the language in which type classes were designed)
• Operator overloading (one application of type classes)
• Monads in functional programming (Monad is an example of a type class)

1. ^ Wadler, Philip; Stephen Blott (January 1989). "How to make ad-hoc polymorphism less ad hoc". Proc. 16th ACM Symposium on Principles of Programming Languages. 
2. ^ Dreyer, Derek; Robert Harper; Manuel M.T. Chakravarty (January 2007). "Modular Type Classes". Proc. 34th ACM Symposium on Principles of Programming Languages. 

• Simon Peyton Jones, Mark Jones, Erik Meijer. Type classes: an exploration of the design space. From Proc. ACM SIGPLAN Haskell Workshop. May, 1997.
• Mark Jones. Type Classes with Functional Dependencies. From Proc. 9th European Symposium on Programming. March, 2000.
• Andrew Appel, David MacQueen. Standard ML of New Jersey. From Proc. 3rd International Symposium on Programming Language Implementation and Logic Programming. June, 1991.

• 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.
• The Haskell Wiki, page Type Classes, Dictionaries, and Type-based Dispatch.
• The Haskell Wiki, page Underestimated Type Classes