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.
Classes, instances, constraints
Definition— Type class
A class declaration names a set of methods with their types, in terms of a type variable:
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x /= y = not (x == y) -- a default definitionA 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.
Writing classes and instances
Your own instances, and your own class
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])))[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.4The 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.
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 -> aHere 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.
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))(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.
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))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.
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 type | Only by editing the type's declaration | Anywhere: write a new instance for a type you did not define |
| Dispatch | On the run-time object | On the static type, decided at compile time |
| Methods returning the type | Awkward | Natural: mempty :: Monoid a => a, minBound, read choose the instance from the expected result type |
| Instances for type constructors | Not expressible | Functor Tree, Foldable Maybe |
The standard classes you will meet
| Class | Methods (some) | Meaning |
|---|---|---|
Eq, Ord | ==, compare, <, max | equality, total ordering |
Show, Read | show, read | to and from source-code text |
Enum, Bounded | succ, [a ..], minBound | enumerable, with limits |
Num, Integral, Fractional | +, div, / | numeric tower |
Semigroup, Monoid | <>, mempty | combinable, with identity |
Functor | fmap, <$> | map over a context |
Foldable, Traversable | foldr, foldMap, traverse | visit and combine, or visit with effects |
Applicative, Monad | pure, <*>, >>= | sequence computations in a context (next lesson) |
The Typeclassopedia describes them all with their laws.
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:
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 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
1. Type classes: Eq, Ord, Show, Functor, Foldable
Warm-upComputationalWhat 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-upComputationalWhat 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
CoreHumanWhat constraint does this function need?
ranking :: ??? => [a] -> String
ranking xs = unwords (map show (sort xs))
4. Type classes: Eq, Ord, Show, Functor, Foldable
CoreHumanYou have defined data Bag a = Bag [a]. Which instance must you write so that sum (Bag [1, 2, 3]) compiles?
5. Type classes: Eq, Ord, Show, Functor, Foldable
CoreComputationalWhat 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
StretchComputationalA 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
StretchHumanWhy does the standard library wrap numbers in Sum and Product instead of giving Int a Monoid instance directly?
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.