Introduction to Lists

In the next lessons, we will study the list datatype, the essential datatype of Haskell and functional programming in general. As lists are defined recursively themselves, they fit well to a language that uses recursion as its primary problem solving technique.

The list datatype

A list is a linear data structure for a collection of elements. Each element points to the next element, except the last element, which points to a special nil value (the empty list). Here is a visualization of a list containing the three numbers 1, 2, 3.

Just like tuples, we can make lists from any Haskell data type. List types are denoted using square brackets. A list of integers has the type [Int], a list of doubles the type [Double], and so on. To make list literals, we can simply enumerate values in square brackets. Here are some examples of lists:

ints :: [Int]
ints = [1, 2, 3]

empty :: [Int]
empty = []

functions :: [Int -> Int]
functions = [(+1), (*2)]

nested :: [[String]]
nested = [["hi"], ["how", "are", "you"], ["i'm", "fine"]]

As the examples show, we can make lists from any type, including function types and list types themselves (producing nested lists). Elements of one Haskell list must all have the same type. There can be no mixed lists of ints and doubles.

Lists in Haskell, like most types, are immutable, i.e., it is not possible to modify the values inside a list without creating a new list. But Haskell makes it easy to build new lists from existing ones.

Constructing lists

We can build lists element by element using its two data constructors [] and :.

• [] denotes the empty list. It can stand in for the empty list of any type (e.g., [Int] or [Double]).
• If x is an element of type a, and xs is a list of type [a], then l = x : xs is a list of type [a] as well. The first element of l is x, called the head of l. The rest of the list is xs, called the tail of l.

For example, we can write the list [1, 2, 3] as 1 : (2 : (3 : []))

• [] is the empty list
• 3 : [] is the list with head 3 and an empty tail. It is the singleton list [3]
• 2 : (3 : []) is the list with head 2 and tail 3 : []. It is the two element list [2, 3]
• 1 : (2 : (3 : [])) is the list with 1 as its head and 2 : (3 : []) at its tail. It is the three element list [1, 2, 3]

The : operator associates to the right, so we can also write the above list as 1 : 2 : 3 : [], which looks exactly like the visualization from above. In fact, the short form [1, 2, 3] is just syntactic sugar and internally will be translated into 1 : 2 : 3 : []. All Haskell lists are built from the empty list [] and the operator :, which is often called the cons operator.

Pattern matching on lists

To write functions operating on lists, we will again use pattern matching. There are two types of list patterns:

• The nil pattern []. It matches only the empty list.
• The cons pattern pattern_1 : pattern_2 where pattern_1 and pattern_2 are patterns themselves. It matches only non empty lists, where pattern_1 matches the head and pattern_2 matches the tail.

The patterns closely match the data constructors in syntax. Especially the cons pattern can be seen as a “data deconstructor” for lists since it splits a nonempty list into its head and tail component.

The most common use case of the cons pattern is to use pattern variables for both pattern_1 and pattern_2. By convention, the variable for the head is commonly called x, and the variable for the tail is called xs (read as a plural of x). This results in the pattern x : xs which matches every nonempty list. Here x will bind to the head of the list and xs will bind to its tail (which might be empty).

Let’s illustrate the use of these patterns by implementing a containsMatchingInt function. It takes a function test :: Int -> Bool and a list xs of integers. containsMatchingInt test xs should be True if some value of xs satisfies the predicate test, otherwise False.

containsMatchingInt :: (Int -> Bool) -> [Int] -> Bool

We will implement containsMatchingInt as a recursive function on the list argument. The base case is that the list is empty, which means that it cannot contain the value we are looking for.

containsMatchingInt _ [] = False

The recursive case is that the list is nonempty. Here, we can use a guarded equation to check if the head matches the predicate test, in which case we can return True. Otherwise, we need to continue checking the tail of the list with a recursive call to containsMatchingInt.

containsMatchingInt test (x:xs) | test x == True = True
                                | otherwise      = containsMatchingInt test xs

Syntax-wise, we need to use parentheses around the cons pattern on the left hand side. Here is the complete definition of containsMatchingInt:

Exercise: List patterns

Write a function intLength :: [Int] -> Int. It should return the length of the given list of integers. Implement intLength as a recursive function using pattern matching on the list.