Lists are Scheme's most useful built-in class of data. A list is useful when we want to keep track of a number of pieces of data as one. A shopping list is one good example; a todo list is another one. As we shall see, lists are extremely versatile, and their usefulness far exceeds that of similar kinds of data. In this section, we introduce lists and recursive functions for processing them; in the next section, we discuss a few looping constructs for lists.

Lists and S-expressions are generated from one constant and one
constructor: `null`

and `cons`

. The former is a unique
value; it is a class by itself. A Scheme program can recognize
`null`

with the `null?`

predicate. The latter is a general
constructor function. It compounds any value and a list value into a
list.^{2} In
other words, the class of Scheme lists is defined as follows:

AThis definition refers to itself, but this is okay. If we think of it as a procedure that explains how to construct certain values, it works just fine. The first clause gets us started. The second clause keeps us going. For example,list-- also known as`(Listof X)`

-- is one of:

`null`

`(cons X L)`

where`X`

is any kind of value and`L`

is a list.

`5`

is a value and `null`

is a list, so
`(cons 5 null)`

is a list, too. And from there we can create ever
larger lists: `(cons 'a (cons 5 null))`

, ```
(cons #t (cons 'a
(cons 5 null)))
```

, and so on.
Clearly, `cons`

is just like a structure constructor, and from what
we have seen a `cons`

-structure has two fields. Before we can
process lists, we need to know how to access the two fields. The two
selectors are called `car`

and `rest`

. The predicate
`pair?`

recognizes `cons`

-structures.

**Note**: While `car`

and `cdr`

are the
traditional and widely used names for these functions, the Pretty Big
Scheme language also knows `first`

and `rest`

, which are much
better names. In addition, it recognizes `cons?`

for
`pair?`

, `empty?`

for `null?`

, and `empty`

for
`null`

.

With these list operations we can now define our first list processing function:

`;; ``(listof Number) --> Number`

;; to compute the sum of a list of numbers
(define (sum alon)
(cond
[(null? alon) 0]
[else (+ (car alon) (sum (cdr alon)))]))
;; Tests:
(= (sum (cons 10 (cons -1 (cons 3 (cons 55 null)))))
67)

Even a cursory glance shows that the layout of this function is similar to
the layout of the above definition of the class of lists. The data definition
consists of two clauses, and so does the function definition. The first
clause in the data definition talks about the empty list, and so does the
first clause in `sum`

's conditional. The second clause specifies a
`cons`

structure and refers to itself -- in both definitions.

The test shows how to run such programs. We construct a list with
`cons`

, step by step, and apply the function. The computation
proceeds just like one that involves numbers:

(sum (cons 10 (cons -1 (cons 3 (cons 55 null))))) = (+ (car (cons 10 (cons -1 (cons 3 (cons 55 null))))) (sum (cdr (cons 10 (cons -1 (cons 3 (cons 55 null))))))) = (+ 10 (sum (cons -1 (cons 3 (cons 55 null))))) = (+ 10 (+ -1 (sum (cons 3 (cons 55 null))))) = (+ 10 (+ -1 (+ 3 (sum (cons 55 null))))) = (+ 10 (+ -1 (+ 3 (+ 55 (sum null))))) = (+ 10 (+ -1 (+ 3 (+ 55 0)))) = 67

The novelty is that we need to know that `(car (cons X Y))`

is
`X`

and that `(cdr (cons X Y))`

is `Y`

no matter what
`X`

and `Y`

are. These laws correspond to the rules about
numbers that we know from first grade: 1 + 1 is 2, 2 * 2 is 4, and so on.
Choose one of the HtDP languages and use the stepper to experience
stepping first hand.

Using `cons`

to define large lists gets tiring fast. Hence, Scheme
provides `list`

, which is like `string`

and `vector`

:

(list #t 'a 5)

This expression constructs a list with three elements: a Boolean, a symbol, and a number. It's basically just an abbreviation for

(cons #t (cons 'a (cons 5 null)))

Lists, like vectors and structures, can also be nested:

(define authors (list (list "Matthias" "Boston" "Northeastern") (list "Robby" "Chicago" "University of Chicago") (list "Matthew" "Salt Lake City" "University of Utah") (list "Shriram" "Providence" "Brown University")))

This list consists of four lists, each of which consists of three strings. Using this nesting of lists, and possibly other values, a Scheme programmer can easily construct large values to represent complex pieces of information from the real world.

Once we use big lists, we also need functions for processing lists. Scheme
comes with a host of them: `append`

, which concatenates as many
lists as it is given; `length`

, which counts the number of items on
a list; `reverse`

, which produces the reverse of the given list;
`list-ref`

, which extracts items using an index;
`quick-sort`

, which constructs a sorted version of a given list;
and many more. Because of this library, we can already define many
functions without using recursion; the recursion in the built-in functions
suffices. Still, it is good to know how things work so we discuss this
first and then see how to simulate a ufo attack.

Writing functions for numbers, Booleans, characters and even strings looked easy, but writing functions for lists appears to be more intimating. Even the definition of the class of lists refers to itself:

Contrary to rumors that many people spread, this isn't actually a problem but a big help. It just takes a bit of practice, and after that, writing functions for lists is easier than writing loops in conventional languages. Promised.

As the discussion of `sum`

suggests, the organization of the data
definition suggests an organization for the function. If the function
consumes a list, it should probably distinguish between the `null`

list and the `cons`

tructed list, because the data definition does
this, too. Put differently, the function body is a **cond**-expression with two
clauses because the data definition consists of two clauses:

(define (function-for-lists a-list) (cond [(null? a-list) ...] [(pair? a-list) ...]))

Furthermore, while `null`

is just a constant, a `cons`

cell -- the traditional name for a `cons`

structure -- contains two
values: an `X`

and a `list`

. The function can extract those
values in the clause for `cons`

:

(define (function-for-lists a-list) (cond [(null? a-list) ...] [(pair? a-list) ... (car a-list) ... (cdr a-list) ...]))

Last but not least, the data definition refers to itself in the second
clause for the `cdr`

field of the `cons`

cell. This
suggests that the function should process the list in the `cdr`

field by calling itself recursively:

One way to understand this template is to think about it as a plan that enumerates all the ingredients that we know about list-processing functions. We're now ready to program because programming in Scheme means composing values to get the desired result.

Using the template, we can easily define many list-processing functions in an almost rote manner. To make this point perfectly clear, let us look at the definitions of a bunch of built-in functions:

The function

`length`

illustrates that not all the pieces from the template are always needed; it omits`(car l)`

.;;

`(Listof X) -->`

;; count the number of items on**N**`l`

(define (length l) (cond [(null? l) 0] [else (+ 1 (length (cdr l)))])) (= 0 (length null)) (= 2 (length (list 'a 'b)))The function

`last-pair`

shows how to omit an entire clause. Since the function doesn't really apply to non-empty lists, it calls`error`

in the`null`

clause.;;

`(Listof X) --> (list X)`

;; extract the last pair from`l`

(if there is one) (define (last-pair l) (cond [(null? l) (error 'last-pair "expected non-empty list")] [else (if (pair? (cdr l)) (last-pair (cdr l)) l)])) (equal? (list 'c) (last-pair (list 'a 'b 'c))) (equal? (list 9) (last-pair (list 1 2 3 4 5 6 7 9)))The function

`member`

produces either`#f`

or a list of items, indicating that it found the desired item. Otherwise it is a plain old instance of the template:;;

`X (Listof X) --> (union #f (Listof X))`

;; is`a`

a member of`l`

? (compare with`equal?`

) (define (member a l) (cond [(null? l) #f] [else (if (equal? a (car l)) l (member a (cdr l)))])) (not (member 0 (list 1 2 3))) (equal? (list 0 4 5) (member 0 (list 1 2 3 0 4 5))) (equal? (list (list 0) 4 5) (member (list 0) (list 1 2 3 (list 0) 4 5)))The function

`remove`

constructs a list from a given list, but its organization follows that of the template.;;

`X (Listof X) --> (Listof X)`

;; remove the first instance of`a`

from`l`

(compare with`equal?`

) (define (remove a l) (cond [(null? l) null] [else (if (equal? (car l) a) (cdr l) (cons (car l) (remove a (cdr l))))])) (equal? (list 1 2 3 5) (remove 4 (list 1 2 3 4 5))) (equal? (list 1 4 (list 2 3) 6) (remove (list 2 3) (list 1 (list 2 3) 4 (list 2 3) 6)))The function

`append`

consumes two lists -- the built-in function consumes as many as we want -- but only traverses the first one according to plan. Indeed, it doesn't even matter what the second argument is, which suggests that`replace-end-with`

is almost a better name for the function.;;

`(Listof X) (Listof X) --> (Listof X)`

;; juxtapose the items from`l1`

and`l2`

in a single list (define (append l1 l2) (cond [(null? l1) l2] [else (cons (car l1) (append (cdr l1) l2))])) (equal? (list 3) (append null (list 3))) (equal? (list 3) (append (list 3) null)) (equal? (list 'a 1 2) (append (list 'a) (list 1 2)))The function

`reverse`

is weird in that it uses the result of the recursive function call to build the final result. Although this is a perfectly fine function definition, it introduces some algorithmic inefficiencies that we should avoid. We discuss the function again, and its real definition in Scheme, later in section 10.;;

`(Listof X) --> (Listof X)`

;; produce a reversed version of`l`

(define (reverse l) (cond [(null? l) '()] [else (append (reverse (cdr l)) (list (car l)))])) (equal? (list 3 2 1) (reverse (list 1 2 3))) (equal? (list 'a (list 'b 'c)) (reverse (list (list 'b 'c) 'a)))

The above functions are built into Scheme. In most cases, they are even more powerful than indicated here. Consult the Help Desk for further information.

Figure 3:A UFO flying across the night sky

Figure 3 displays the flight of a UFO across a night sky. The UFO enters the picture at the top and, when it reaches the bottom, it stops and sits there. In section 3.5 we figured out how to simulate the flight per se. The one novel aspect of flying the UFO is that it lands:

;;`UFO (Listof Star) --> true`

;; fly UFO until it has landed (define (run b s) (cond [(ufo-landed? b) (ufo-paint b)] [else (and (one-moment b s) (run (ufo-move b) s))])) ;;`UFO --> true`

;; had the ufo reached the bottom of the canvas yet (define (ufo-landed? u) (>= (posn-y (ufo-pos u)) HEIGHT))

As before, `run`

deals with one moment and then repeats
itself. Unlike the original version, however, it stops when the UFO has
landed. Naturally, landing is just a condition and, if it is true,
`run`

paints the UFO and doesn't repeat itself. Adding other stop
conditions is trivial now:

`;; ``UFO (Listof Star) (Listof Shots) --> true`

;; fly UFO until it has landed
(define (run b s shots)
(cond
[(ufo-landed? b) (ufo-paint b)]
[(shot-hit-ufo? b shots) (ufo-explodes b)]
[(meteorite-collides-with-ufo? b (detect-meteorite)) (ufo-disappears b)]
[else (and (one-moment b s) (run (ufo-move b) s))]))

But we're getting ahead of ourselves. Let's do the background first.

The background is no longer a solid color but a bunch of stars sprinkled
across the blue sky. Representing and keep track of these stars suggests
using a list. But first we need to agree on the representation of
stars. Given that stars are just little dots in the sky, a `Posn`

is
a good representation. When we create such a star, we place it at random
place on the canvas. To do so we need the shape of the canvas and a function
for picking random numbers on that canvas. For the former we use constants,
and for the latter, we use `(random n)`

, which picks a different
number from `0`

, `...`, `n - 1`

every time it is evaluated.

To create the background, we use lists of stars. Painting such a list is
easy. Following the usual template, we process each star in the list with
`star-paint`

, and that's that; see the definition of stars-paint in
figure 4. Creating such a list requires a moment of
thought and a hint:

A natural-numberis either

`0`

or

`(add1 n)`

if`n`

is a natural number.

If this is the definition for a natural number, then a function that processes natural numbers must have this shape:

(define (fun-for-natural-number n) (cond [(= n 0) ...] [else ... (fun-for-natural-number (- n 1)) ... ]))

Why? Because the data definition contains two clauses; because one of them
is concerned with `0`

; and the other one adds `1`

to some
number. Now compare this template to the definition of `create-stars`

in figure 4. Starting from the template, it is easy
to define any function that goes through recursive kinds of data.

^{2} This is a lie, but the truth doesn't matter for now.