Structure and Interpretation of Computer Programs

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.

---