SICP Section 2.2 Hierarchical Data and the Closure Property - Part 1

Exercise 2.17. Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

1. (last-pair (list 23 72 149 34))  
2. (34)  

(last-pair (list 23 72 149 34)) (34)
Answer: This solution uses the length and list-ref functions described in the text. Here is a simpler solution which does not use length or list-ref.

view plainprint?

1. (define (last-pair items)  
2.   (cond ((null? items) '())  
3.         ((null? (cdr items)) items)  
4.         (else (last-pair (cdr items)))))  

(define (last-pair items) (cond ((null? items) '()) ((null? (cdr items)) items) (else (last-pair (cdr items)))))
Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

1. (reverse (list 1 4 9 16 25))  
2. (25 16 9 4 1)  

(reverse (list 1 4 9 16 25)) (25 16 9 4 1)
Answer:

view plainprint?

1. (define (reverse items)  
2.   (if (null? items)  
3.       '()  
4.       (append (reverse (cdr items)) (list (car items)))))  

(define (reverse items) (if (null? items) '() (append (reverse (cdr items)) (list (car items)))))
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:

view plainprint?

1. (define us-coins (list 50 25 10 5 1))  
2. (define uk-coins (list 100 50 20 10 5 2 1 0.5))  

(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:

1. (cc 100 us-coins)  
2. 292  

(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:

view plainprint?

1. (define (cc amount coin-values)  
2.   (cond ((= amount 0) 1)  
3.         ((or (< amount 0) (no-more? coin-values)) 0)  
4.         (else  
5.          (+ (cc amount  
6.                 (except-first-denomination coin-values))  
7.             (cc (- amount  
8.                    (first-denomination coin-values))  
9.                 coin-values)))))  

(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?

Answer:

view plainprint?

1. (define (first-denomination coin-values)  
2.   (car coin-values))    
3.   
4. (define (except-first-denomination coin-values)  
5.   (cdr coin-values))  
6.   
7. (define (no-more? coin-values)  
8.   (null? coin-values))  

(define (first-denomination coin-values) (car coin-values)) (define (except-first-denomination coin-values) (cdr coin-values)) (define (no-more? coin-values) (null? coin-values))
Order of the list coin-values will not matter. This owes to the way cc is structured. The first recursive call to cc tries to compare the amount with *all* denominations irrespective of their order in the list.

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

view plainprint?

1. (define (f x y . z) <body>)  

(define (f x y . z) <body>)
the procedure f can be called with two or more arguments. If we evaluate

1. (f 1 2 3 4 5 6)  

(f 1 2 3 4 5 6)
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

view plainprint?

1. (define (g . w) <body>)  

(define (g . w) <body>)
the procedure g can be called with zero or more arguments. If we evaluate

1. (g 1 2 3 4 5 6)  

(g 1 2 3 4 5 6)
then in the body of g, w will be the list (1 2 3 4 5 6).

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,

1. (same-parity 1 2 3 4 5 6 7)  
2. (1 3 5 7)  
3.   
4. (same-parity 2 3 4 5 6 7)  
5. (2 4 6)  

(same-parity 1 2 3 4 5 6 7) (1 3 5 7) (same-parity 2 3 4 5 6 7) (2 4 6)
Answer:

view plainprint?

1. (define (same-parity . items)  
2.   (define (parity-type n)  
3.     (if (= (modulo n 2) 0) even? odd?))  
4.     
5.   (define (iter has-expected-parity? items result)  
6.     (if (null? items)  
7.         result  
8.         (let ((first (car items))  
9.               (rest  (cdr items)))  
10.           (if (has-expected-parity? first)  
11.               (iter has-expected-parity? rest (append result (list first)))  
12.               (iter has-expected-parity? rest result)))))  
13.     
14.   (iter (parity-type (car items)) items '()))  

(define (same-parity . items) (define (parity-type n) (if (= (modulo n 2) 0) even? odd?)) (define (iter has-expected-parity? items result) (if (null? items) result (let ((first (car items)) (rest (cdr items))) (if (has-expected-parity? first) (iter has-expected-parity? rest (append result (list first))) (iter has-expected-parity? rest result))))) (iter (parity-type (car items)) items '()))
Exercise 2.21. The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.

1. (square-list (list 1 2 3 4))  
2. (1 4 9 16)  

(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:

view plainprint?

1. (define (square-list items)  
2.   (if (null? items)  
3.       nil  
4.       (cons <??> <??>)))  
5. (define (square-list items)  
6.   (map <??> <??>))  

(define (square-list items) (if (null? items) nil (cons <??> <??>))) (define (square-list items) (map <??> <??>))
Answer:

view plainprint?

1. (define (square-list items)  
2.   (if (null? items)  
3.       '()  
4.       (cons (* (car items) (car items)) (square-list (cdr items)))))  
5.   
6. (define (square-list items)  
7.   (map (lambda (x) (* x x)) items))  

(define (square-list items) (if (null? items) '() (cons (* (car items) (car items)) (square-list (cdr items))))) (define (square-list items) (map (lambda (x) (* x x)) items))
Exercise 2.22. Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:

view plainprint?

1. (define (square-list items)  
2.   (define (iter things answer)  
3.     (if (null? things)  
4.         answer  
5.         (iter (cdr things)   
6.               (cons (square (car things))  
7.                     answer))))  
8.   (iter items nil))  

(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:

view plainprint?

1. (define (square-list items)  
2.   (define (iter things answer)  
3.     (if (null? things)  
4.         answer  
5.         (iter (cdr things)  
6.               (cons answer  
7.                     (square (car things))))))  
8.   (iter items nil))  

(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.

Answer: In the first procedure iter starts by attaching the first item from the input list to answers. Subsequent items are consed to answers, thereby ending up *before* the first. Hence answers ends up having the square of the items in reverse order.

The second approach tried by Louis gets the order right. However the end result is not a plain list as he expects. Here the cons operation starts by attaching the empty answer list to the square of the first item. This yields (() . 1) and not (1). Further iterations repeat the same operation with similar results.

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,

view plainprint?

1. (for-each (lambda (x) (newline) (display x))  
2.           (list 57 321 88))  
3. 57  
4. 321  
5. 88  

(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.

Answer:

view plainprint?

1. (define (for-each proc items)  
2.   (cond ((not (null? items))  
3.          (proc (car items))  
4.          (for-each proc (cdr items)))))  

(define (for-each proc items) (cond ((not (null? items)) (proc (car items)) (for-each proc (cdr items)))))
Exercise 2.24. Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6). Answer: The interpreter prints (1 (2 (3 4))). I'll add the pictures once I draw them out using GIMP.

Exercise 2.25. Give combinations of cars and cdrs that will pick 7 from each of the following lists:

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

(1 3 (5 7) 9) ((7)) (1 (2 (3 (4 (5 (6 7))))))
Answer:

view plainprint?

1. (define x '(1 3 (5 7) 9))  
2. (car (cdr (car (cdr (cdr x)))))  
3. 7  
4.   
5. (define x '((7)))  
6. (car (car x))  
7. 7  
8.   
9. (define x '(1 (2 (3 (4 (5 (6 7)))))))  
10. (cadr (cadr (cadr (cadr (cadr (cadr x))))))  
11. 7  

(define x '(1 3 (5 7) 9)) (car (cdr (car (cdr (cdr x))))) 7 (define x '((7))) (car (car x)) 7 (define x '(1 (2 (3 (4 (5 (6 7))))))) (cadr (cadr (cadr (cadr (cadr (cadr x)))))) 7
Exercise 2.26. Suppose we define x and y to be two lists:

view plainprint?

1. (define x (list 1 2 3))  
2. (define y (list 4 5 6))  

(define x (list 1 2 3)) (define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of the following expressions:

view plainprint?

1. (append x y)  
2.   
3. (cons x y)  
4.   
5. (list x y)  

(append x y) (cons x y) (list x y)
Answer:

view plainprint?

1. (append x y)  
2. (1 2 3 4 5 6)  
3.   
4. (cons x y)  
5. ((1 2 3)  4 5 6)  
6.   
7. (list x y)  
8. ((1 2 3) (4 5 6))  

(append x y) (1 2 3 4 5 6) (cons x y) ((1 2 3) 4 5 6) (list x y) ((1 2 3) (4 5 6))
Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

view plainprint?

1. (define x (list (list 1 2) (list 3 4)))  
2.   
3. x  
4. ((1 2) (3 4))  
5.   
6. (reverse x)  
7. ((3 4) (1 2))  
8.   
9. (deep-reverse x)  
10. ((4 3) (2 1))  

(define x (list (list 1 2) (list 3 4))) x ((1 2) (3 4)) (reverse x) ((3 4) (1 2)) (deep-reverse x) ((4 3) (2 1))
Answer:

view plainprint?

1. (define (deep-reverse tree)  
2.   (cond ((null? tree)  
3.          nil)  
4.         ((pair? (car tree))  
5.          (append (deep-reverse (cdr tree))  
6.                  (list (deep-reverse (car tree)))))  
7.         (else  
8.          (append (deep-reverse (cdr tree))  
9.                  (list (car tree))))))  
10.   
11. (deep-reverse (list (list 1 2) (list 3 4)))  
12. ((4 3) (2 1))  

(define (deep-reverse tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (deep-reverse (cdr tree)) (list (deep-reverse (car tree))))) (else (append (deep-reverse (cdr tree)) (list (car tree)))))) (deep-reverse (list (list 1 2) (list 3 4))) ((4 3) (2 1))
Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

view plainprint?

1. (define x (list (list 1 2) (list 3 4)))  
2.   
3. (fringe x)  
4. (1 2 3 4)  
5.   
6. (fringe (list x x))  
7. (1 2 3 4 1 2 3 4)  

(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
Answer:

view plainprint?

1. (define (fringe tree)  
2.   (cond ((null? tree)  
3.          nil)  
4.           
5.         ((pair? (car tree))  
6.          (append (fringe (car tree))  
7.                  (fringe (cdr tree))))  
8.           
9.         (else  
10.          (append (list (car tree))  
11.                  (fringe (cdr tree))))))  

(define (fringe tree) (cond ((null? tree) nil) ((pair? (car tree)) (append (fringe (car tree)) (fringe (cdr tree)))) (else (append (list (car tree)) (fringe (cdr tree))))))
Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

view plainprint?

1. (define (make-mobile left right)  
2.   (list left right))  

(define (make-mobile left right) (list left right))
A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

view plainprint?

1. (define (make-branch length structure)  
2.   (list length structure))  

(define (make-branch length structure) (list length structure))
a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

d. Suppose we change the representation of mobiles so that the constructors are

view plainprint?

1. (define (make-mobile left right)  
2.   (cons left right))  
3. (define (make-branch length structure)  
4.   (cons length structure))  

(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))
How much do you need to change your programs to convert to the new representation?

Answer: a. As the mobile is represented as a list the selectors are straight forward to implement.

view plainprint?

1. ;; (a) Selectors  
2. (define (left-branch mobile)  
3.   (car mobile))  
4.   
5. (define (right-branch mobile)  
6.   (car (cdr mobile)))  
7.   
8. (define (branch-length branch)  
9.   (car branch))  
10.   
11. (define (branch-structure branch)  
12.   (car (cdr branch)))  

;; (a) Selectors (define (left-branch mobile) (car mobile)) (define (right-branch mobile) (car (cdr mobile))) (define (branch-length branch) (car branch)) (define (branch-structure branch) (car (cdr branch)))
b. Calculation of total weight is made easier by an utility procedure which calculates the weight of a given branch. These procedure use mutual recursion to calculate the total weight of a given mobile.

view plainprint?

1. ;; (b) total-weight  
2. (define (branch-weight branch)  
3.   (if (pair? (branch-structure branch))  
4.       (total-weight (branch-structure branch))  
5.       (branch-structure branch)))  
6.   
7. (define (total-weight mobile)  
8.   (+ (branch-weight (left-branch mobile))  
9.      (branch-weight (right-branch mobile))))  

;; (b) total-weight (define (branch-weight branch) (if (pair? (branch-structure branch)) (total-weight (branch-structure branch)) (branch-structure branch))) (define (total-weight mobile) (+ (branch-weight (left-branch mobile)) (branch-weight (right-branch mobile))))
c. The test to find out if a mobile is balanced can be similarly written with the help of an utility procedure to find out if its sub-mobiles are balanced.

view plainprint?

1. ;; (c) balanced?  
2. (define (balanced? mobile)  
3.   (let ((left  (left-branch mobile))  
4.         (right (right-branch mobile)))  
5.     (and   
6.      (= (torque left) (torque right))  
7.      (submobiles-balanced? left)  
8.      (submobiles-balanced? right))))  
9.   
10. (define (torque branch)  
11.   (* (branch-length branch) (branch-weight branch)))  
12.   
13. (define (submobiles-balanced? branch)  
14.   (let ((structure (branch-structure branch)))  
15.     (or (not (pair? structure))  
16.         (balanced? structure))))  

;; (c) balanced? (define (balanced? mobile) (let ((left (left-branch mobile)) (right (right-branch mobile))) (and (= (torque left) (torque right)) (submobiles-balanced? left) (submobiles-balanced? right)))) (define (torque branch) (* (branch-length branch) (branch-weight branch))) (define (submobiles-balanced? branch) (let ((structure (branch-structure branch))) (or (not (pair? structure)) (balanced? structure))))
d. Only the selectors need to be changed. For instance the right-branch can use (cdr mobile) instead of (car (cadr mobile)).

Exercise 2.30. Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:

1. (square-tree  
2.  (list 1  
3.        (list 2 (list 3 4) 5)  
4.        (list 6 7)))  
5. (1 (4 (9 16) 25) (36 49))  

(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))
Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

Answer:

view plainprint?

1. (define (square-tree tree)  
2.   (cond ((null? tree)  
3.          nil)  
4.         ((not (pair? tree))  
5.          (* tree tree))  
6.         (else  
7.          (cons (square-tree (car tree))  
8.                (square-tree (cdr tree))))))  
9.   
10. ;; using map  
11. (define (square-tree tree)  
12.   (map (lambda (sub-tree)  
13.          (if (pair? sub-tree)  
14.              (square-tree sub-tree)  
15.              (* sub-tree sub-tree)))  
16.        tree))  

(define (square-tree tree) (cond ((null? tree) nil) ((not (pair? tree)) (* tree tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree)))))) ;; using map (define (square-tree tree) (map (lambda (sub-tree) (if (pair? sub-tree) (square-tree sub-tree) (* sub-tree sub-tree))) tree))
Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as

view plainprint?

1. (define (square-tree tree) (tree-map square tree))  

(define (square-tree tree) (tree-map square tree))
Answer:

view plainprint?

1. (define (tree-map proc tree)  
2.   (map (lambda (sub-tree)  
3.          (if (pair? sub-tree)  
4.              (tree-map proc sub-tree)  
5.              (proc sub-tree)))  
6.        tree))  
7.   
8. (define (square-tree tree) (tree-map square tree))  
9. ;; another use  
10. (define (inc-tree tree) (tree-map inc tree))  

(define (tree-map proc tree) (map (lambda (sub-tree) (if (pair? sub-tree) (tree-map proc sub-tree) (proc sub-tree))) tree)) (define (square-tree tree) (tree-map square tree)) ;; another use (define (inc-tree tree) (tree-map inc tree))
Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

view plainprint?

1. (define (subsets s)  
2.   (if (null? s)  
3.       (list nil)  
4.       (let ((rest (subsets (cdr s))))  
5.         (append rest (map <??> rest)))))  

(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))
Answer:

view plainprint?

1. (define (subsets s)  
2.   (if (null? s)  
3.       (list nil)  
4.       (let ((rest (subsets (cdr s))))  
5.         (append rest (map (lambda (x) (cons (car s) x)) rest)))))  

(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
Exercise 2.33. Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

view plainprint?

1. (define (map p sequence)  
2.   (accumulate (lambda (x y) <??>) nil sequence))  
3. (define (append seq1 seq2)  
4.   (accumulate cons <??> <??>))  
5. (define (length sequence)  
6.   (accumulate <??> 0 sequence))  

(define (map p sequence) (accumulate (lambda (x y) <??>) nil sequence)) (define (append seq1 seq2) (accumulate cons <??> <??>)) (define (length sequence) (accumulate <??> 0 sequence))
Answer:

view plainprint?

1. (define (a-map p sequence)  
2.   (accumulate (lambda (x y) (cons (p x) y)) nil sequence))  
3.   
4. (a-map inc (list 1 2 3 4))  
5. (2 3 4 5)  
6.   
7. (define (a-append seq1 seq2)  
8.   (accumulate cons seq2 seq1))  
9.   
10. (a-append (list 1) (list 3 4))  
11. (1 3 4)  
12.   
13. (define (length sequence)  
14.   (accumulate (lambda (x y) (+ y 1)) 0 sequence))  
15.   
16. (length (list 1 (list 3 4)))  
17. 2  

(define (a-map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)) (a-map inc (list 1 2 3 4)) (2 3 4 5) (define (a-append seq1 seq2) (accumulate cons seq2 seq1)) (a-append (list 1) (list 3 4)) (1 3 4) (define (length sequence) (accumulate (lambda (x y) (+ y 1)) 0 sequence)) (length (list 1 (list 3 4))) 2
Exercise 2.34. Evaluating a polynomial in x at a given value of x can be formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner's rule, which structures the computation as

In other words, we start with an, multiply by x, add an-1, multiply by x, and so on, until we reach a0.16 Fill in the following template to produce a procedure that evaluates a polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged in a sequence, from a0 through an.

view plainprint?

1. (define (horner-eval x coefficient-sequence)  
2.   (accumulate (lambda (this-coeff higher-terms) <??>)  
3.               0  
4.               coefficient-sequence))  

(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))
For example, to compute 1 + 3x + 5x³ + x⁵ at x = 2 you would evaluate

1. (horner-eval 2 (list 1 3 0 5 0 1))  

(horner-eval 2 (list 1 3 0 5 0 1))
Answer:

view plainprint?

1. (define (horner-eval x coefficient-sequence)  
2.   (accumulate (lambda (this-coeff higher-terms)   
3.                 (+ this-coeff (* higher-terms x)))  
4.               0  
5.               coefficient-sequence))  

(define (horner-eval x coefficient-sequence) (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x))) 0 coefficient-sequence))
Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:

view plainprint?

1. (define (count-leaves t)  
2.   (accumulate <??> <??> (map <??> <??>)))  

(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))
Answer:

view plainprint?

1. (define (count-leaves t)  
2.   (accumulate +  
3.               0  
4.               (map (lambda (x) 1)   
5.                    (fringe t))))  

(define (count-leaves t) (accumulate + 0 (map (lambda (x) 1) (fringe t))))
Exercise 2.36. The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if 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:

view plainprint?

1. (define (accumulate-n op init seqs)  
2.   (if (null? (car seqs))  
3.       nil  
4.       (cons (accumulate op init <??>)  
5.             (accumulate-n op init <??>))))  

(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init <??>) (accumulate-n op init <??>))))
Answer:

view plainprint?

1. (define (accumulate-n op init seqs)  
2.   (if (null? (car seqs))  
3.       nil  
4.       (cons (accumulate op init (map (lambda (x) (car x)) seqs))  
5.             (accumulate-n op init (map (lambda (x) (cdr x)) seqs)))))  

(define (accumulate-n op init seqs) (if (null? (car seqs)) nil (cons (accumulate op init (map (lambda (x) (car x)) seqs)) (accumulate-n op init (map (lambda (x) (cdr x)) seqs)))))
Exercise 2.37. Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) 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

view plainprint?

1. (define (dot-product v w)  
2.   (accumulate + 0 (map * v w)))  

(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.)

view plainprint?

1. (define (matrix-*-vector m v)  
2.   (map <??> m))  
3. (define (transpose mat)  
4.   (accumulate-n <??> <??> mat))  
5. (define (matrix-*-matrix m n)  
6.   (let ((cols (transpose n)))  
7.     (map <??> m)))  

(define (matrix-*-vector m v) (map <??> m)) (define (transpose mat) (accumulate-n <??> <??> mat)) (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map <??> m)))
Answer:

view plainprint?

1. ;; Matrix * Vector  
2. (define (matrix-*-vector m v)  
3.   (map (lambda (x) (dot-product x v)) m))  
4.   
5. ;; Transpose Matrix  
6. (define (transpose mat)  
7.   (accumulate-n cons nil mat))  
8.   
9. ;; Matrix * Matrix  
10. (define (matrix-*-matrix m n)  
11.   (let ((cols (transpose n)))  
12.     (map (lambda (x)  
13.            (map (lambda (y)  
14.                   (accumulate + 0  
15.                               (accumulate-n * 1 (list x y))))  
16.                 cols))  
17.          m)))  

;; Matrix * Vector (define (matrix-*-vector m v) (map (lambda (x) (dot-product x v)) m)) ;; Transpose Matrix (define (transpose mat) (accumulate-n cons nil mat)) ;; Matrix * Matrix (define (matrix-*-matrix m n) (let ((cols (transpose n))) (map (lambda (x) (map (lambda (y) (accumulate + 0 (accumulate-n * 1 (list x y)))) cols)) 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:

view plainprint?

1. (define (fold-left op initial sequence)  
2.   (define (iter result rest)  
3.     (if (null? rest)  
4.         result  
5.         (iter (op result (car rest))  
6.               (cdr rest))))  
7.   (iter initial sequence))  

(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

1. (fold-right / 1 (list 1 2 3))  
2. (fold-left / 1 (list 1 2 3))  
3. (fold-right list nil (list 1 2 3))  
4. (fold-left list nil (list 1 2 3))  

(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.

Answer:

1. (fold-right / 1 (list 1 2 3))  
2. 1 1/2  
3.   
4. (fold-left / 1 (list 1 2 3))  
5. 1/6  
6.   
7. (fold-right list nil (list 1 2 3))  
8. (1 (2 (3 ())))  
9.   
10. (fold-left list nil (list 1 2 3))  
11. (((() 1) 2) 3)  

(fold-right / 1 (list 1 2 3)) 1 1/2 (fold-left / 1 (list 1 2 3)) 1/6 (fold-right list nil (list 1 2 3)) (1 (2 (3 ()))) (fold-left list nil (list 1 2 3)) (((() 1) 2) 3)
In order for fold-right and fold-left to yield identical results op should be associative. For instance take the + operator.

1. (fold-right + 1 (list 1 2 3))  
2. 7  
3.   
4. (fold-left + 1 (list 1 2 3))  
5. 7  

(fold-right + 1 (list 1 2 3)) 7 (fold-left + 1 (list 1 2 3)) 7
Exercise 2.39. Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:

view plainprint?

1. (define (reverse sequence)  
2.   (fold-right (lambda (x y) <??>) nil sequence))  
3. (define (reverse sequence)  
4.   (fold-left (lambda (x y) <??>) nil sequence))  

(define (reverse sequence) (fold-right (lambda (x y) <??>) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) <??>) nil sequence))
Answer:

view plainprint?

1. (define (reverse sequence)  
2.   (fold-right (lambda (x y) (if (null? y) (list x) (append y (list x))))  
3.               nil  
4.               sequence))  
5.   
6. (define (reverse sequence)  
7.   (fold-left (lambda (x y) (if (null? x) (list y) (append (list y) x)))  
8.              nil  
9.              sequence))  

(define (reverse sequence) (fold-right (lambda (x y) (if (null? y) (list x) (append y (list x)))) nil sequence)) (define (reverse sequence) (fold-left (lambda (x y) (if (null? x) (list y) (append (list y) x))) nil sequence))
Exercise 2.40. Define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i,j) with 1< j< i< n. Use unique-pairs to simplify the definition of prime-sum-pairs given above.

Answer:

view plainprint?

1. (define (unique-pairs n)  
2.   (flatmap (lambda (i)  
3.              (map (lambda (j) (list i j))  
4.                   (enumerate-interval 1 (- i 1))))  
5.            (enumerate-interval 1 n)))  

(define (unique-pairs n) (flatmap (lambda (i) (map (lambda (j) (list i j)) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n)))
Exercise 2.41. Write a procedure to find all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer n that sum to a given integer s.

Answer:

view plainprint?

1. (define (generate-triples n)  
2.   (flatmap (lambda (i)  
3.              (flatmap (lambda (j)  
4.                         (map (lambda (k) (list i j k))  
5.                              (enumerate-interval 1 (- j 1))))  
6.                       (enumerate-interval 1 (- i 1))))  
7.            (enumerate-interval 1 n)))  
8.   
9. (define (find-triples n s)  
10.   (define (sum-equal-s? triple)  
11.     (let ((a (car triple))  
12.           (b (cadr triple))  
13.           (c (caddr triple)))  
14.       (= (+ a b c) s)))      
15.   (filter sum-equal-s? (generate-triples n)))  

(define (generate-triples n) (flatmap (lambda (i) (flatmap (lambda (j) (map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1)))) (enumerate-interval 1 (- i 1)))) (enumerate-interval 1 n))) (define (find-triples n s) (define (sum-equal-s? triple) (let ((a (car triple)) (b (cadr triple)) (c (caddr triple))) (= (+ a b c) s))) (filter sum-equal-s? (generate-triples n)))
Exercise 2.42.

Figure 2.8: A solution to the eight-queens puzzle.

The ``eight-queens puzzle'' asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n× n chessboard. Queens has an internal procedure queen-cols that returns the sequence of all ways to place queens in the first k columns of the board.

view plainprint?

1. (define (queens board-size)  
2.   (define (queen-cols k)    
3.     (if (= k 0)  
4.         (list empty-board)  
5.         (filter  
6.          (lambda (positions) (safe? k positions))  
7.          (flatmap  
8.           (lambda (rest-of-queens)  
9.             (map (lambda (new-row)  
10.                    (adjoin-position new-row k rest-of-queens))  
11.                  (enumerate-interval 1 board-size)))  
12.           (queen-cols (- k 1))))))  
13.   (queen-cols board-size))  

(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and new-row is a proposed row in which to place the queen for the kth column. Complete the program by implementing the representation for sets of board positions, including the procedure adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board, which represents an empty set of positions. You must also write the procedure safe?, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others. (Note that we need only check whether the new queen is safe -- the other queens are already guaranteed safe with respect to each other.)

Answer:

view plainprint?

1. (define empty-board (list nil))  
2.   
3. (define (adjoin-position new-row k rest-of-queens)  
4.   (if (null? (car rest-of-queens))  
5.       (list (list k new-row))  
6.       (cons (list k new-row) rest-of-queens)))  
7.   
8. (define (safe? k positions)  
9.   (define (iter new-pos others)  
10.     (if (null? others) #t  
11.         (let ((other-pos (car others)))  
12.           (if (row-col-or-dia-matches? new-pos other-pos) #f  
13.               (iter new-pos (cdr others))))))  
14.   (if (= k 1) #t  
15.       (iter (car positions) (cdr positions))))  
16.                
17. (define (row-col-or-dia-matches? new-position other-position)  
18.   (or (same-row? new-position other-position)  
19.       (same-col? new-position other-position)  
20.       (same-diagonal? new-position other-position)))  
21.             
22. (define (same-row? pos1 pos2)  
23.   (= (cadr pos1) (cadr pos2)))  
24.     
25. (define (same-col? pos1 pos2)  
26.   (= (car pos1) (car pos2)))  
27.   
28. (define (same-diagonal? pos1 pos2)  
29.   (let ((k1 (car pos1))  
30.         (k2 (car pos2))  
31.         (r1 (cadr pos1))          
32.         (r2 (cadr pos2)))  
33.     (= (abs (- k1 k2))  
34.        (abs (- r1 r2)))))  

(define empty-board (list nil)) (define (adjoin-position new-row k rest-of-queens) (if (null? (car rest-of-queens)) (list (list k new-row)) (cons (list k new-row) rest-of-queens))) (define (safe? k positions) (define (iter new-pos others) (if (null? others) #t (let ((other-pos (car others))) (if (row-col-or-dia-matches? new-pos other-pos) #f (iter new-pos (cdr others)))))) (if (= k 1) #t (iter (car positions) (cdr positions)))) (define (row-col-or-dia-matches? new-position other-position) (or (same-row? new-position other-position) (same-col? new-position other-position) (same-diagonal? new-position other-position))) (define (same-row? pos1 pos2) (= (cadr pos1) (cadr pos2))) (define (same-col? pos1 pos2) (= (car pos1) (car pos2))) (define (same-diagonal? pos1 pos2) (let ((k1 (car pos1)) (k2 (car pos2)) (r1 (cadr pos1)) (r2 (cadr pos2))) (= (abs (- k1 k2)) (abs (- r1 r2)))))
Exercise 2.43. Louis Reasoner is having a terrible time doing exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6× 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as

view plainprint?

1. (flatmap  
2.  (lambda (new-row)  
3.    (map (lambda (rest-of-queens)  
4.           (adjoin-position new-row k rest-of-queens))  
5.         (queen-cols (- k 1))))  
6.  (enumerate-interval 1 board-size))  

(flatmap (lambda (new-row) (map (lambda (rest-of-queens) (adjoin-position new-row k rest-of-queens)) (queen-cols (- k 1)))) (enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis's program to solve the eight-queens puzzle, assuming that the program in exercise 2.42 solves the puzzle in time T.

Answer: Louis is breaking a well known rule of thumb in programming - namely to avoid expensive operations in inner loops. His code is calling the expensive recursive call to queen-cols in the inner loop.

I am not able to figure out how much time Louis' procedure will take to run in terms of T. If you have an answer/explanation do let me know.