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)
    [(null? alon) 0]
    [else (+ (car alon) (sum (cdr alon)))]))

;; Tests: 
(= (sum (cons 10 (cons -1 (cons 3 (cons 55 null)))))

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 "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:

list data def with arrow

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 constructed 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)
    [(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)
    [(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:

list data def with arrow

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

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)
    [(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)
    [(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)
    [(= n 0) null]
    [else (cons (star-create) (stars-create (- n 1)))]))

;; (Listof Star)  -->  true
(define (stars-paint s)
    [(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

  1. 0 or

  2. (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)
    [(= 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.