Be careful not
to confuse the expression
(list 1 2 3 4)
with the list
(1 2 3 4)
, which is the
result obtained when the expression is evaluated. Attempting to evaluate the expression
(1 2 3 4)
will signal an error when the interpreter tries to apply the procedure
1
to arguments
2
,
3
, and
4
.
We can think of
car
as selecting the first item in the list, and of
cdr
as
selecting the sublist
consisting of all but the first item. Nested applications of
car
and
cdr
can be used to extract the
second, third, and subsequent items in the list.
9
The constructor
cons
makes a list like the original
one, but with an additional item at the beginning.
(car one-through-four)
1
(cdr one-through-four)
(2 3 4)
(car (cdr one-through-four))
2
(cons 10 one-through-four)
(10 1 2 3 4)
(cons 5 one-through-four)
(5 1 2 3 4)
The value of
nil
, used to terminate the chain of pairs, can be thought of as a sequence of no elements,
the
empty list.
The word nil is a contraction of the Latin word
nihil, which means ‘‘nothing.’’
10
List operations
The use of pairs to represent sequences of elements as lists is accompanied by conventional
programming techniques for manipulating lists by successively ‘‘
cdr
ing down’’ the lists. For
example, the procedure
list-ref
takes as arguments a list and a number
n and returns the
nth item
of the list. It is customary to number the elements of the list beginning with 0. The method for
computing
list-ref
is the following:
For n = 0,
list-ref
should return the
car
of the list.
Otherwise,
list-ref
should return the (
n - 1)st
item of the
cdr
of the list.
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))
(list-ref squares 3)
16
Often we
cdr
down the whole list. To aid in this, Scheme includes a primitive predicate
null?
,
which tests whether its argument is the empty list. The procedure
length
, which returns the number
of items in a list, illustrates this typical pattern of use:
(define (length items)
(if (null? items)
0
(+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))
(length odds)
4
The
length
procedure implements a simple recursive plan. The reduction step is:
The
length
of any list is 1 plus the
length
of the
cdr
of the list.
This is applied successively until we reach the base case:
The
length
of the empty list is 0.
We could also compute
length
in an iterative style:
(define (length items)
(define (length-iter a count)
(if (null? a)
count
(length-iter (cdr a) (+ 1 count))))
(length-iter items 0))
Another conventional programming technique is to ‘‘
cons
up’’ an answer list while
cdr
ing down a
list, as in the procedure
append
, which takes two lists as arguments and combines their elements to
make a new list:
(append squares odds)
(1 4 9 16 25 1 3 5 7)
(append odds squares)
(1 3 5 7 1 4 9 16 25)
Append
is also implemented using a recursive plan. To
append
lists
list1
and
list2
, do the
following:
If
list1
is the empty list, then the result is just
list2
.
Otherwise,
append
the
cdr
of
list1
and
list2
, and
cons
the
car
of
list1
onto the
result:
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))
Exercise 2.17. Define a procedure
last-pair
that returns the list that contains only the last
element of a given (nonempty) list:
(last-pair (list 23 72 149 34))
(34)
Exercise 2.18. Define a procedure
reverse
that takes a list as argument and returns a list of the
same elements in reverse order:
(reverse (list 1 4 9 16 25))
(25 16 9 4 1)
Exercise 2.19. Consider the change-counting program of section 1.2.2. It would be nice to be able to
easily change the currency used by the program, so that we could compute the number of ways to
change a British pound, for example. As the program is written, the knowledge of the currency is
distributed partly into the procedure
first-denomination
and partly into the procedure
count-change
(which knows that there are five kinds of U.S. coins). It would be nicer to be able to
supply a list of coins to be used for making change.
We want to rewrite the procedure
cc
so that its second argument is a list of the values of the coins to
use rather than an integer specifying which coins to use. We could then have lists that defined each
kind of currency:
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))
We could then call
cc
as follows:
(cc 100 us-coins)
292
To do this will require changing the program
cc
somewhat. It will still have the same form, but it will
access its second argument differently, as follows:
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else
(+ (cc amount
(except-first-denomination coin-values))
(cc (- amount
(first-denomination coin-values))
coin-values)))))
Define the procedures
first-denomination
,
except-first-denomination
, and
no-more?
in terms of primitive operations on list structures. Does the order of the list
coin-values
affect the answer produced by
cc
? Why or why not?
Exercise 2.20. The procedures
+
,
*
, and
list
take arbitrary numbers of arguments. One way to
define such procedures is to use
define
with
dotted-tail notation. In a procedure definition, a
parameter list that has a dot before the last parameter name indicates that, when the procedure is
called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final
parameter’s value will be a list of any remaining arguments. For instance, given the definition
(define (f x y . z) )
the procedure
f
can be called with two or more arguments. If we evaluate
(f 1 2 3 4 5 6)