# 4  Lists and Recursive Functions

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.

## 4.1  Little 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:

A list -- also known as `(Listof X)` -- is one of:
1. `null`

2. `(cons X L)` where `X` is any kind of value and `L` is a list.

This 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, `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.

## 4.2  Big Lists

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.

## 4.3  Lists and Recursion

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)  -->  N`
;; count the number of items on `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.

## 4.4  Our First Program with Lists

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.

 ```;; `Number Number  -->  true` (define (background-draw) (and (draw-solid-rect (make-posn 0 0) WIDTH HEIGHT BACKGROUND))) ;; Star = `Posn` ;; ` -->  Star` (define (star-create) (make-posn (random WIDTH) (random HEIGHT))) ;; `Star  -->  true` (define (star-paint s) (draw-solid-disk s STAR-RADIUS 'white)) ;; `Number  -->  (Listof Star)` (define (stars-create n) (cond [(= n 0) null] [else (cons (star-create) (stars-create (- n 1)))])) ;; `(Listof Star)  -->  true` (define (stars-paint s) (cond [(null? s) true] [else (and (star-paint (car s)) (stars-paint (cdr s)))])) (define STAR-RADIUS 1) (define WIDTH 110) (define HEIGHT 400) (define BACKGROUND 'blue) ``` Figure 4:  A Background for UFOs

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-number is 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.