Type Classes and Ad-Hoc Polymorphism

There are two very different ways a function can work at many types. Parametric polymorphism — the \forall X of generics — runs the same code for every type: length counts a list's elements without ever looking at what they are. Ad-hoc polymorphism — overloading — runs different code depending on the type: + on integers is machine addition, on strings is concatenation, on matrices is something else again. Ad-hoc polymorphism is what lets one symbol mean the right thing everywhere, and for decades it was handled by messy, untyped, compiler-magic overloading rules.

Type classes (Wadler & Blott, 1989) made ad-hoc polymorphism principled. A class is a named interface of overloaded operations; an instance supplies that interface for a particular type; and a function may carry constraints — "\mathsf{Eq}\,a \Rightarrow \dots", read "provided a is an equality type" — that the compiler must discharge. The beautiful part is the implementation: type classes desugar completely into ordinary records passed as hidden arguments, by the dictionary-passing translation. No magic — just a systematic elaboration into a language we already understand.

Classes, instances, constraints

A class declaration names an overloaded interface. A class constraint \Rightarrow appears in a type to demand that interface. An instance provides it for one type.

class Eq a where -- the interface eq :: a -> a -> Bool instance Eq Int where eq = primEqInt -- provide it for Int instance Eq Bool where eq = primEqBool -- provide it for Bool instance Eq a => Eq [a] where -- provide it for lists, GIVEN Eq a eq xs ys = length xs == length ys && and (zipWith eq xs ys) member :: Eq a => a -> [a] -> Bool -- a CONSTRAINED (qualified) type member x = any (eq x)

The type of member is a qualified type: the part before \Rightarrow is a context of constraints, the part after is an ordinary type. Read it as a promise the caller must keep:

\mathsf{member} \;:\; \forall a.\ \underbrace{\mathsf{Eq}\,a}_{\text{constraint}} \;\Rightarrow\; a \to [a] \to \mathsf{Bool}.

Note the last instance is itself conditional: \mathsf{Eq}\,a \Rightarrow \mathsf{Eq}\,[a] — you get equality on lists provided you have equality on elements. Instance resolution is therefore a small logic program; the compiler searches instances like Prolog clauses to discharge each constraint.

The dictionary-passing translation

Here is how the compiler makes it all real, with no run-time type inspection whatsoever. Each class becomes a record type — a dictionary holding its methods. Each instance becomes a dictionary value. Each constraint C\,a \Rightarrow \tau becomes an extra argument of type \mathsf{Dict}_C\,a. A call site supplies the right dictionary; a conditional instance is a function from dictionaries to dictionaries.

So the qualified type elaborates by turning every \Rightarrow into a \to:

\underbrace{\forall a.\ \mathsf{Eq}\,a \Rightarrow a \to [a] \to \mathsf{Bool}}_{\text{source, qualified type}} \;\;\rightsquigarrow\;\; \underbrace{\forall a.\ \mathsf{EqDict}\,a \to a \to [a] \to \mathsf{Bool}}_{\text{target, ordinary type}}.

The constraint became a plain parameter. Everything a type class does is captured by this one move — which is exactly why type classes are "just" a disciplined, type-directed, automatically-inserted form of passing an interface record. The programmer writes eq x y; the compiler rewrites it to dict.eq(x, y), having threaded dict in for them.

Run the translation by hand

Below is the dictionary translation done explicitly in TypeScript: dictionaries are records, instances are values, the conditional \mathsf{Eq}\,a \Rightarrow \mathsf{Eq}\,[a] instance is a function of dictionaries, and every constrained function takes its dictionary first. This is precisely the code a Haskell compiler generates.

// class Eq a ==> the dictionary type (a record of the class's methods). type Eq<A> = { eq: (x: A, y: A) => boolean }; // instance Eq number ; instance Eq string ==> dictionary VALUES. const eqNumber: Eq<number> = { eq: (x, y) => x === y }; const eqString: Eq<string> = { eq: (x, y) => x === y }; // instance (Eq a) => Eq (a[]) ==> a FUNCTION from the element dict to the list dict. const eqArray = <A>(d: Eq<A>): Eq<A[]> => ({ eq: (xs, ys) => xs.length === ys.length && xs.every((x, i) => d.eq(x, ys[i])), }); // member :: Eq a => a -> [a] -> Bool ==> dictionary threaded in as the first argument. function member<A>(dEq: Eq<A>, x: A, xs: A[]): boolean { return xs.some((y) => dEq.eq(x, y)); // "eq x y" becomes "dEq.eq(x, y)" } console.log("member 3 [1,2,3] =", member(eqNumber, 3, [1, 2, 3])); // true console.log("member 'z' ['a','b'] =", member(eqString, "z", ["a", "b"])); // false // The conditional instance builds a list-dictionary from the number-dictionary: const eqNumList = eqArray(eqNumber); console.log("[1,2,3] == [1,2,3] =", eqNumList.eq([1, 2, 3], [1, 2, 3])); // true console.log("[1,2] == [1,2,3] =", eqNumList.eq([1, 2], [1, 2, 3])); // false

eqArray(eqNumber) is instance resolution made concrete: to compare two number[]s the compiler needed \mathsf{Eq}\,[\mathsf{number}], so it applied the \mathsf{Eq}\,a\Rightarrow\mathsf{Eq}\,[a] instance to the \mathsf{Eq}\,\mathsf{number} dictionary. A whole tree of constraints becomes a tree of dictionary constructions — computed once, at compile time.

Ad-hoc vs parametric, and dispatch on the result

Because dispatch is by type, not by a runtime value, type classes can do something ordinary object-oriented method dispatch cannot: choose the instance from the result type. Haskell's read :: Read a => String -> a parses into whatever type the context demands; mempty :: Monoid a => a and fromInteger :: Num a => Integer -> a conjure a value of a type that appears nowhere in the arguments. In dictionary terms this is trivial — the dictionary for the result type is simply threaded in — but it is impossible for a this-receiver dispatch that needs an object in hand to pick the method.

Ask an object-oriented programmer to dispatch parse("42") to an Int parser or a Bool parser and they are stuck: there is no receiver object yet to look a method up on — the value is what we are trying to create. Type classes shrug. Because the instance is selected by the static type and delivered as a dictionary argument, the compiler reads the expected result type from context — let n :: Int = read "42" — and passes the Read Int dictionary. This "return-type polymorphism" underlies fromInteger (so the literal 5 can be an Int, a Double, or a Complex depending on use), minBound, mempty, and the whole numeric tower. It is the clearest single demonstration that type-class dispatch is fundamentally different from — and strictly more expressive than — the vtable dispatch of objects.

A type class carries a hidden, load-bearing promise: for any given class and type there is at most one instance in the entire program — global uniqueness, or coherence. It matters because a data structure can bake a dictionary into itself: a Set ordered by one Ord Int instance would silently corrupt if another part of the program compared its elements by a different one. That is why Haskell forbids two instance Eq Ints, and why orphan instances (an instance defined in neither the class's module nor the type's) are discouraged — they let two libraries each define an instance for a third party's type, and now which one you get depends on imports, breaking coherence. Contrast Scala's implicit/given parameters, which are just dictionary passing but without the global-uniqueness rule: more flexible (locally scoped instances) at the cost that two modules can disagree on "the" Ordering for a type. Coherence is the price of, and the guarantee behind, the type class's magic.