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