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:

Prelude> [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> [3, 5 .. 11]
[3,5,7,9,11]
Prelude> [(-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:

Prelude> 'f':"ear"
"fear"
Prelude> head [7, 18, 3]
7
Prelude> head "Harvard"
'H'
Prelude> tail [7, 18, 3]
[18,3]
Prelude> tail "Harvard"
"arvard"
Prelude> length "time"
4
Prelude> length [8, 1, 4, 5, 2]
5
Prelude> "time" !! 2
'm'
Prelude> [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 :.

List addition and subtraction

Two useful binary infix functions on lists are ++ (list addition) and \\ (list subtraction). 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 subtraction is not predefined in the version of Haskell used here, but it can be defined like this:

(\\) :: Eq a => [a] -> [a] -> [a]
[] \\ _  = []
xs \\ [] = xs
(x:xs) \\ (y:ys)
  | x == y    = xs \\ ys
  | otherwise = (x : (xs \\ [y])) \\ ys

Memoisation

In mathematics the Fibonacci numbers are usually defined like this:

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 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.

© Antoni Diller (30 May 2016)