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.
A list is a sequence of elements ending with
(), sometimes called
the "empty list" or "nil". We can build up lists with
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
x followed by the elements of
xs. (Scheme's way of
printing lists uses a shorthand which hides the final
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)
Two predicates define the Scheme list type.
is true for
() (the empty list) and is false otherwise, while
pair? returns true only for objects constructed with
There are two basic functions for accessing the elements of lists. The first,
extracts the first element of a list:
> (car (cons 1 '())) 1 > (car (cons 2 (cons 3 '()))) 2 > (car '()) ; Error!
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!
car, trying to apply
cdr to the empty list causes an error.
The three functions
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
is clumsy. Scheme provides the built-in function
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
cdr. For example, we can define a function to compute the length of
(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)))))
#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,
(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
and false otherwise. But since this is the definition of
itself, we have a recursive call with the new argument
is a simplified account which is correct for our current purposes. In fact,
consconstructs pairs of its arguments, both of which may be arbitrary Scheme objects. A pair whose second element is
()or another pair is called a list; all other pairs are called improper.
- The definition of the Scheme list type is
looser than that of numbers, booleans, etc.
While the (scheme list) library provides a true
list?function, this function is defined in terms of
pair?. See the previous note.