Scheme Programming/List Operations

Lists are a fundamental data structure in Scheme, as they are in many other functional languages. While among the simplest of structures, they have a rich set of operations and an amazing variety of uses. In this section, we'll cover the basics of creating and using lists.

Scheme Lists

A list is a sequence of elements ending with (), sometimes called the "empty list" or "nil". We can build up lists with cons, which attaches a new element to the head of a list:

> '()     ; The empty list must be quoted.
()
> (cons 3 '())
(3)
> (cons 2 (cons 3 '()))
(2 3)
> (cons #t (cons 2 (cons 3 '())))
(#t 2 3)

The first argument of cons may be any Scheme object, and the second is a list; the value of (cons x xs) is a new list which contains x followed by the elements of xs. (Scheme's way of printing lists uses a shorthand which hides the final (). In the responses above, we simply see the elements of a list enclosed in parentheses.) It's important to note that we must always quote (), in order to prevent Scheme from trying to interpret it as an (invalid) expression.

Two predicates define the Scheme list type. null?, is true for () (the empty list) and is false otherwise, while pair? returns true only for objects constructed with cons.

There are two basic functions for accessing the elements of lists. The first, car, extracts the first element of a list:

> (car (cons 1 '()))
1
> (car (cons 2 (cons 3 '())))
2
> (car '())
; Error!

Applying car to the empty list causes an error.

The second function, cdr, gives us the tail of a list: that is, the list without its leading element:

> (cdr (cons 1 '()))
()
> (cdr (cons 2 (cons 3 '())))
(3)
> (cdr '())
; Error!

As with car, trying to apply cdr to the empty list causes an error.

The three functions cons, car, and cdr satisfy some useful identities. For any Scheme object x and list xs, we have

(car (cons x xs)) = x
(cdr (cons x xs)) = xs

For any non-empty list ys, we also have

(cons (car ys) (cdr ys)) = ys

Clearly, building a list through successive cons operations is clumsy. Scheme provides the built-in function list which returns a list of its arguments:

> (list 1 2 3 4)
(1 2 3 4)
> (cons 1 (cons 2 (cons 3 (cons 4 '()))))  ; equivalent, but tedious
(1 2 3 4)

list can take any number of arguments.

We can write a range of useful functions using just cons, car, and cdr. For example, we can define a function to compute the length of a list:

(define (length xs)
  (if (null? xs)
      0
      (+ 1 (length (cdr xs)))))

This definition, like the definitions of most list operations, closely follows the recursive structure of a list. There is a case for the empty list (which is assigned the length 0), and a case for a non-empty list (the length of the tail of the list, plus one). In practice, Scheme provides length as a built-in function.

Here's another simple example:

(define (find-number n xs)
  (if (null? xs)
      #f
      (if (= n (car xs))
          #t
          (find-number n (cdr xs)))))

find-number returns #t if the argument n occurs in the list xs, and returns #f otherwise. Once again, this definition follows the structure of the list argument. The empty list has no elements, so (find-number n '()) is always false. If xs is non-empty, then n could be the first element, or it could be somewhere in the tail. In the former case, find-number returns true immediately. In the latter, the return value should be true if n appears in (cdr xs) and false otherwise. But since this is the definition of find-number itself, we have a recursive call with the new argument (cdr xs).