# 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 `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 (17 September 2021)