then
in the body of
f
,
x
will be 1,
y
will be 2, and
z
will be the list
(3 4 5 6)
. Given the definition
(define (g . w) )
the procedure
g
can be called with zero or more arguments. If we evaluate
(g 1 2 3 4 5 6)
then in the body of
g
,
w
will be the list
(1 2 3 4 5 6)
.
11
Use this notation to write a procedure
same-parity
that takes one or more integers and returns a
list of all the arguments that have the same even-odd parity as the first argument. For example,
(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)
Mapping over lists
One extremely useful operation is to apply some transformation to each element in a list and generate
the list of results. For instance, the following procedure scales each number in a list by a given factor:
(define (scale-list items factor)
(if (null? items)
nil
(cons (* (car items) factor)
(scale-list (cdr items) factor))))
(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)
We can abstract this general idea and capture it as a common pattern expressed as a higher-order
procedure, just as in section 1.3. The higher-order procedure here is called
map
.
Map
takes as
arguments a procedure of one argument and a list, and returns a list of the results produced by
applying the procedure to each element in the list:
12
(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))
(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)
(map (lambda (x) (* x x))
(list 1 2 3 4))
(1 4 9 16)
Now we can give a new definition of
scale-list
in terms of
map
:
(define (scale-list items factor)
(map (lambda (x) (* x factor))
items))
Map
is an important construct, not only because it captures a common pattern, but because it
establishes a higher level of abstraction in dealing with lists. In the original definition of
scale-list
, the recursive structure of the program draws attention to the element-by-element
processing of the list. Defining
scale-list
in terms of
map
suppresses that level of detail and
emphasizes that scaling transforms a list of elements to a list of results. The difference between the
two definitions is not that the computer is performing a different process (it isn’t) but that we think
about the process differently. In effect,
map
helps establish an abstraction barrier that isolates the
implementation of procedures that transform lists from the details of how the elements of the list are
extracted and combined. Like the barriers shown in figure 2.1, this abstraction gives us the flexibility
to change the low-level details of how sequences are implemented, while preserving the conceptual
framework of operations that transform sequences to sequences. Section 2.2.3 expands on this use of
sequences as a framework for organizing programs.
Exercise 2.21. The procedure
square-list
takes a list of numbers as argument and returns a list
of the squares of those numbers.
(square-list (list 1 2 3 4))
(1 4 9 16)
Here are two different definitions of
square-list
. Complete both of them by filling in the missing
expressions:
(define (square-list items)
(if (null? items)
nil
(cons <??> <??>)))
(define (square-list items)
(map <??> <??>))
Exercise 2.22. Louis Reasoner tries to rewrite the first
square-list
procedure of exercise 2.21 so
that it evolves an iterative process:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
(iter items nil))
Unfortunately, defining
square-list
this way produces the answer list in the reverse order of the
one desired. Why?
Louis then tries to fix his bug by interchanging the arguments to
cons
:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(square (car things))))))
(iter items nil))
This doesn’t work either. Explain.
Exercise 2.23. The procedure
for-each
is similar to
map
. It takes as
arguments a procedure and a
list of elements. However, rather than forming a list of the results,
for-each
just applies the
procedure to each of the elements in turn, from left to right. The values returned by applying the
procedure to the elements are not used at all --
for-each
is used with procedures that perform an
action, such as printing. For example,
(for-each (lambda (x) (newline) (display x))
(list 57 321 88))
57
321
88
The value returned by the call to
for-each
(not illustrated above) can be something arbitrary, such
as true. Give an implementation of
for-each
.
2.2.2 Hierarchical Structures
The representation of sequences in terms of lists generalizes naturally to represent sequences whose
elements may themselves be sequences. For example, we can regard the object
((1 2) 3 4)
constructed by
(cons (list 1 2) (list 3 4))
as a list of three items, the first of which is itself a list,
(1 2)
. Indeed, this is suggested by the form in
which the result is printed by the interpreter. Figure 2.5 shows the representation of this structure in
terms of pairs.
Figure 2.5: Structure formed by
(cons (list 1 2) (list 3 4))
.
Figure 2.5: Structure formed by
(cons (list 1 2) (list 3 4))
.
Another way to think of sequences whose elements are sequences is as trees. The elements of the
sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
Figure 2.6 shows the structure in figure 2.5 viewed as a tree.