So far, all of the types we’ve defined have been of constant size. We can represent one report or one colour, but how could we represent a collection of things? We could use lists of course, but could we define a list type ourselves?

Just like Haskell functions, Haskell data types can be recursive. This is no weirder than having an object in Java or Python that refers to another object of the same class. This is how you define a list of integers:

data IntList = Empty | Node Int IntList
    deriving Show

ihead :: IntList -> Int
ihead (Node i _) = i

itail :: IntList -> IntList
itail (Node _ t) = t

ilength :: IntList -> Int
ilength Empty = 0
ilength (Node _ t) = 1 + ilength t

We can use the functions defined above to work with lists of integers:

Prelude> ihead (Node 3 (Node 5 (Node 4 Empty)))
3
Prelude> itail (Node 3 (Node 5 (Node 4 Empty)))
Node 5 (Node 4 Empty)
Prelude> ilength (Node 3 (Node 5 (Node 4 Empty)))
3

Note that we can’t put values other than Ints inside our IntList:

Prelude> Node False Empty

<interactive>:3:6: error:
    • Couldn't match expected type ‘Int’ with actual type ‘Bool’
    • In the first argument of ‘Node’, namely ‘False’
        In the expression: Node False Empty
        In an equation for ‘it’: it = Node False Empty

To be able to put any type of element in our list, let’s do the same thing with a type parameter. This is the same as the built in type [a], but with slightly clunkier syntax:

data List a = Empty | Node a (List a)
    deriving Show

Note how we need to pass the the type parameter a onwards in the recursion. We need to write Node a (List a) instead of Node a List. The Node constructor has two arguments. The first has type a, and the second has type List a. Here are the reimplementations of some standard list functions for our List type:

lhead :: List a -> a
lhead (Node h _) = h

ltail :: List a -> List a
ltail (Node _ t) = t

lnull :: List a -> Bool
lnull Empty = True
lnull _     = False

llength :: List a -> Int
llength Empty = 0
llength (Node _ t) = 1 + llength t

Prelude> lhead (Node True Empty)
True
Prelude> ltail (Node True (Node False Empty))
Node False Empty
Prelude> lnull Empty
True

Note that just like with normal Haskell lists, we can’t have elements of different types in the same list:

Prelude> Node True (Node "foo" Empty)

<interactive>:5:12: error:
    • Couldn't match type ‘[Char]’ with ‘Bool’
        Expected type: List Bool
        Actual type: List [Char]
    • In the second argument of ‘Node’, namely ‘(Node "foo" Empty)’
        In the expression: Node True (Node "foo" Empty)
        In an equation for ‘it’: it = Node True (Node "foo" Empty)

Example: Growing a Tree

Just like a list, we can also represent a binary tree:

data Tree a = Node a (Tree a) (Tree a) | Empty

Our tree contains nodes, which contain a value of type a and two child trees, and empty trees.

In case you’re not familiar with binary trees, they’re a data structure that’s often used as the basis for other data structures (Data.Map is based on trees!). Binary trees are often drawn as (upside-down) pictures, like this:

The highest node in the tree is called the root (0 in this case), and the nodes with no children are called leaves (2, 3 and 4 in this case). We can define this tree using our Tree type like this:

example :: Tree Int
example = (Node 0 (Node 1 (Node 2 Empty Empty)
                            (Node 3 Empty Empty))
                    (Node 4 Empty Empty))

The height of a binary tree is length of the longest path from the root to a leaf. In Haskell terms, it’s how many nested levels of Node constructors you need to build the tree. The height of our example tree is 3. Here’s a function that computes the height of a tree:

treeHeight :: Tree a -> Int
treeHeight Empty = 0
treeHeight (Node _ l r) = 1 + max (treeHeight l) (treeHeight r)

treeHeight Empty ==> 0
treeHeight (Node 2 Empty Empty)
    ==> 1 + max (treeHeight Empty) (treeHeight Empty)
    ==> 1 + max 0 0
    ==> 1
treeHeight (Node 1 Empty (Node 2 Empty Empty))
    ==> 1 + max (treeHeight Empty) (treeHeight (Node 2 Empty Empty))
    ==> 1 + max 0 1
    ==> 2
treeHeight (Node 0 (Node 1 Empty (Node 2 Empty Empty)) Empty)
    ==> 1 + max (treeHeight (Node 1 Empty (Node 2 Empty Empty))) (treeHeight Empty)
    ==> 1 + max 2 0
    ==> 3

In case you’re familiar with binary search trees, here are the definitions of the lookup and insert opertions for a binary search tree. If you don’t know what I’m talking about, you don’t need to understand this.

lookup :: Int -> Tree Int -> Bool
lookup x Empty = False
lookup x (Node y l r)
    | x < y = lookup x l
    | x > y = lookup x r
    | otherwise = True

insert :: Int -> Tree Int -> Tree Int
insert x Empty = Node x Empty Empty
insert x (Node y l r)
    | x < y = Node y (insert x l) r
    | x > y = Node y l (insert x r)
    | otherwise = Node y l r

Exercises

All exercises can be found in Set5a and Set5b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Optional:

The assignments of 5b are optional. Only make them if you want some extra practice on recursive datatypes, but trees will not be asked on the exam.

Exercises from 5b:

You can check your current points from the blue blob in the bottom-right corner of the page.