Type Classes as Dictionary Passing and the Coherence Problem

A function constrained by Eq α is not a single function. It is a family of functions, one per type that has an equality test, and the compiler must choose which one to call at each use site. The mechanism that makes the choice is dictionary passing: constraints become extra parameters, instances become records of functions, and resolution becomes a search over a global table. The search is what gives the feature its power and what gives it its characteristic failure modes.

Constraints are parameters the programmer does not write

Consider a signature that sorts a list using an ordering on the element type: sort :: Ord a => [a] -> [a]. The Ord a part is not a type. It is a constraint, and the elaboration that lowers the program to a core language turns it into a parameter, so the elaborated signature is sort :: OrdDict a -> [a] -> [a].

An OrdDict a is a record with a field for the comparison function and, because Ord has Eq as a superclass, a field holding the Eq dictionary:

data OrdDict a = OrdDict
  { cmp  :: a -> a -> Ordering
  , eqDict :: EqDict a
  }

data EqDict a = EqDict
  { eq :: a -> a -> Bool
  }

Every call to sort receives the dictionary as an ordinary argument. Every instance declaration becomes a value of the dictionary type. Resolution — deciding which dictionary to pass — happens entirely at compile time, so the run-time cost of a constrained function is one extra pointer-sized argument per constraint, and every operation called through the dictionary is an indirect call that the compiler can inline only when it can see the dictionary at the call site.

This is a type-passing translation only in the shallow sense: the dictionary carries operations, not type representations. A function polymorphic in a with no constraints receives no dictionary and cannot inspect a at all. That is the same erasure described in erasure and reification of generic types, and it is why a constrained function can do more than an unconstrained one without any run-time type information. The difference from monomorphization is that the constrained function’s body is compiled once rather than once per type, which is the trade examined in that article.

Resolution is a logic program over instances

Instance declarations form a set of Horn-like clauses. A declaration instance Eq a => Eq [a] says that Eq [a] holds if Eq a holds. Resolution of a goal Eq [Int] matches the head of the clause, producing the subgoal Eq Int, which matches a base instance. The search is depth-first with backtracking in principle, but production compilers do not backtrack: the instance set is required to be non-overlapping so that at most one clause matches any goal, which turns the search into a deterministic walk.

The non-overlap requirement is enforced by a consistency check on instance heads. Two instances overlap when their heads unify after renaming variables. Eq [a] and Eq [Int] overlap, because the first subsumes the second, and a compiler rejects the pair unless the language supports overlapping instances with an explicit ordering pragma. Eq [a] and Eq (Maybe a) do not overlap, because no substitution makes the heads identical.

The check is not merely hygiene. If two instances matched the same goal, the dictionary chosen would depend on which clause the resolver tried first, and the program’s behaviour would depend on declaration order or module import order. That is the coherence problem, and non-overlap is the static guarantee that avoids it.

Coherence and its two readings

Coherence is the property that a program’s meaning does not depend on how the type checker resolves constraints. Formally: if a term is well typed under two different resolutions, the two elaborated terms behave identically. There are two ways to get it.

Static coherence is the guarantee that at most one resolution exists. Non-overlapping instances give this for ground types. For a goal containing a type variable — Eq a inside a function polymorphic in a — no instance matches at all, so the constraint must be discharged by being passed in as a dictionary parameter. The rule that enforces this is that instance resolution never instantiates a type variable in the goal; a goal is only solved when its head is concrete enough to match exactly one instance.

Dynamic coherence is a fallback in languages that permit overlapping instances or type-directed dispatch at run time. The resolution is deterministic but may depend on the runtime type of a value, which means two call sites with the same static type can receive different dictionaries. This is how type-directed multiple dispatch works, and it is coherent only if the dispatch order is specified independently of the program’s structure.

The practical difference appears at module boundaries. Static coherence is a whole-program property: a new instance added in a module that another module imports can change the resolution of a goal in that module, and the change may not be visible from the module’s own source. Languages that take coherence seriously therefore either forbid the situation or make conflicting instances a compile- or link-time error rather than a silent change of meaning.

Orphan instances and the transitivity problem

The rule that prevents most coherence violations is the orphan restriction: an instance may be declared only in the module that defines the class or the module that defines the type. An instance for a class and type that both come from elsewhere is an orphan, and it is rejected or warned about.

The restriction exists because instance resolution is transitive. If module A declares Eq T and module B imports A and uses it, then B’s behaviour depends on A’s instance. If C also declares Eq T — legally, since C might not import A — then a program importing both B and C has two instances for the same goal and no way to choose. The orphan restriction makes this impossible by requiring the instance to live where the type is defined, so any two modules that could see the instance see the same one.

The cost is real. A user who wants a class instance for a type from a library cannot add it without editing the library or wrapping the type in a newtype. The newtype wrapper is the standard answer: it is a distinct type, defined in the user’s module, so an instance for it is not an orphan, and the wrapper costs nothing at run time because the compiler gives it the representation of the type it wraps. The price is paid in source: every function that crosses between the wrapper and its underlying type needs an explicit wrapping or unwrapping, and the wrapper does not inherit the instances of the type inside it — instances are keyed by the head type, and the head type is now the wrapper.

Newtype derivation has a second cost: the compiler must know that the wrapper has the same representation, which requires the wrapper to be declared as a newtype rather than a data type. A data declaration with one field allocates; a newtype does not. The distinction is observable in allocation behaviour and is the reason the two declarations exist separately rather than as one feature with an optimization.

Superclasses, and why dictionaries nest

A superclass constraint means that any dictionary for the subclass contains a dictionary for the superclass. Ord contains Eq; Monad contains Applicative contains Functor. The nesting is static and total: resolving Ord a yields a record whose eqDict field is the Eq dictionary, so a function needing only Eq can be called from one that has Ord by projecting the field. This is the same containment that the subtype relation expresses for records, described in structural subtyping and variance, with the difference that dictionary projection is a field access on a value that exists at run time.

The projection is free at run time — it reads a pointer at a fixed offset — but it has a compile-time cost that is easy to underestimate. A deep superclass chain means every dictionary type contains the dictionaries of the whole chain, and every instance must construct all the nested dictionaries. For a class with k superclasses transitively, each dictionary value holds k nested dictionaries, and the chain is traversed once per projection at compile time. Compilers may instead pass superclass dictionaries as separate arguments rather than nesting, which flattens the structure at the cost of a wider calling convention.

Superclasses also constrain what an instance can be. If Ord requires Eq, an instance Ord T must be accompanied by Eq T, and the compiler checks the superclass goal at the instance site. That check is itself a resolution, so it can fail for the same reasons any resolution fails — a missing instance, an ambiguous variable, an orphan.

Ambiguity, defaulting, and the limits of inference

A constraint whose type variable appears nowhere in the function’s type cannot be resolved by the caller. A function with type Show a => String has a constraint on a variable that no argument or result mentions, so at a call site the compiler must pick a type for a with no information. The constraint is ambiguous, and the language must either reject it or apply a default.

Defaulting rules exist for exactly this case: numeric literals are the common instance, where fromInteger has type Integer -> a and a literal’s type variable may remain unconstrained. A defaulting declaration maps a class to a list of types tried in order, and the compiler picks the first whose instance exists. Defaulting is a deliberate unsoundness in the sense that it changes the program’s meaning based on which instances happen to be in scope — but it is a specified unsoundness, confined to a fixed set of classes, and the alternative is that every numeric literal needs an annotation.

Ambiguity is the reason constraint solving is not simply unification. Unification asks “can these two types be made equal”; resolution asks “does an instance exist for this goal”, and a goal containing variables has no answer until the variables are fixed. The solver therefore interleaves the two: it simplifies constraints as types become known, defers the rest, and reports the residual set at the end of the binding. A residual constraint that mentions a variable appearing in the binding’s type can be discharged by the caller and becomes an extra dictionary parameter; one that mentions no such variable cannot, and is an error or a candidate for defaulting.

Dictionary-passing versus vtable dispatch

The obvious comparison is with object-oriented dynamic dispatch, which also passes a table of functions. The differences are in when the choice is made and what it can depend on.

A vtable is selected by the runtime class of the receiver, so the choice can depend on a value’s dynamic type, and adding a subclass does not require recompiling callers. A dictionary is selected at compile time from the static type, so the choice cannot depend on a value, and adding an instance can change the resolution of goals in other modules, which means those modules must be compiled against the new instance set.

In exchange, dictionary passing supports constraints on types that have no values — a constraint on a phantom parameter, on a type-level list, or on a function type. It also supports multi-parameter classes, where the dictionary is selected by a tuple of types, and functional dependencies, where one parameter determines another and the resolver can use that determination to fix a variable that would otherwise be ambiguous. A vtable has no analogue for either, because it dispatches on one receiver and nothing else.