# 5.3 Lists

In the previous section, we saw how to construct arbitrarily
large tuples from Pairs. This way of managing data is not very
satisfying since it requires defining different procedures for
constructing and accessing elements of every length tuple. For many
applications, we want to be able to manage data of any length such as
all the items in a web store, or all the bids on a given item. Since the
number of components in these objects can change, it would be very
painful to need to define a new tuple type every time an item is added.
We need a data type that can hold *any* number of items.

This definition almost provides what we need:

- An
*any-uple*is a Pair whose second cell is an*any-uple*.

This seems to allow an *any-uple* to contain any number of elements. The
problem is we have no stopping point. With only the definition above,
there is no way to construct an *any-uple* without already having one.

The situation is similar to defining *MoreDigits* as zero or more digits in Chapter 2, defining *MoreExpressions* in the
Scheme grammar in Chapter 3 as zero or more
*Expression*s, and recursive composition in Chapter 4.

Recall the grammar rules for *MoreExpressions*:

*MoreExpressions* ::$\Rightarrow $ *MoreExpressions*

*MoreExpressions* ::$\Rightarrow $ $\epsilon$

The rule for constructing an *any-uple* is analogous to the first
*MoreExpression* replacement rule. To allow an *any-uple* to be
constructed, we also need a construction rule similar to the second
rule, where *MoreExpression* can be replaced with nothing. Since it is
hard to type and read nothing in a program, Scheme has a name for this
value: *null*.

DrRacket will print out the value of `null`

as `()`

. It is also known as
the *empty list*, since it represents the List containing no elements.
The built-in procedure `null?`

takes one input parameter and evaluates
to `true`

if and only if the value of that parameter is `null`

.null?

Using `null`

, we can now define a *List*:

- A
*List*is either (1) null or (2) a Pair whose second cell is a*List*.

Symbolically, we define a List as:

*List* ::$\Rightarrow$ null

*List* ::$\Rightarrow$ `(cons Value List)`

These two rules define a List as a data structure that can contain any
number of elements. Starting from `null`

, we can create Lists of any
length:

`null`

evaluates to a List containing no elements.`(cons 1 null)`

evaluates to a List containing one element.`(cons 1 (cons 2 null))`

evaluates to a List containing two elements.`(cons 1 (cons 2 (cons 3 null)))`

evaluates to a 3-element List.

Scheme provides a convenient procedure, `list`

, for constructing a List.
The `list`

procedure takes zero or more inputs, and evaluates to a List
containing those inputs in order. The following expressions are
equivalent to the corresponding expressions above: `(list)`

, `(list 1)`

,
`(list 1 2)`

, and `(list 1 2 3)`

.

Lists are just a collection of Pairs, so we can draw a List using the
same box and arrow notation we used to draw structures created with
Pairs. Here is the structure resulting from `(list 1 2 3)`

:

There are three Pairs in the List, the second cell of each Pair is a
List. For the third Pair, the second cell is the List `null`

, which we
draw as a slash through the final cell in the diagram.

Table 5.1 summarizes some of the built-in procedures for manipulating Pairs and Lists.

Type | Output | |
---|---|---|

`cons` |
Value $\times $ Value $\rightarrow $ Pair | a Pair consisting of the two inputs |

`car` |
Pair $\rightarrow $ Value | the first cell of the input Pair |

`cdr` |
Pair $\rightarrow $ Value | the second cell of the input Pair |

`list` |
zero or more Values $\rightarrow $ List | a List containing the inputs |

`null?` |
Value $\rightarrow $ Boolean | `true` if the input is `null` , otherwise `false` |

`pair?` |
Value $\rightarrow $ Boolean | `true` if the input is a Pair, otherwise `false` |

`list?` |
Value $\rightarrow $ Boolean | `true` if the input is a List, otherwise `false` |

**Table 5.1**: Selected Built-In Scheme Procedures for Lists and Pairs.

Exercise 5.10. For each of the following expressions, explain whether
or not the expression evaluates to a List. Check your answers with a
Scheme interpreter by using the `list?`

procedure.

`null`

`(cons 1 2)`

`(cons null null)`

`(cons (cons (cons 1 2) 3) null)`

`(cdr (cons 1 (cons 2 (cons null null))))`

`(cons (list 1 2 3) 4)`