Type Classes

Sidenote: Tuples

Before we dive into type classes, let’s introduce the last remaining built-in datatype in Haskell: the tuple. Tuples or pairs (or triples, quadruples, etc) are a way of bundling a couple of values of different types together. You can think of tuples as fixed-length lists (just like Python’s tuples). Unlike lists, each element in the tuple can have a different type. The types of the elements are reflected in the type of the tuple. Here are some examples of tuple types and values:

Type	Example value
(String,String)	("Hello","World!")
(Int,Bool)	(1,True)
(Int,Int,Int)	(4,0,3)

To get values out of tuples, you can use the functions fst and snd:

fst :: (a, b) -> a
snd :: (a, b) -> b

You can also pattern match on tuples. This is often the most convenient way, and also works for tuples of larger sizes. The fst and snd functions work only on pairs.

Tuples are very useful in combination with lists. Here are some examples using the zip, unzip and partition functions from the Data.List module.

-- two lists to list of pairs
zip :: [a] -> [b] -> [(a, b)]

-- list of pairs to pair of lists
unzip :: [(a, b)] -> ([a], [b])

-- elements that satisfy and don't satisfy a predicate
partition :: (a -> Bool) -> [a] -> ([a], [a])

zip [1,2,3] [True,False,True]
  ==> [(1,True),(2,False),(3,True)]
unzip [("Fred",1), ("Jack",10), ("Helen",13)]
  ==> (["Fred","Jack","Helen"],[1,10,13])
partition (>0) [-1,1,-4,3,2,0]
  ==> ([1,3,2],[-1,-4,0])

Here’s an example of pattern matching on tuples:

swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

Here’s an example of pattern matching on tuples and lists at the same time:

-- sum all numbers that are paired with True
sumIf :: [(Bool,Int)] -> Int
sumIf [] = 0
sumIf ((True,x):xs) = x + sumIf xs
sumIf ((False,_):xs) = sumIf xs

sumIf [(True,1),(False,10),(True,100)]
  ==> 101

Interlude: Folding

Consider the functions sumNumbers :: [Int] -> Int, myMaximum :: [Int] -> Int, and countNothings :: [Maybe a] -> Int again.

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

myMaximum :: [Int] -> Int
myMaximum [] = 0
myMaximum (x:xs) = go x xs
  where go biggest [] = biggest
        go biggest (x:xs) = go (max biggest x) xs

countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs) = 1 + countNothings xs
countNothings (Just _  : xs) = countNothings xs

They have one common characteristic. They take a list and produce a value that depends on the values of the elements in the given list. They “crunch” or fold a list of many values into a single value.

Prelude has a function called foldr, which performs a right associative fold over a Foldable data type. We’ll learn more about Foldable soon. At this point, it suffices to think of lists, so we define

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f y []     = y
foldr f y (x:xs) = f x (foldr f y xs)

What this definition says, is that for an empty list [] :: [a], foldr returns the default value y :: b. For any other list x : xs, foldr applies f to x and the result of foldr f y xs (i.e. folding over the rest of the list). It’s a simple definition by recursion.

In other words, foldr calls its argument function f repeatedly with two arguments.

• The first argument is the current element from the list.
• The second argument is what f returned for the rest of the list.

Consider the list [1,2,3]:

The expression foldr (+) 0 [1,2,3] evaluates as follows:

foldr (+) 0 [1,2,3] ==> foldr (+) 0 (1:2:3:[])
                    ==> 1 + (foldr (+) 0 (2:3:[]))
                    ==> 1 + (2 + (foldr (+) 0 (3:[])))
                    ==> 1 + (2 + (3 + (foldr (+) 0 [])))
                    ==> 1 + (2 + (3 + 0))

The result can be thought of as a tree:

One way to think about foldr f y xs is that it replaces the (:) operation with f and [] with y. In this case, f was (+) and y was 0. If you write out how sumNumbers [1,2,3] behaves, you’ll notice that it performs the same computation as foldr (+) 0 [1,2,3] does! More generally:

sumNumbers xs == foldr (+) 0 xs

Those more experienced with math may notice that we can prove this claim by induction: Firstly, sumNumbers [] ==> 0 and foldr (+) 0 [] ==> 0, so in the base case sumNumbers [] == foldr (+) 0 []. Next, we may assume as our induction hypothesis that sumNumbers xs == foldr (+) 0 xs for any list xs. Then, for the list x:xs, we have sumNumbers (x:xs) ==> x + sumNumbers xs. Hence, foldr (+) 0 (x:xs) ==> x + foldr (+) 0 xs ==> x + sumNumbers xs by induction hypothesis. Therefore, by induction, the equation holds.

You don’t need to read, write, or understand induction proofs in this course, but perhaps it is reassuring to know that properties and equalities of functions in Haskell can be (in principle) analysed mathematically, because Haskell is such a nice language. (Equalities and properties can be analysed in any programming language, but for Haskell, this analysis is especially convenient because Haskell is pure.)

Another folding example is the map function:

map g xs = foldr helper [] xs
  where helper y ys = g y : ys

To see why this works, consider what foldr helper [] [x1,x2,..,xn] does:

Now, since helper x xs ==> g x : xs for every x and xs, we get that:

The resulting list, [ g x1, g x2, g x3, ..., g xn ], is then exactly what we would have gotten with map g xs. (This could have been also proved by induction as we did for sumNumbers.) The lesson to take away is that folding is a particular, yet quite general, way to apply some transformation recursively into some structure (e.g. a list).

Type Classes

How can Haskell’s + work on both Ints and Doubles? Why can I compare all sorts of things with ==? We’ve briefly mentioned constrained types earlier. Let’s see what they really mean. Let’s look at the types of == and +.

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

The type (Eq a) => a -> a -> Bool means: for all types a that belong to the class Eq, this is a function of type a -> a -> Bool. That is, if the type a is a member of the class Eq, you can give two values of type a to == and get a Bool result.

(+) :: (Num a) => a -> a -> a

Similarly, the type (Num a) => a -> a -> a means: for all types a that belong to the class Num, this is a function of type a -> a -> a. That is, you can give two values of the same type a to + and get out a third value of type a, as long as a is a member of Num.

Num and Eq are type classes. A type class is a way to group together types that support similar operations.

Note! A type class is a collection of types. It doesn’t have much to do with the classes of object oriented programming! In some situations, type classes can act like interfaces in object oriented programming. Unfortunately the functions in a type class are often called methods, adding to the confusion.

PS. remember how using type variables for polymorphism was called parametric polymorphism? The fancy word for what type classes achieve is ad-hoc polymorphism. The difference is that with parametric polymorphism the function (e.g. head) has the same implementation for all types, whereas with ad-hoc polymorphisms there are multiple implementations (consider == on numbers and strings).

Type Constraints

When you’re working with a concrete type (not a type variable), you can just use type class functions (in this case, (==)):

f :: (Int -> Int) -> Int -> Bool
f g x = x == g x

Of course, if the type in question isn’t a member of the right class, you get an error. For example:

addTrue :: Bool -> Bool
addTrue b = b + True

error:
    • No instance for (Num Bool) arising from a use of ‘+’
    • In the expression: b + True
      In an equation for ‘addTrue’: addTrue b = b + True

However in a polymorphic function, you need to add type constraints. This doesn’t work:

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

Luckily the error is nice:

error:
    • No instance for (Eq a) arising from a use of ‘==’
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            f :: (a -> a) -> a -> Bool
    • In the expression: x == g x
      In an equation for ‘f’: f g x = x == g x

To signal that f only works on types that are members of the Eq class, we add a type constraint (Eq a) => to the type annotation.

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

If you don’t have a type annotation, type inference can provide the constraints!

Prelude> let f g x = x == g x
Prelude> :type f
f :: (Eq a) => (a -> a) -> a -> Bool

You can also have multiple constraints:

bothPairsEqual :: (Eq a, Eq b) => a -> a -> b -> b -> Bool
bothPairsEqual x1 x2 y1 y2 = x1 == x2 && y1 == y2

Standard Type Classes

Here are some standard Haskell type classes you should know about.

Eq

We already saw the Eq class for equality comparisons. Here are the basic operations of the Eq class and some examples of their use. As you can see pretty much all the types we’ve seen so far, except for functions, are members of Eq.

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

Prelude> 1 == 2
False
Prelude> 1 /= 2
True
Prelude> "Foo" == "Bar"
False
Prelude> [[1,2],[3,4]] == [[1,2],[3,4]]
True
Prelude> (\x -> x+1) == (\x -> x+2)

<interactive>:5:1: error:
    • No instance for (Eq (Integer -> Integer))
        arising from a use of ‘==’
        (maybe you haven't applied a function to enough
         arguments?)
    • In the expression: (\ x -> x + 1) == (\ x -> x + 2)
      In an equation for ‘it’:
        it = (\ x -> x + 1) == (\ x -> x + 2)

There are some other useful functions that use the Eq class, like nub from the module Data.List.

Prelude> import Data.List
Prelude Data.List> :t nub
nub :: Eq a => [a] -> [a]
Prelude Data.List> nub [3,5,3,1,1] -- eliminates duplicates
[3,5,1]

Ord

The Ord class is for ordering (less than, greater than). Again, here are the basic operations and some examples of their use. Note the new Ordering type. It has values LT for “less than”, EQ for “equal” and GT for “greater than”.

compare :: Ord a => a -> a -> Ordering
(<)  :: Ord a => a -> a -> Bool
(>)  :: Ord a => a -> a -> Bool
(>=) :: Ord a => a -> a -> Bool
(<=) :: Ord a => a -> a -> Bool
max  :: Ord a => a -> a -> a
min  :: Ord a => a -> a -> a

Prelude> compare 1 1           -- 1 is EQual to 1
EQ
Prelude> compare 1 3           -- 1 is Less Than 3
LT
Prelude> compare 1 0           -- 1 is Greater Than 0
GT
Prelude> min 5 3
3
Prelude> max 5 3
5
Prelude> "aardvark" < "banana" -- alphabetic comparison
True
Prelude> [1,2,3] > [2,5]       -- similar to strings
False
Prelude> [1,2,3] > [1,1]
True

When we can compare values, we can also sort lists of them. The function sort from Data.List works on all types that belong to the Ord class.

Prelude> import Data.List
Prelude Data.List> :t sort
sort :: Ord a => [a] -> [a]
Prelude Data.List> sort [6,1,4,8,2]
[1,2,4,6,8]
Prelude Data.List> sort "black sphinx of quartz"
"   aabcfhiklnopqrstuxz"

As a last example, let’s sort a list of lists according to length. We’ll need two helper functions:

-- from the module Data.Ord
-- compares two values "through" the function f
comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing f x y = compare (f x) (f y)

-- from the module Data.List
-- sorts a list using the given comparison function
sortBy :: (a -> a -> Ordering) -> [a] -> [a]

Now the implementation of sortByLength is straightforward:

-- sorts lists by their length
sortByLength :: [[a]] -> [[a]]
sortByLength = sortBy (comparing length)

sortByLength [[1,2,3],[4,5],[4,5,6,7]]
  ==>  [[4,5],[1,2,3],[4,5,6,7]]

Num, Integral, Fractional, Floating

The Num class contains integer arithmetic:

(+) :: Num a => a -> a -> a
(-) :: Num a => a -> a -> a
(*) :: Num a => a -> a -> a
negate :: Num a => a -> a    -- 0-x
abs :: Num a => a -> a       -- absolute value
signum :: Num a => a -> a    -- -1, 0, or 1
fromInteger :: Num a => Integer -> a

Num also shows up in the types of integer literals:

Prelude> :t 12
12 :: Num p => p

This means that a literal like 12 can be interpreted as a member of any type implementing Num. When GHC reads a number literal like, 12 it produces code that corresponds to fromIntegral 12.

Prelude> 1 :: Int
1
Prelude> 1 :: Double
1.0
Prelude> fromIntegral 1 :: Double
1.0

Integral is the class of types that represent whole numbers, like Int and Integer. The most interesting functions are div and mod for integer division and remainder. All types that belong to Integral also belong to Num.

div :: Integral a => a -> a -> a
mod :: Integral a => a -> a -> a

Fractional is the class for types that have division. All types that belong to Fractional also belong to Num.

(/) :: Fractional a => a -> a -> a

Floating contains some additional operations that only make sense for floating point numbers. All types that belong to Floating also belong to Fractional (and to Num).

sqrt :: Floating a => a -> a
sin :: Floating a => a -> a

Read and Show

The Show and Read classes are for the functions show and read, that convert values to and from Strings.

show :: Show a => a -> String
read :: Read a => String -> a

Prelude> show 3
"3"
Prelude> read "3" :: Int
3
Prelude> read "3" :: Double
3.0

As you can see above, you often need to use a type annotation with read so that the compiler can choose the right implementation.

Sidenote: Foldable

One more thing! You might remember that it was mentioned earlier that the type of length isn’t [a] -> Int but something more general. Let’s have a look:

Prelude> :t length
length :: Foldable t => t a -> Int

This type looks a bit different than the ones we’ve seen before. The type variable t has an argument a. We’ll look at type classes like this in more detail later, but here’s a crash course.

What Foldable represents is types that you can fold over. The true type of foldr is:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

We’ve succesfully used the fact that lists are Foldable since we’ve managed to use length and foldr on lists. However, Maybe is also Foldable! The Foldable instance for Maybe just pretends that values of Maybe a are like lists of length 0 or 1:

foldr (+) 1 Nothing   ==> 1
foldr (+) 1 (Just 3)  ==> 4
length Nothing        ==> 0
length (Just 'a')     ==> 1

Reading Docs

Haskell libraries tend to have pretty good docs. We’ve linked to docs via Hackage (https://hackage.haskell.org) previously, but it’s important to know how to find the docs by your self too. The tool for generating Haskell documentation is called Haddock so sometimes Haskell docs are referred to as haddocks.

Hackage is the Haskell package repository (just like PyPI for Python, Maven Central for Java or NPM for Javascript). In addition to the actual packages, it hosts documentation for them. Most of the modules that we use on this course are in the package called base. You can browse the docs for the base package at http://hackage.haskell.org/package/base.

When you’re not quite sure where the function you’re looking for is, Hoogle (https://hoogle.haskell.org/) can help. Hoogle is a search engine for Haskell documentation. It is a great resource when you need to check what was the type of foldr or which packages contain a function named reverse.

In summary, here are the main ways of reading Haskell library documentation:

• If you know the name of the package you browse the docs via https://hackage.haskell.org/.
• If you know the name of the function you can find it using https://hoogle.haskell.org/.

Self Checks

Check 1

What is the type of swap . swap?

1. (a, b) -> (a, b)
2. (a, b) -> (b, a)
3. a -> a

Check 2

What is the type of \f g x -> (f x, g x)?

1. (a -> b) -> (c -> d) -> (a,c) -> (b, d)
2. (a -> b) -> (a -> c) -> a -> (b, c)
3. (a -> b) -> (b -> a) -> a -> (b, a)

Check 3

What is the type of
\t -> (fst . fst $ t, (snd . fst $ t, snd t))?

1. (a, (b, c)) -> (a, (b, c))
2. (a, (b, c)) -> ((a, b), c)
3. ((a, b), c) -> (a, (b, c))

Check 4

What does the function foldr (\x xs -> xs ++ [x]) [] do?

1. It doesn’t change its input list at all
2. It changes the associativity of a list from left to right
3. It reverses its input list

Check 5

What does the function foldr (\(x, y) zs -> x : y : zs) [] do?

1. It turns a list of pairs into a pair of lists
2. It turns a pair of lists into a list of pairs
3. It turns a list of pairs into a list of elements

Check 6

What is the type of foldr (\n b -> n == 3 && b)?

1. (Foldable t, Eq a, Num a) => Bool -> t a -> Bool
2. (Foldable t, Eq a, Num a, Bool b) => b -> t a -> b
3. (Foldable t, Eq a, Num a) => Bool -> [ a ] -> Bool

Check 7

What is the type of
\x -> case x of (True, "Foo") -> show True ++ "Foo"?

1. Either Bool String -> String
2. (Bool, String) -> String
3. Show a => (Bool, String) -> a

Acknowledgment:

This reading was originally written by Joel Kaasinen and John Lång in their open source textbook. The book is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License, which allows users to copy, modify, and distribute the book.

This reading was modified by Titus H. Klinge in 2021 and presented above under the same license in order to better serve the students of this course.