Unit 2: Lists

Introduction

The most important datatype in any functional programming language is the list. A list is a linearly ordered collection of elements. All the elements of a list must be of the same type. The easiest way in which to specify a list is by enumeration: you simply write the elements of the list between square brackets and separate them with commas. Here are some examples with their types:

[3, 7, 5, 88] :: [Int]
[[2, 3], [4, 8, 17]] :: [[Int]]
['t', 'i', 'm', 'e'] :: [Char]
"time" :: [Char]

Note that the last two of these are equivalent. The empty list, written [], belongs to type [a]. Haskell has a means of producing lists of integers in arithmetical progression. A few examples should make clear how this is achieved:

ghci> [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
ghci> [3, 5 .. 11]
[3,5,7,9,11]
ghci> [(-9), (-7) .. (-3)]
[-9,-7,-5,-3]

Because Haskell is a lazy functional programming language it can handle infinite lists. Here are some examples:

nats  = [1 .. ]
evens = [2, 4 .. ]
negs  = [(-1), (-2) .. ]
ones  = 1:ones
stars = '*':stars

Haskell provides several list operators. Some are: : (binary infix), which sticks an element at the front of a list, head (unary prefix), which extracts the first element of a non-empty list, tail (unary prefix), which returns the tail of a non-empty list, that is to say, the list of all the elements except the first, length (unary prefix), which returns the length of a list and !! (binary infix), which extracts an element of a list. Note that this list indexing operator treats the first element of a list as occupying position 0. Some examples of these operators in action should make it clear what they do:

ghci> 'f':"ear"
"fear"
ghci> head [7, 18, 3]
7
ghci> head "Harvard"
'H'
ghci> tail [7, 18, 3]
[18,3]
ghci> tail "Harvard"
"arvard"
ghci> length "time"
4
ghci> length [8, 1, 4, 5, 2]
5
ghci> "time" !! 2
'm'
ghci> [1, 2, 3, 4] !! 0
1

These operators have the following types:

(:)    :: a -> [a] -> [a]
head   :: [a] -> a
tail   :: [a] -> [a]
length :: [a] -> Int
(!!)   :: [a] -> Int -> a

Note that (head xs):(tail xs) is the same as xs except when xs is the empty list. Note also that every list can be represented using the cons operator and the empty list. For example, [2, 8, 13] can be depicted as 2:8:13:[]; there's no need to add parentheses as cons associates to the right.

Defining functions that operate on lists

A function to sum the elements of a list of integers can be defined like this:

sum :: Integral a => [a] -> [a]
sum ys
  | ys == []  = 0
  | otherwise = head ys + sum (tail ys)

It is better, however, to use pattern-matching thus:

sum :: Integral a => [a] -> [a] 
sum []     = 0
sum (y:ys) = y + sum ys

Here, the patterns are [] and (y:ys). In dealing with lists a pattern can contain variables and any number of occurrences of the empty list and the cons operator :. The function sum is actually defined in the Haskell Prelude; the above definitions are just presented here as examples.

List addition and subtraction

Two useful binary infix functions on lists are ++ (list addition) and \\ (list subtraction). In talking about the operator ++, various idioms are used. People talk about joining two lists together or concatenating them. The operator ++ itself is often called append. These days, list subtraction is more usually called list difference.

List addition takes two lists as its arguments and sticks them together. List subtraction removes elements from a list, for example: [1, 2, 3, 4, 5] \\ [1, 4] is equivalent to [2, 3, 5], [1, 1, 1, 1] \\ [1, 4] is equivalent to [1, 1, 1] and [1, 1, 1, 1] \\ [1, 1] is equivalent to [1, 1]. List difference is not included in the standard Prelude. If you want to use it, you need to include the library of functions Data.List which you do as follows:

ghci> import Data.List
ghci> [1,8,77,11] \\ [77]
[1,8,11]

You can also add import Data.List to any file you load into GHCi.

Memoisation

In mathematics the Fibonacci numbers are usually defined like this:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib i = fib (i - 1) + fib (i - 2)

Although this works in Haskell, it is extremely inefficient. A more efficient definition prevents the re-evaluation of the same Fibonacci number. The values are stored in a list. The definition is as follows:

fib :: Integer -> Integer
fib j   = fiblist !! j
fiblist = map f [ 0 .. ]
          where f 0 = 0
                f 1 = 1
                f i = fiblist !! (i - 1) + fiblist !! (i - 2)

Intuitively, fiblist contains the infinite list of Fibonacci numbers. Each element, say the ith, can be expressed in at least two ways, namely as fib i and as fiblist !! i. This version of the Fibonacci numbers is very much more efficient.