# 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"
7
'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]
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 `:`.

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)