# 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 `i`

th 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)