Haskell 7: Type Classes and Dictionary Passing

Part 7 of Haskell from First Principles.

Load complete definitions from a .hs file and try expressions in GHCi. Signatures of existing Prelude methods explain their types; they are not new declarations to paste into a module. Treat alternative data declarations and instance implementations as separate examples.

Higher-order functions let us pass operations such as predicates and transformations into reusable code. Type classes let us ask for a family of operations through a type constraint instead.

Consider:

square :: Num a => a -> a
square x = x * x

What does Num a => mean? How does multiplication choose the operation for Int, Double, or another numeric type? We will answer this by defining classes and instances, then turning their implicit arguments into explicit records of functions.

7.1 Two kinds of polymorphism

An unconstrained polymorphic function can work without knowing a particular representation or operation for its argument type:

identity :: a -> a
identity x = x
 
-- Examples:
-- identity (5 :: Int)  == 5
-- identity True       == True
-- identity "hello"    == "hello"

This is parametric polymorphism. The same definition works uniformly across types. In particular, its signature grants no addition or equality operation for a.

Now compare:

double :: Num a => a -> a
double x = x + x
 
-- double (3 :: Int)       -- 6
-- double (3.5 :: Double)  -- 7.0

double needs addition. Its constraint says that a must have a Num instance, which supplies numeric operations. This is constrained polymorphism; type classes support a form of ad-hoc polymorphism, because different instances can implement the same operation differently.

Parametric polymorphism	Type-class polymorphism
identity :: a -> a	double :: Num a => a -> a
Requires no class operations	Requires numeric operations for a
Cannot assume + is available	Can use Num methods such as + and *
Uses one uniform implementation	Uses operations supplied by an instance

A type class describes operations that a type can support. A constraint requires those operations for a particular type.

7.2 Reading a class declaration

The standard Eq class provides equality. A simplified declaration is:

-- Illustration of the existing Prelude class; do not redeclare it.
class Eq a where
  (==) :: a -> a -> Bool

Fragment	Meaning
class	Introduce a class
Eq	Name of the class
a	Type parameter
where	Begin its methods and optional defaults
(==) :: a -> a -> Bool	An equality method for two values of the same type

Outside the class declaration, the method has a qualified type:

(==) :: Eq a => a -> a -> Bool

The constraint is supplied by the surrounding class declaration when we write the method signature inside it. At a use site, it says that comparing two values requires the appropriate Eq operations.

(3 :: Int) == 3   -- True
True == False    -- False
"abc" == "abc"   -- True

These expressions use different instances of the same class.

7.3 Defining instances with instance

Define a type whose values describe a traffic signal:

data Traffic = Stop | Caution | Go
  deriving (Show)
 
instance Eq Traffic where
  Stop    == Stop    = True
  Caution == Caution = True
  Go      == Go      = True
  _       == _       = False

instance Eq Traffic where declares how the equality operations work for Traffic. Each equation is an ordinary function equation, written with an infix method name.

Stop == Stop    -- True
Stop == Go      -- False
Go == Caution   -- False

The full Eq interface also includes inequality, /=. Its defaults relate the two methods:

-- Conceptual presentation of the existing class.
class Eq a where
  (==), (/=) :: a -> a -> Bool
 
  x /= y = not (x == y)
  x == y = not (x /= y)

Implementing either method is sufficient; the other gets its default. Implementing neither leaves the two defaults calling one another indefinitely. This is an example of a minimal complete definition: the smallest set of methods an instance must provide. The official Eq documentation lists (==) or (/=) as that minimum.

Our instance supplies (==), so it also supports:

Stop /= Go    -- True
Stop /= Stop  -- False

7.4 Creating a class of our own

Suppose several types should support a human-readable description:

class Render a where
  render :: a -> String
 
instance Render Traffic where
  render Stop    = "Stop the vehicle"
  render Caution = "Proceed carefully"
  render Go      = "You may proceed"
 
instance Render Int where
  render x = "Integer: " ++ show x

Now the same method name works at different types:

render Stop          -- "Stop the vehicle"
render Go            -- "You may proceed"
render (42 :: Int)   -- "Integer: 42"

Its overall type is:

render :: Render a => a -> String

For render Go, the argument type determines that we need Render Traffic. For render (42 :: Int), we need Render Int. This instance resolution is based on types; Haskell does not inspect the runtime value 42 to discover a rendering implementation.

Type classes resemble interfaces or traits in other languages, but the data declaration and its instance declarations are separate. We do not put Render inside the definition of Traffic. In the ordinary instances used here, implementations are associated with types, rather than being overridden independently on individual objects. More advanced instance-selection extensions are outside this series’s current scope.

7.5 How constraints propagate

Operations in a function body impose requirements on its type:

same :: Eq a => a -> a -> Bool
same x y = x == y

The two arguments must have the same type, and that type must support equality.

same (3 :: Int) 3  -- True
same True False   -- False
same Stop Go      -- False

There is no standard Eq instance for arbitrary functions, so this expression is rejected:

-- Does not type-check:
-- (\x -> x + 1) == (\x -> x + 1)

A function can need several classes:

isZero :: (Eq a, Num a) => a -> Bool
isZero x = x == 0

(==) requires Eq a; the overloaded integer literal 0 requires Num a. These requirements are separate. Similarly:

showIfEqual :: (Eq a, Show a) => a -> a -> String
showIfEqual x y =
  if x == y
  then show x
  else "Not equal"

Here equality requires Eq a, while converting the result to text requires Show a. The constraint does not add a visible value argument in source syntax, but Section 7.8 will show how it corresponds to an implicit implementation argument.

7.6 Superclasses: one class can require another

The ordering class begins conceptually as follows:

-- Illustration of the existing Prelude class.
class Eq a => Ord a where
  compare :: a -> a -> Ordering

Eq a is a superclass constraint: every Ord a instance must also have Eq a. Ord provides compare and operators such as <, <=, >, and >=.

The standard Ordering type has three constructors:

-- Already defined by the Prelude:
-- data Ordering = LT | EQ | GT
 
compare (3 :: Int) 5  -- LT
compare (5 :: Int) 5  -- EQ
compare (7 :: Int) 5  -- GT

Because Ord a entails Eq a, this function needs only one explicit constraint:

compareAndCheck :: Ord a => a -> a -> Bool
compareAndCheck x y = x < y || x == y

Writing (Eq a, Ord a) would be redundant. By contrast, Num a does not imply Ord a: arithmetic and ordering are separate capabilities.

7.7 Generic instances for parameterized types

We can provide an instance for a family of types:

data Box a = Box a
  deriving (Show)
 
instance Eq a => Eq (Box a) where
  Box x == Box y = x == y

Read the instance declaration as: if a supports equality, then Box a supports equality.

Box (3 :: Int) == Box 3  -- True
Box True == Box False   -- False

To check Eq (Box Int), the compiler uses the instance rule for Box a, substitutes Int for a, and then needs Eq Int:

Required evidence	How to obtain it
Eq (Box Int)	Apply the generic Box instance
Eq Int	Use the existing integer instance

Haskell’s list equality follows a similar recursive pattern:

-- Illustration of the existing instance; do not redefine it.
instance Eq a => Eq [a] where
  [] == [] = True
  (x:xs) == (y:ys) = x == y && xs == ys
  _ == _ = False

Two lists are equal when they have the same length and corresponding elements are equal. The list instance reuses the element instance:

([1,2,3] :: [Int]) == [1,2,3]  -- True
[True,False] == [True,True]     -- False

7.8 Dictionary passing, from first principles

How can same call equality when its element type is still abstract? Begin with ordinary higher-order programming:

sameWith :: (a -> a -> Bool) -> a -> a -> Bool
sameWith eq x y = eq x y

The caller supplies an equality operation explicitly:

sameWith (==) (3 :: Int) 3  -- True
sameWith (==) True False   -- False

sameWith does not discover how to compare anything. It receives a function that already knows how.

Package several methods into a record

A class can have many methods, so passing them individually becomes awkward. Package them in an ordinary record:

data EqDict a = EqDict
  { eqMethod  :: a -> a -> Bool
  , neqMethod :: a -> a -> Bool
  }
 
intEqDict :: EqDict Int
intEqDict = EqDict
  { eqMethod  = (==)
  , neqMethod = (/=)
  }
 
boolEqDict :: EqDict Bool
boolEqDict = EqDict
  { eqMethod  = (==)
  , neqMethod = (/=)
  }

These are ordinary, illustrative Haskell values. The signatures select the existing Int and Bool methods when we construct them.

Record	eqMethod field	neqMethod field
EqDict Int	Integer equality	Integer inequality
EqDict Bool	Boolean equality	Boolean inequality

The name dictionary describes this association between class methods and their implementations. It does not mean a runtime hash table with string keys such as "==". The record has a statically known layout and typed fields. Selecting eqMethod means selecting a known field, rather than searching a map of method names.

Make the hidden argument visible

Rewrite same with an explicit dictionary:

sameExplicit :: EqDict a -> a -> a -> Bool
sameExplicit dict x y = eqMethod dict x y
 
-- sameExplicit intEqDict 3 3         -- True
-- sameExplicit boolEqDict True False -- False

Compare the two interfaces:

same         :: Eq a => a -> a -> Bool
sameExplicit :: EqDict a -> a -> a -> Bool

The constraint represents a requirement for evidence that equality operations exist. A dictionary supplies that evidence by carrying the operations. Dictionary passing is the compiler’s way of making this evidence available as an implicit argument.

At a concrete call site:

same (3 :: Int) 5

the conceptual elaboration is:

sameExplicit intEqDict 3 5

Distinguish two activities:

1. Instance resolution determines how to obtain evidence for Eq Int.
2. Dictionary passing supplies that evidence to the function using it.

The compiler does not need to inspect the runtime value 3 to choose an instance. A dictionary and its method calls may still exist at runtime; static instance resolution does not mean every overloaded call is necessarily compiled into a direct call.

Forward evidence through polymorphic calls

What if the caller is also polymorphic?

sameTwice :: Eq a => a -> a -> Bool
sameTwice x y = same x y && same y x

It can forward the dictionary it received:

sameTwiceExplicit :: EqDict a -> a -> a -> Bool
sameTwiceExplicit dict x y =
  sameExplicit dict x y && sameExplicit dict y x

Neither function must know whether a is Int, Bool, or Traffic. Both calls use the same supplied operations. This is what makes the mechanism work compositionally across layers of generic functions.

Build a dictionary from another dictionary

The constrained instance from Section 7.7 can be represented by a dictionary-building function:

boxEqDict :: EqDict a -> EqDict (Box a)
boxEqDict dict = EqDict
  { eqMethod = \(Box x) (Box y) -> eqMethod dict x y
  , neqMethod = \(Box x) (Box y) -> neqMethod dict x y
  }

Its type mirrors the instance context:

-- Instance rule:
-- Eq a => Eq (Box a)
 
-- Explicit evidence construction:
boxEqDict :: EqDict a -> EqDict (Box a)

Thus comparing two integer boxes becomes conceptually:

sameExplicit (boxEqDict intEqDict) (Box 3) (Box 5)
-- False

A constrained instance is a rule for constructing evidence from other evidence. The compiler can build nested evidence using the same rule: an equality dictionary for Box (Box Int) comes from boxEqDict (boxEqDict intEqDict).

Defaults are implementations, too

The class’s default inequality method can be made explicit as well:

eqDictFrom :: (a -> a -> Bool) -> EqDict a
eqDictFrom eq = EqDict
  { eqMethod  = eq
  , neqMethod = \x y -> not (eq x y)
  }

For a manual instance that implements only (==), the dictionary still provides inequality through its default. If both methods were defined only through mutually recursive defaults, the dictionary would contain operations that loop; passing a record does not make those definitions productive.

Superclasses provide evidence inside evidence

An ordering dictionary can conceptually contain its required equality dictionary:

data OrdDict a = OrdDict
  { eqSuperclass :: EqDict a
  , compareMethod :: a -> a -> Ordering
  }
 
compareAndCheckExplicit :: OrdDict a -> a -> a -> Bool
compareAndCheckExplicit dict x y =
  compareMethod dict x y == LT ||
  eqMethod (eqSuperclass dict) x y

This simplified record omits the other ordering methods, but shows why Ord a is enough to use both comparisons and equality: the needed superclass evidence is available from the ordering evidence. The comparison with LT uses the already concrete Eq Ordering instance.

What GHC actually generates

Our records describe the mechanism; they are not a promise that GHC literally inserts these source declarations or preserves this exact layout. In GHC’s intermediate language, Core, constraints are represented by evidence arguments. A schematic view is:

same @a dict x y = equalityMethod dict x y

Here @a indicates an intermediate-language type argument. This line is explanatory pseudocode. Type arguments are erased before execution; dictionary evidence may survive as runtime values or disappear through optimization. GHC can specialize overloaded functions for known types and inline selected methods, sometimes eliminating the dictionary machinery. See the GHC optimization guide.

The reliable conceptual model is an implicit parameter containing operations. The final machine code depends on compilation and optimization decisions.

7.9 Automatic instances with deriving

For ordinary algebraic data types, the compiler can generate several standard instances:

data Color = Red | Green | Blue
  deriving (Eq, Ord, Show)
 
-- Red == Red    -- True
-- Red == Green  -- False
-- show Blue     -- "Blue"
-- Red < Green   -- True
-- Green < Blue  -- True

Derived ordering follows the order of constructors in the declaration. It is not an intrinsic mathematical ordering of colors.

For a product type, derived equality compares corresponding fields:

data Point = Point Int Int
  deriving (Eq, Show)
 
-- Point 1 2 == Point 1 2  -- True
-- Point 1 2 == Point 2 1  -- False

For parameterized data, deriving introduces the necessary constraints. As an alternative to the manual Box definition in Section 7.7, we could write:

data Box a = Box a
  deriving (Eq, Show)

Its generated equality behaves like instance Eq a => Eq (Box a). Choose either manual equality or derived equality for a given type, rather than defining both instances.

7.10 Standard classes and overloaded literals

Class	Purpose	Representative operations
Eq	Equality	==, /=
Ord	Ordering	compare, <, <=
Show	Convert a value to text	show
Read	Parse a value from text	read
Num	Basic arithmetic	+, -, *, fromInteger
Fractional	Fractional arithmetic	/, fromRational
Integral	Integral division	quotRem, divMod

An integer literal uses the Num operation:

fromInteger :: Num a => Integer -> a

Conceptually, the literal 3 is converted from an Integer using fromInteger. This explains why it can appear at different numeric types:

3 :: Int
3 :: Integer
3 :: Double

Show and Read illustrate how context can constrain either an input or a result:

show :: Show a => a -> String
read :: Read a => String -> a
 
-- show (123 :: Int)       -- "123"
-- read "123" :: Int      -- 123
-- read "123" :: Double   -- 123.0

For read, the expected result type tells Haskell which parsing instance is needed. Parsing invalid input with read can fail at runtime; a total interface for ordinary parse failure is available from Text.Read:

import Text.Read (readMaybe)
 
-- readMaybe "123" :: Maybe Int   -- Just 123
-- readMaybe "oops" :: Maybe Int  -- Nothing

7.11 Type classes and algebraic data types

An algebraic data type specifies how values are constructed:

data Shape
  = Circle Double
  | Rectangle Double Double

We can define an operation by pattern matching over that known set of alternatives. A type class instead specifies an operation that independently defined types can support:

class Area a where
  area :: a -> Double
 
data Disk = Disk Double
data Rect = Rect Double Double
 
instance Area Disk where
  area (Disk r) = pi * r * r
 
instance Area Rect where
  area (Rect w h) = w * h
 
-- area (Disk 2.0)      -- approximately 12.566
-- area (Rect 3.0 4.0)  -- 12.0

Algebraic data type	Type class
Specifies possible value structures	Specifies supported operations
Defined with data	Defined with class and instance
Alternatives distinguished by constructors	Implementations associated with instance types
Operations can pattern-match over alternatives	Generic code requests operations through constraints

ADTs are convenient for a known set of alternatives. Type classes are convenient when multiple types should support a shared operation. They solve different design problems and often work together.

7.12 The grammar in one place

The common single-parameter forms are:

class [SuperclassConstraints =>] ClassName TypeVariable where
  MethodSignature
  [DefaultMethodDefinition]
  ...
 
instance [InstanceConstraints =>] ClassName InstanceType where
  MethodDefinition
  ...

The square brackets here mark optional grammar fragments; they are not literal Haskell syntax. Typical examples are:

class Render a where
  render :: a -> String
 
instance Render Int where
  render x = show x
 
instance Eq a => Eq (Box a) where
  Box x == Box y = x == y

These snippets summarize earlier definitions; do not add duplicate class or instance declarations to the same module.

A qualified type places constraints before =>:

a -> a
Eq a => a -> a -> Bool
Num a => a -> a
(Eq a, Show a) => a -> String

These forms cover the ordinary class syntax used here. The Haskell Report’s section on type classes and overloading gives the complete language rules.

7.13 Exercises

1. Infer the most general type

f x y = x == y

Show solution

f :: Eq a => a -> a -> Bool

Equality requires Eq a, and both arguments must have the same type.

2. Infer the constraints

f x = x > 0

Show solution

f :: (Ord a, Num a) => a -> Bool

Ordering requires Ord a; the literal 0 requires Num a. Num alone does not supply ordering.

3. Implement equality

data Direction = North | South
  deriving (Show)

Show solution

instance Eq Direction where
  North == North = True
  South == South = True
  _ == _ = False

The default /= follows from the supplied (==).

4. Supply the instance context

instance ??? => Eq (Box a) where
  Box x == Box y = x == y

Show solution

instance Eq a => Eq (Box a) where
  Box x == Box y = x == y

The box implementation needs equality for its contents. In the explicit model, it receives an EqDict a and builds an EqDict (Box a).

5. Define an interface

Write a class for types that can be converted to a list of Int values.

Show solution

class ToInts a where
  toInts :: a -> [Int]

The method consumes the instance type and returns a list with a fixed element type.

6. Explain the missing constraint

Why is this signature sufficient?

f :: Ord a => a -> a -> Bool
f x y = x < y || x == y

Show solution

Eq a is a superclass of Ord a. The ordering evidence gives access to equality evidence, so a separate Eq a constraint would be redundant.

7. Compare implicit and explicit operations

What differs between these interfaces?

f :: Eq a => a -> Bool
g :: (a -> a -> Bool) -> a -> Bool

Show solution

f receives equality through a type-class constraint whose evidence is supplied by the compiler. g receives a comparison function explicitly from its caller. An explicit dictionary model of f would have the type:

fExplicit :: EqDict a -> a -> Bool

The explicit caller can choose an arbitrary comparison, whereas ordinary type-class use follows the selected instance.

7.14 Type classes as mathematical structure

An equality instance can be viewed as a type $A$ equipped with an operation:

$${\mathrm{eq}}_A:A\times A\to \mathrm{Bool}.$$

Then Eq a => a -> a -> Bool describes a function that works with a type together with its equality operations. a -> a asks for no such extra structure. The explicit dictionary makes that difference concrete.

Types alone do not prove that supplied operations behave sensibly. Equality instances are conventionally expected to satisfy properties such as reflexivity, symmetry, and transitivity; Haskell’s type checker does not establish those properties. Ordering has its own expected laws, and the mapping interface in the next post will have identity and composition laws.

The distinction between an interface and its laws matters: an instance can have methods of the correct types while giving surprising or unsuitable behavior.

Concept	Meaning
Class	A family of operations
Instance	Implementations for an instance type
Constraint	A requirement for evidence of those operations
Dictionary	A conceptual typed record of implementations
Dictionary passing	Supplying evidence as implicit arguments
Instance resolution	Determining how to obtain that evidence
Generic instance	Constructing evidence from other evidence
Superclass	Making one class’s evidence available from another

Next we will use exactly this mechanism for Functor, whose parameter is a type constructor such as Maybe, rather than a complete type such as Int.

Adapted from Block 7 and the expanded dictionary-passing explanation in the original GPT tutorial.

← Previous: Higher-order functions · Series · Next: Functors →