Skip to content
LumenaryAcademy
Practice 60 min

Type classes: Eq, Ord, Show, Functor, Foldable

How one function can work on many types without losing type safety, from equality and printing to mapping and folding over any container.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

One name, many types

You can compare two numbers with ==, two strings, two lists of booleans, two Maybe Books. You can show almost anything, sort any list whose elements can be ordered, and sum a list, a Maybe or a tree. Yet every one of those functions is type-checked: sort will not accept a list of functions, because functions cannot be ordered, and it tells you so at compile time.

The mechanism behind this is the type class, Haskell's most influential invention. A type class names a set of operations (equality, ordering, printing, mapping); types join the class by providing an instance; and functions say which classes they need with a constraint. You have been reading constraints since lesson 2: Num a =>, Ord a =>. This lesson shows how to write classes and instances yourself, and introduces the standard classes that structure most Haskell code.

DefinitionsH

Classes, instances, constraints

Definition— Type class

A class declaration names a set of methods with their types, in terms of a type variable:

haskell
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  x /= y = not (x == y)   -- a default definition

A method may have a default definition in terms of the others, so an instance need only define a minimal set. For Eq, defining == is enough.

Definition— Instance

An instance declares that a particular type belongs to a class, by defining its methods for that type: instance Eq Colour where .... An instance may itself require other instances, through an instance context: instance Eq a => Eq [a] says that lists can be compared whenever their elements can.

Definition— Constraint

A constraint C a => in a type says the function works for every type a that has an instance of C. sort :: Ord a => [a] -> [a]. Several constraints go in parentheses: (Ord k, Show v) => ....

Definition— Superclass

A class can require another: class Eq a => Ord a means every ordered type must also have equality. Ord's methods (compare, <, max and so on) can then rely on ==.

Definition— Laws

Most standard classes come with laws: equations every instance is expected to satisfy, such as x == x for Eq or fmap id = id for Functor. The compiler does not check laws; programmers and tests do. Code everywhere relies on them.

Worked examplesH

Writing classes and instances

Your own instances, and your own class

haskell
import Data.List (intercalate, sort)

-- A software version such as 1.10.2.
newtype Version = Version [Int] deriving (Eq, Ord)

-- Our own Show instance: print versions the way people write them.
instance Show Version where
  show (Version parts) = intercalate "." (map show parts)

-- A class of our own, with one method that has a default definition.
class Pretty a where
  pretty :: a -> String
  prettyList :: [a] -> String
  prettyList xs = "[" ++ intercalate ", " (map pretty xs) ++ "]"

instance Pretty Bool where
  pretty True = "yes"
  pretty False = "no"

instance Pretty Version where
  pretty v = "v" ++ show v

-- Instances can depend on other instances: a Maybe of something pretty is pretty.
instance Pretty a => Pretty (Maybe a) where
  pretty Nothing = "(none)"
  pretty (Just x) = pretty x

instance (Pretty a, Pretty b) => Pretty (a, b) where
  pretty (a, b) = pretty a ++ " / " ++ pretty b

main :: IO ()
main = do
  let versions = [Version [1, 10, 2], Version [1, 9], Version [2, 0], Version [1, 9, 4]]
  print (sort versions)
  print (sort (map show versions)) -- as text, "1.10.2" sorts before "1.9"
  print (maximum versions, Version [1, 9] < Version [1, 9, 0])
  putStrLn (prettyList [True, False])
  putStrLn (prettyList [Just (Version [3, 1]), Nothing])
  putStrLn (pretty (True, Just (Version [0, 4])))
text
[1.9,1.9.4,1.10.2,2.0]
["1.10.2","1.9","1.9.4","2.0"]
(2.0,True)
[yes, no]
[v3.1, (none)]
yes / v0.4

The Version type gets Eq and Ord by deriving. Because the field is a list of Ints, the derived order compares component by component, as numbers, which is exactly how versions should sort. Sorting the same versions as strings puts 1.10.2 before 1.9, a classic bug in hand-written version comparisons. Writing Show by hand makes versions print the way people write them.

The derived ordering has one quirk worth noticing: 1.9 is less than 1.9.0, because a list that is a prefix of another sorts first. If your project considers them equal, you would write Eq and Ord by hand (pad the shorter list with zeros before comparing). Deriving is a sensible default, not a decision you cannot revisit.

The Pretty class shows the other features. prettyList has a default, so the instances only define pretty. And the instances for Maybe a and for pairs have contexts: GHC builds the right code for pretty (True, Just (Version [0, 4])) by combining the Bool, Version, Maybe and pair instances, chosen from the types alone. You never pass them yourself.

Functor and Foldable

Two of the most useful standard classes are about containers, or more precisely, about types with a parameter, like Maybe a, [a] or Tree a.

text
ghci> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
ghci> :t foldMap
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
ghci> :t sum
sum :: (Foldable t, Num a) => t a -> a

Here f and t stand for a type constructor such as Maybe or Tree, not a full type. fmap applies a function to every element inside, keeping the shape. Foldable says the elements can be visited in order and combined; sum, length, elem, maximum, foldr and many more are its methods, which is why they work on far more than lists.

haskell
data Tree a = Leaf | Node (Tree a) a (Tree a)

-- fmap applies a function to every element, keeping the shape.
instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)

-- foldr is enough to make a Foldable: sum, length, elem, maximum... come free.
instance Foldable Tree where
  foldr _ z Leaf = z
  foldr f z (Node l x r) = foldr f (f x (foldr f z r)) l

main :: IO ()
main = do
  let t = Node (Node Leaf 3 Leaf) 5 (Node Leaf 8 Leaf)
  print (sum t, product t, length t, maximum t, elem 8 t)
  print (foldr (:) [] t, foldr (:) [] (fmap (* 10) t))
  print (fmap length (Just "hello"), fmap (+ 1) [1, 2, 3])
  print (fmap (+ 1) (Right 3 :: Either String Int), fmap (+ 1) (Left "no number" :: Either String Int))
  print (sum (Just 5), length (Just 'x'), length Nothing)
  print (length (10, 20), sum (10, 20))
text
(16,120,3,8,True)
([3,5,8],[30,50,80])
(Just 5,[2,3,4])
(Right 4,Left "no number")
(5,1,0)
(1,20)

Two short instances buy a lot. Defining foldr for Tree (visiting the left subtree, then the node, then the right) gives the tree sum, product, length, maximum, elem and about a dozen more, all with the in-order meaning. The Functor instance makes fmap (* 10) work on trees exactly as map works on lists; in fact, for lists, fmap is map.

fmap on Maybe applies the function inside a Just and leaves Nothing alone. On Either e, it applies the function to a Right and leaves a Left (an error) untouched. That is the beginning of a theme for the next lesson: a Functor lets you work on the value inside a context without taking it out.

The last line is a famous surprise. A pair (a, b) is Foldable over its second component only (the first is part of the "shape", like a label), so length (10, 20) is 1 and sum (10, 20) is 20. It follows from the rules, but it catches everyone once.

Note

For types like Tree, you rarely write these instances by hand. With GHC2021, the default language edition, you can write data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Functor, Foldable, Traversable) and GHC generates them. Writing them once yourself is the best way to understand what deriving does.

Semigroup and Monoid

A semigroup is a type with an associative way to combine two values, <>. A monoid adds an identity element, mempty, that changes nothing when combined. Lists and strings are monoids under concatenation, with the empty list as identity. Numbers are monoids in two ways, under addition with 0 and under multiplication with 1, so the standard library wraps them in newtypes, Sum and Product, to say which one you mean.

haskell
import Data.Monoid (Sum (..), Product (..), Any (..))

-- Summary statistics that can be combined: a Monoid.
data Stats = Stats {count :: !Int, total :: !Double, low :: !Double, high :: !Double}

instance Semigroup Stats where
  Stats c1 t1 l1 h1 <> Stats c2 t2 l2 h2 = Stats (c1 + c2) (t1 + t2) (min l1 l2) (max h1 h2)

instance Monoid Stats where
  mempty = Stats 0 0 (1 / 0) (-1 / 0) -- infinities: identities for min and max

single :: Double -> Stats
single x = Stats 1 x x x

report :: Stats -> String
report s =
  show (count s) ++ " readings, mean " ++ show (total s / fromIntegral (count s))
    ++ ", range " ++ show (low s) ++ " to " ++ show (high s)

main :: IO ()
main = do
  let morning = [12.5, 9, 14]
      evening = [30.25, 18]
  putStrLn (report (foldMap single (morning ++ evening)))
  putStrLn (report (foldMap single morning <> foldMap single evening))
  print ("ab" <> "cd", [1, 2] <> [3], mconcat ["x", "y", "z"])
  print (getSum (foldMap Sum [1 .. 10]), getProduct (foldMap Product [1 .. 5]))
  print (getAny (foldMap (Any . (> 20)) morning), getAny (foldMap (Any . (> 20)) evening))
text
5 readings, mean 16.75, range 9.0 to 30.25
5 readings, mean 16.75, range 9.0 to 30.25
("abcd",[1,2,3],"xyz")
(55,120)
(False,True)

foldMap single turns each reading into a one-reading summary and combines them all with <>. The first two output lines are equal, and that is the point: because <> is associative, you can summarise the morning and the evening separately (on two machines, on two cores, in two months) and combine the summaries, and get exactly the answer you would have got from all the data at once. This is the idea behind many large-scale data systems, which aggregate partial results across thousands of machines.

Stats has strict fields (the !), which you met briefly in lesson 5; lesson 8 explains why it matters for accumulators like this.

ExplanationH

Under the hood, and compared with interfaces

How GHC implements type classes

A function with a constraint, such as pretty :: Pretty a => a -> String, is compiled into a function with an extra, hidden argument: a dictionary, a record holding the methods of the instance for the type in question. When you call pretty True, GHC sees that a is Bool, finds the instance, and passes the Bool dictionary. For pretty (True, Just v) it builds the pair dictionary from the Bool and Maybe Version dictionaries, just as the instance contexts said. All this is decided at compile time from the types. When the type is known, the optimiser usually specialises the code and removes the dictionary entirely, so class-polymorphic code costs nothing extra in hot loops.

For this to be well-defined, there may be at most one instance of a class for each type in the whole program. This property, called coherence, is why Sum and Product exist: Int cannot have two Monoid instances, so each meaning gets a newtype. An instance defined in a module that owns neither the class nor the type is called an orphan instance; GHC warns about them, and teams avoid them, because two libraries defining the same orphan would clash.

Type classes versus interfaces

Type classes resemble interfaces in Java or C#, protocols in Swift and traits in Rust (which were directly inspired by them), with differences that matter in practice.

Interface (Java, C#)Type class (Haskell)
Adding to an existing typeOnly by editing the type's declarationAnywhere: write a new instance for a type you did not define
DispatchOn the run-time objectOn the static type, decided at compile time
Methods returning the typeAwkwardNatural: mempty :: Monoid a => a, minBound, read choose the instance from the expected result type
Instances for type constructorsNot expressibleFunctor Tree, Foldable Maybe

The standard classes you will meet

ClassMethods (some)Meaning
Eq, Ord==, compare, <, maxequality, total ordering
Show, Readshow, readto and from source-code text
Enum, Boundedsucc, [a ..], minBoundenumerable, with limits
Num, Integral, Fractional+, div, /numeric tower
Semigroup, Monoid<>, memptycombinable, with identity
Functorfmap, <$>map over a context
Foldable, Traversablefoldr, foldMap, traversevisit and combine, or visit with effects
Applicative, Monadpure, <*>, >>=sequence computations in a context (next lesson)

The Typeclassopedia describes them all with their laws.

ComputationC

When not to define a class

New Haskell programmers sometimes define a type class for every abstraction, as they might define an interface for every concept in Java. Experienced Haskell programmers are more sparing. A class is worth defining when there is a law-abiding family of types with many instances, such as Monoid or Functor, or when the right implementation should be chosen automatically from a type. When you simply need "some function to call", an ordinary record of functions is often clearer:

haskell
data Logger = Logger
  { logInfo :: String -> IO (),
    logError :: String -> IO ()
  }

consoleLogger :: Logger
consoleLogger = Logger {logInfo = putStrLn, logError = putStrLn . ("ERROR: " ++)}

A function that takes a Logger argument can be given a console logger in production and a silent one in tests, and you can build new loggers at run time from configuration. That is exactly what a class's dictionary is under the hood, but passed explicitly, without coherence rules, orphan worries or type-level puzzles. The rule of thumb in many teams: start with plain functions and records; introduce a class when you find yourself passing the same dictionary everywhere, or when there are laws to state.

Common misconceptionsH

Common misconceptions

Misconception

"A type class is like a class in Java." The shared word misleads. A Haskell class is a set of types that support some operations, closer to an interface; it has no fields, no constructors and no objects. Data lives in data types, behaviour in functions and instances.

Misconception

"A Functor is a container." Many functors are containers, but the class only promises that you can map a function over "the values inside a context". Functions themselves form a functor (fmap on functions is composition), and so does IO: fmap length getLine is an action that reads a line and yields its length, without containing any string beforehand.

Misconception

"If my instance compiles, it is correct." Laws are not checked. A Functor instance that, say, reverses a list while mapping would compile, but would break code that assumes fmap id changes nothing. Property-based tests (lesson 9) are the professional way to check laws.

Misconception

"length (3, 4) must be 2." It is 1: pairs are Foldable over their second component only. Avoid calling Foldable functions on tuples; it is almost always a mistake.

Exercises

Exercises

1. Type classes: Eq, Ord, Show, Functor, Foldable

Warm-upComputational

What does this program print?

main :: IO ()
main = print (length (4, 9), maximum (Just 7), sum Nothing)

2. Type classes: Eq, Ord, Show, Functor, Foldable

Warm-upComputational

What does this program print?

main :: IO ()
main = do
  let bad = Left "oops" :: Either String Int
      good = Right 21 :: Either String Int
  print (fmap (* 2) bad, fmap (* 2) good)

3. Type classes: Eq, Ord, Show, Functor, Foldable

CoreHuman

What constraint does this function need?

ranking :: ??? => [a] -> String
ranking xs = unwords (map show (sort xs))
Choose one

4. Type classes: Eq, Ord, Show, Functor, Foldable

CoreHuman

You have defined data Bag a = Bag [a]. Which instance must you write so that sum (Bag [1, 2, 3]) compiles?

Choose one

5. Type classes: Eq, Ord, Show, Functor, Foldable

CoreComputational

What does this program print?

newtype Version = Version [Int] deriving (Eq, Ord)

main :: IO ()
main = print (Version [2] < Version [10], "2" < "10")

6. Type classes: Eq, Ord, Show, Functor, Foldable

StretchComputational

A pair of monoids is a monoid, combining component by component. What does this program print?

import Data.Monoid (Product (..), Sum (..))

main :: IO ()
main = do
  let (s, p) = foldMap (\x -> (Sum x, Product x)) [1, 2, 3, 4 :: Int]
  print (getSum s + getProduct p)

7. Type classes: Eq, Ord, Show, Functor, Foldable

StretchHuman

Why does the standard library wrap numbers in Sum and Product instead of giving Int a Monoid instance directly?

Choose one

Further reading and resources

  • Typeclassopedia · Brent Yorgey and the Haskell communityA long-standing guide to the standard type classes, their laws and how they relate.
  • How to make ad-hoc polymorphism less ad hoc · Philip Wadler and Stephen Blott · 1989The paper that introduced type classes, presented at the POPL symposium.
  • Data.Foldable documentation (base)Every function a Foldable instance provides.
  • Data.Monoid documentation (base)Sum, Product, Any, All, First, Last and the other standard monoids.