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:

  1. 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 Expressions, 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:

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

  1. null
  2. (cons 1 2)
  3. (cons null null)
  4. (cons (cons (cons 1 2) 3) null)
  5. (cdr (cons 1 (cons 2 (cons null null))))
  6. (cons (list 1 2 3) 4)