Structure and Interpretation of Computer Programs

s

 is a sequence containing four sequences, 

((1 2 3) (4 5 6) (7 8 9) (10 11 12)),

then the value of 

(accumulate-n + 0 s)

 should be the sequence 

(22 26 30)

. Fill in the

missing expressions in the following definition of 

accumulate-n

: 

(define (accumulate-n op init seqs)

  (if (null? (car seqs))

      nil

      (cons (accumulate op init <??>)

            (accumulate-n op init <??>))))

Exercise 2.37.  Suppose we represent vectors v = (v

i

) as sequences of numbers, and matrices m = 

(m

ij

) as sequences of vectors (the rows of the matrix). For example, the matrix 

is represented as the sequence 

((1 2 3 4) (4 5 6 6) (6 7 8 9))

. With this representation,

we can use sequence operations to concisely express the basic matrix and vector operations. These

operations (which are described in any book on matrix algebra) are the following:

We can define the dot product as

17

 

(define (dot-product v w)

  (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations.

(The procedure 

accumulate-n

 is defined in exercise 2.36.) 

(define (matrix-*-vector m v)

  (map <??> m))

(define (transpose mat)

  (accumulate-n <??> <??> mat))

(define (matrix-*-matrix m n)

  (let ((cols (transpose n)))

    (map <??> m)))

Exercise 2.38.  The 

accumulate

 procedure is also known as 

fold-right

, because it combines

the first element of the sequence with the result of combining all the elements to the right. There is

also a 

fold-left

, which is similar to 

fold-right

, except that it combines elements working in

the opposite direction: 

---

(define (fold-left op initial sequence)

  (define (iter result rest)

    (if (null? rest)

        result

        (iter (op result (car rest))

              (cdr rest))))

  (iter initial sequence))

What are the values of 

(fold-right / 1 (list 1 2 3))

(fold-left / 1 (list 1 2 3))

(fold-right list nil (list 1 2 3))

(fold-left list nil (list 1 2 3))

Give a property that 

op

 should satisfy to guarantee that 

fold-right

 and 

fold-left

 will produce

the same values for any sequence. 

Exercise 2.39.   Complete the following definitions of 

reverse

 (exercise 2.18) in terms of 

fold-right

 and 

fold-left

 from exercise 2.38: 

(define (reverse sequence)

  (fold-right (lambda (x y) <??>) nil sequence))

(define (reverse sequence)

  (fold-left (lambda (x y) <??>) nil sequence))

Nested Mappings

We can extend the sequence paradigm to include many computations that are commonly expressed

using nested loops.

18

 Consider this problem: Given a positive integer n, find all ordered pairs of

distinct positive integers i and j, where 1< j< i< n, such that i + j is prime. For example, if n is 6, then

the pairs are the following: 

A natural way to organize this computation is to generate the sequence of all ordered pairs of positive

integers less than or equal to n, filter to select those pairs whose sum is prime, and then, for each pair 

(i, j) that passes through the filter, produce the triple (i,j,i + j).

Here is a way to generate the sequence of pairs: For each integer i< n, enumerate the integers j<i, and

for each such i and j generate the pair (i,j). In terms of sequence operations, we map along the

sequence 

(enumerate-interval 1 n)

. For each i in this sequence, we map along the sequence 

(enumerate-interval 1 (- i 1))

. For each j in this latter sequence, we generate the pair 

(list i j)

. This gives us a sequence of pairs for each i. Combining all the sequences for all the i

(by accumulating with 

append

) produces the required sequence of pairs:

19

 

(accumulate append

            nil

            (map (lambda (i)

                   (map (lambda (j) (list i j))

---

                        (enumerate-interval 1 (- i 1))))

                 (enumerate-interval 1 n)))

The combination of mapping and accumulating with 

append

 is so common in this sort of program

that we will isolate it as a separate procedure: 

(define (flatmap proc seq)

  (accumulate append nil (map proc seq)))

Now filter this sequence of pairs to find those whose sum is prime. The filter predicate is called for

each element of the sequence; its argument is a pair and it must extract the integers from the pair.

Thus, the predicate to apply to each element in the sequence is 

(define (prime-sum? pair)

  (prime? (+ (car pair) (cadr pair))))

Finally, generate the sequence of results by mapping over the filtered pairs using the following

procedure, which constructs a triple consisting of the two elements of the pair along with their sum: 

(define (make-pair-sum pair)

  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

Combining all these steps yields the complete procedure: 

(define (prime-sum-pairs n)

  (map make-pair-sum

       (filter prime-sum?

               (flatmap

                (lambda (i)

                  (map (lambda (j) (list i j))

                       (enumerate-interval 1 (- i 1))))

                (enumerate-interval 1 n)))))

Nested mappings are also useful for sequences other than those that enumerate intervals. Suppose we

wish to generate all the permutations of a set S; that is, all the ways of ordering the items in the set. For

instance, the permutations of {1,2,3} are {1,2,3}, { 1,3,2}, {2,1,3}, { 2,3,1}, { 3,1,2}, and { 3,2,1}.

Here is a plan for generating the permutations of S: For each item x in S, recursively generate the

sequence of permutations of S - x,

20

 and adjoin x to the front of each one. This yields, for each x in S,

the sequence of permutations of S that begin with x. Combining these sequences for all x gives all the

permutations of S:

21

(define (permutations s)

  (if (null? s)                    ; empty set?

      (list nil)                   ; sequence containing empty set

      (flatmap (lambda (x)

                 (map (lambda (p) (cons x p))

                      (permutations (remove x s))))

               s)))

Notice how this strategy reduces the problem of generating permutations of S to the problem of

generating the permutations of sets with fewer elements than S. In the terminal case, we work our way

down to the empty list, which represents a set of no elements. For this, we generate 

(list nil)

,

---