3.1 The problem: one symbol, many types

== should work on Int, Char, Bool, lists... but not on functions (equality of functions is undecidable). + should work on Int and Double but not on Bool. This controlled "one name, many implementations" is overloading (ad-hoc polymorphism) — and Haskell's mechanism for it is the type class.

Contrast with parametric polymorphism: length :: [a] -> Int uses one implementation for all types; (==) needs a different implementation per type.

3.2 Declaring a class and its instances

-- A class declares an interface: a set of method signatures
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x /= y = not (x == y)        -- default method definition

-- An instance provides the implementation for one type
data Colour = Red | Green | Blue

instance Eq Colour where
  Red   == Red   = True
  Green == Green = True
  Blue  == Blue  = True
  _     == _     = False

Because /= has a default, an instance only needs to define ==.

3.3 Reading constrained types

elem :: Eq a => a -> [a] -> Bool

Read Eq a => as: "for any type a that supports equality". The part before => is the context (constraint). Multiple constraints: (Eq a, Show a) => ....

3.4 The standard classes you must know

Ord is a subclass of Eq (class Eq a => Ord a where ...): every ordered type must first be an equality type.

For your own data types, Haskell can write the obvious instances automatically:

data Colour = Red | Green | Blue
  deriving (Eq, Ord, Show, Enum, Bounded)

3.5 Type checking — how Haskell finds types by itself

Haskell uses the Hindley–Milner type system: the compiler infers the most general (principal) type of every expression without annotations, by unification:

1. Assign every subexpression a fresh type variable.
2. Generate equations from the rules: in f x, if f :: t1 and x :: t2, then t1 = t2 -> t3.
3. Solve the equations (unification); overloaded symbols contribute constraints instead of fixed types.

Worked inference example:

twiceHead xs = head xs + head xs
-- head :: [a] -> a       so  xs :: [a]  and  head xs :: a
-- (+)  :: Num b => b -> b -> b  forces a = b with constraint Num a
-- Result:  twiceHead :: Num a => [a] -> a

The famous benefit: "if it type-checks, it usually works" — the type checker rules out whole categories of bugs before the program ever runs.

3.6 Common type errors decoded

3.7 Why type classes matter beyond Haskell

Type classes are the ancestor of interfaces with default methods (Java 8), traits (Rust/Scala), and protocols (Swift). Understanding them here means understanding the design of half the modern language landscape.

3.8 Type classes vs OOP interfaces — the comparison table

The "dispatch on return type" point deserves a sentence in any comparison answer: read "5" :: Int chooses the Int parser purely from the expected result type — impossible with receiver-based dispatch.

3.9 The class hierarchy at a glance

An arrow means "is a superclass of": to be Ord, a type must already be Eq. (The hierarchy here is simplified to what the exam needs.)

3.10 Instances for parameterised types — propagating constraints

How does [1,2] == [1,2] work? Lists are Eq whenever their elements are:

instance Eq a => Eq [a] where
  []     == []     = True
  (x:xs) == (y:ys) = x == y && xs == ys
  _      == _      = False

instance Eq a => Eq (Maybe a) where
  Nothing == Nothing = True
  Just x  == Just y  = x == y
  _       == _       = False

Read instance Eq a => Eq [a] as: "if a has equality, then [a] has equality" — the constraint machinery is itself rule-like (compare Prolog's :- in Unit 3!).

3.11 A complete type-inference derivation (exam format)

Infer the type of compose f g x = f (g x):

1. Assign fresh variables:   f :: t1,  g :: t2,  x :: t3
2. g x        demands  t2 = t3 -> t4          (g applied to x, result t4)
3. f (g x)    demands  t1 = t4 -> t5          (f applied to result of g)
4. Collect:   compose :: t1 -> t2 -> t3 -> t5
            =  (t4 -> t5) -> (t3 -> t4) -> t3 -> t5
5. Rename tidily (b -> c) -> (a -> b) -> a -> c

This is exactly the library type of (.). Present inference answers in this 5-step layout: fresh variables → one equation per application → solve → substitute → rename.

A second one with a constraint — member x xs = any (== x) xs:

(==) :: Eq a => a -> a -> Bool   ⇒  (== x) :: Eq a => a -> Bool, x :: a
any  :: (b -> Bool) -> [b] -> Bool  forces  b = a
Result:  member :: Eq a => a -> [a] -> Bool

3.12 Overloading vs parametric polymorphism — the precise distinction

Parametric polymorphism: one definition, uniform behaviour at every type — length :: [a] -> Int never looks at the elements. Ad-hoc polymorphism (overloading): one name, a different definition per type, organised by classes — (==) on Int compares machine words; on lists it recurses.

The type tells you which is which: an unconstrained variable (a) is parametric; a constrained one (Eq a => a) is overloaded. A function can use both at once: elem :: Eq a => a -> [a] -> Bool is parametric in the list structure, overloaded on element equality.

Exam pointers

• "What is a type class? Explain with Eq" — give the class declaration, one instance, and the constrained type of elem. Mention default methods.
• "Explain type inference / Hindley–Milner" — define principal type, then run a derivation in the §3.11 layout on a tiny example.
• "Distinguish parametric and ad-hoc polymorphism" — the boxed definitions plus length vs (==) as witnesses.
• Decoding GHC error messages (§3.6) appears as "explain why this expression is ill-typed" — name the missing instance.

Self-check

1. Why can there be no Eq instance for function types?
2. Write instance Show Colour by hand (without deriving) for data Colour = Red | Green | Blue.
3. Infer the type of twice f x = f (f x) using the 5-step layout.
4. What constraint does sort :: ? => [a] -> [a] need, and why?
5. Explain why show (read "5") is ambiguous and give two ways to fix it.