SICP Exercises

Chapter 02 - Part.I

Exercise 2.1

Define a better version of make-rat that handles both positive and negative arguments. make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative. 

(define (sgn x)
    (cond ((= x 0) 0)
          ((> x 0) 1)
          (else -1)))
(define (make-rat n d)
    (let ((an (abs n))
          (ad (abs d)))
    (let ((g (gcd an ad)))
    (cond ((= 0 an) (cons 0 1))
          ((= (sgn n) (sgn d)) (cons (/ an g) (/ ad g)))
          (else (cons (* -1 (/ an g)) (/ ad g)))))))

Exercise 2.2

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points: 

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(define make-point   cons)
(define make-segment cons)
(define start-segment car)
(define end-segment   cdr)
(define x-point car)
(define y-point cdr)

(define (mindpoint-segment seg)
    (make-point (average (x-point (start-segment seg)) (x-point (end-segment seg)))
                (average (y-point (start-segment seg)) (y-point (end-segment seg)))))

Exercise 2.3

Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation? 

(define (make-tringle a b c)
    (cons a (cons b c)))
(define (a-point t) (car t))
(define (b-point t) (car (cdr t)))
(define (c-point t) (cdr (cdr t)))

; another representation
(define (make-tringle a b c)
    (cons (cons a b) c))
(define (a-point t) (car (car t)))
(define (b-point t) (cdr (car t)))
(define (c-point t) (cdr t))

; some helper function
; inner product of vector ab and ac
(define (inner-porduct a b c)
    (+ (* (- (x-point b) (x-point a)) (- (x-point c) (x-point a)))
       (* (- (y-point b) (y-point a)) (- (y-point c) (y-point a)))))
(define (length-segment s)
    (let ((seg (make-point (- (x-point (end-segment s)) (x-point (start-segment s)))
                           (- (y-point (end-segment s)) (y-point (start-segment s))))))
    (sqrt (inner-product (cons 0 0) seg seg))))

; now  the area and perimeter should be identical to both representation
(define (perimeter t)
    (+ (segment-length (a-point t))
       (segment-length (b-point t))
       (segment-length (c-point t))))
(define (area t)
    (abs (inner-product (a-point t) (b-point t) (c-point t))))

Exercise 2.5

Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair \(a\) and \(b\) as the integer that is the product \(2^a\cdot 3^b\). Give the corresponding definitions of the procedures cons, car, and cdr. 

(define (cons a b) (* (exp 2 a) (exp 3 b)))

; helper prodecure used in car and cdr
(define (in b n)
    (define (iter n t)
        (if (= 0 (remainder n b))
            (iter (/ n b) (+ t 1))
            (t)))
    (iter n 0))

; car and cdr
(define (car p) (in 2 p))
(define (cdr p) (in 3 p))

Exercise 2.6

In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as 

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the \(\lambda\)-calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1) 

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))

(define (+ a b) (lambda (f) (lambda (x) ((a f) ((b f) x))))

Exercise 2.7

Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor: 

(define (make-interval a b) (cons a b))

Define selectors upper-bound and lower-bound to complete the implementation. 

(define upper-bound car)
(define lower-bound cdr)

Exercise 2.8

Using reasoning analogous to Alyssa's, describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval. 

(define (sub-interval a b)
    (make-interval (- (lower-bound a) (upper-bound b))
                   (- (upper-bound a) (lower-bound b)))

Exercise 2.9

The width of an interval is half of the difference between its upper and lower bounds. The width is a measure of the uncertainty of the number specified by the interval. For some arithmetic operations the width of the result of combining two intervals is a function only of the widths of the argument intervals, whereas for others the width of the combination is not a function of the widths of the argument intervals. Show that the width of the sum (or difference) of two intervals is a function only of the widths of the intervals being added (or subtracted). Give examples to show that this is not true for multiplication or division.

Simply notice the fact that sum of two interval, say \((a\pm \delta_a)\) and \((b\pm \delta_b)\), is \(((a+b)\pm (\delta_a+\delta_b))\), shows that the width of the sum of two interval is the sum of the width of the two.

And the width of the multiplication of two interval \((a\pm \delta_a)\) and \((b\pm \delta_b)\) is \((ab \pm (b\delta_a+a\delta_b))\), assuming all interval contain no negtive number, which shows that the width of the multiplication of two interval is not only relate to the width of each interval, but also relate to the lower nd upper bound of two interval itself.

Exercise 2.10

Ben Bitdiddle, an expert systems programmer, looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Modify Alyssa's code to check for this condition and to signal an error if it occurs. 

(define (div-interval x y)
    (if (<= (* (lower-bound y) (upper-bound)) 0)
        (error "divisor interval contains zero ")
        (mul-interval x
                      (make-interval (/ 1.0 (upper-bound y))
                                     (/ 1.0 (lower-bound y))))))

Exercise 2.11

In passing, Ben also cryptically comments: "By testing the signs of the endpoints of the intervals, it is possible to break mul-interval into nine cases, only one of which requires more than two multiplications." Rewrite this procedure using Ben's suggestion. 

(define (mul-interval x y)
    (define (pos-zero i)
        (let ((x (lower-bound i))
              (y (upper-bound i)))
        (cond ((and (<  x 0) (<  y 0)) -1)
              ((and (<= x 0) (>= y 0)) 0)
              ((and (>  x 0) (>  y 0)) 1))))
    (let ((tx (pos-zero x))
          (ty (pos-zero y)))
    (define (condition a b) (and (= tx a) (= ty b)))
    (define (mi v1 v2 v3 v4)
        (let ((f1 (if (= 0 v1) lower-bound upper-bound))
              (f2 (if (= 0 v2) lower-bound upper-bound))
              (f3 (if (= 0 v3) lower-bound upper-bound))
              (f4 (if (= 0 v4) lower-bound upper-bound)))
        (make-interval (* (f1 x) (f2 y)) (* (f3 x) (f4 y)))))
    (cond ((condition  1  1) (mi 0 0 1 1)) ; --0---[x]-[y]--
          ((condition -1 -1) (mi 1 1 0 0)) ; --[x]-[y]---0--
          ((condition  1 -1) (mi 0 1 1 0)) ; --[y]--0--[x]--
          ((condition -1  1) (mi 1 0 0 1)) ; --[x]--0--[y]--
          ((condition  0  1) (mi 0 1 1 1)) ; --[x-0-]--[y]--
          ((condition  0 -1) (mi 1 0 0 0)) ; --[y]--[x-0-]--
          ((condition  1  0) (mi 1 0 1 1)) ; --[y-0-]--[x]--
          ((condition -1  0) (mi 0 1 0 0)) ; --[x]--[y-0-]--
          (else make-interval (min (* (lower-bound x) (upper-bound y))
                                   (* (upper-bound x) (lower-bound y)))
                              (max (* (lower-bound x) (lower-bound y))
                                   (* (upper-bound x) (upper-bound y)))))))

Exercise 2.12

Define a constructor make-center-percent that takes a center and a percentage tolerance and produces the desired interval. You must also define a selector percent that produces the percentage tolerance for a given interval. The center selector is the same as the one shown above. ] 

(define (make-center-percent c p)
    (let ((hw (* c p)))
    (make-interval (- c hw) (+ c hw))))
(define (percent i)
    (abs (/ (width i) (center i))))

Exercise 2.13

Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

Assume that two interval \(I_1\) and \(I_2\), that \(I_i=[c_i\pm c_i\cdot p_i]\), \((i=1,2)\), and both interval are positive, the product of two interval would be \(I=[(1-p_1)c_1\cdot (1-p_2)c_2, (1+p_1)c_1\cdot (1+p_2)c_2]=[c\pm cp]\), where \(c=(1+\frac 12 p_2p_2)c_1c_2\), \(p=(p_1+p_2)/(1+\frac 12 p_1p_2)\). From the given assumption that \(p_1\) and \(p_2\) is small enough that \(p_1p_2\) can be ignored. So the product \(I\) has a simple approximation \(I_{approx}=[c_1c_2\pm c_1c_2(p_1+p_2)]\).

Exercise 2.14

Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals \(A\) and \(B\), and use them in computing the expressions \(A/A\) and \(A/B\). You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see exercise 2.12).

With two interval \(A=10\pm 5%\) and \(B=20\pm 1%\), par1 gives \(6.6830\pm 8.132%\) while par2 yields \(6.6643\pm 3.668%\).

The result of \(A/A=1.005\pm 9.975%\), \(B/B=1.0002\pm 1.9998%\), \(A/B=0.5003\pm 5.997%\). shows that basically after the div-interval, the percent of the two interval is the sum of both (as in 2.13). So the error will easily accumulate along with the process of evaluation. As for percedure par1, there are 3 interval arithmetic, namely (add-interval r1 r2), (mul-interval r1 r2) and the div-interval of pervious two. Therefore the error get accumulated 3 times. While the procedure par2, only the add of the two reverse involves interval arithmetic, since one is not actually an interval, result in a more accurate result.

The error analysis shows that the \(R=\frac{R_1R_2}{R_1+R_2}\) gives an error of \((\frac{\delta_R}{R})^2=(\frac{\delta_{R_1}}{R_1})^2+(\frac{\delta_{R_2}}{R_2})^2+\delta_{R_1}^2+\delta_{R_2}^2\), while \(R'=\frac{1}{\frac{1}{R_1}+\frac{1}{R_2}}\) only has an error of \({\delta_{R'}}^2=\delta_{R_1}^2+{\delta_{R_2}}^2\), which is much smaller.

Exercise 2.15

Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a "better" program for parallel resistances than par1. Is she right? Why?

For the most case, this is correct, for in each step of evaluation, the error gets accumulated. Therefore, the lesser expersion with number with error, the better. But in some cases, the algebraically equivlent is needed to prevent underflow from happenning.

Exercise 2.16

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

This is indeed a very diffcult one. I think it is impossible to devise such interval-arithmetic package. One strong reason is the error analysis in ex 2.14, which shows that the how a value calculated dose and should effect its accuracy.

To interval arithmetic, certain laws which is known to be true in real number dose not fits in. For example, if the basic arithmetic of intervla defined as follow:

\[ \begin{alignat}{3} [a,b] &+&[c,d] &= [a+b & &, c+d] \cr [a,b] &\times& [c,d] &= [\min(ac,ad,bc,bd) & &, \max(ac,ad,bc,bd)] \cr \end{alignat} \]

Then all interval, denoted as \(\rm{I}\), along with each of these two operator does not form an group. And with these two operator law of distribute does not applied (\(A(B+C)\) is not equals to \(AB+AC\), \(A,B,C\in\rm{I}\), in fact, \(A(B+C)\subset AB+AC\)).

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)

(define (last-pair xs)
    (if (null? xs)
        (list)
        (let ((x    (car xs))
              (rest (cdr xs)))
             (if (null? xs)
                (list x)
                (last-pair xs)))))

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)

(define (reverse xs)
    (define (iter xs rs)
        (if (null? xs)
            rs
            (iter (cdr xs) (cons (car xs) rs))))
    (iter xs (list)))

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? 

(define first-denomination car)
(define except-first-denomination cdr)
(define no-more? null?)

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) <body>)

The procedure f can be called with two or more arguments. If we evaluate (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 (define (g . w) <body>), 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)

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)

(define (same-parity x . xs)
    (define (iter is rs)
        (cond ((null? is) (reverse rs))
              ((even? (- (car is) x)) (iter (cdr is) (cons (car is) rs)))
              (else (iter (cdr is) rs))))
    (iter xs (list x)))

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

; the recursive way
(cons (square (car items)) (square-list (cdr items)))

; using map
(map square items)

Exercise 2.22

Louis Reasoner tries to rewrite the first quare-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.

The first attemp get the answer in reverse order is because how the answer list been constructed. This precedure take the first member of the list, square it, and push it to the answer list, in which way the first number in the list will become the last one in the answer list.

The second attemp fails for how a list is represtented in Scheme. A proper way to represent the list (square-list (list 1 2 3 4)) would be (cons 1 (cons 4 (cons 9 (cons 16 nil)))), but the second one gives (cons (cons (cons (cons 1 nil) 4) 9) 16), which is obviously the wrong one.

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. 

(define (for-each p xs)
    (if (null? xs) (list)
        ((p (car x)) (for-each p (cdr xs)))))

Noted that for-each is not the same as map, while (define for-each map) seems fine, which, in fact, is not. For for-each should ensure that the given precedure should be strictly applied to each element in the list from the left to right, while map dose not need to be guarantee that.

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.

The interpreter will show (1 (2 (3 4)))

Exercise 2.25

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

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

Noted that (7) is actually (cons 7 nil) for short, the nil is ommited when displaying. So the first car is nessery in each answer.

Exercise 2.26

Suppose we define x and y to be two lists: 

(append x y)
(cons x y)
(list x y)

]=> (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, 

(define x (list (list 1 2) (list 3 4)))

(reverse x)
((3 4) (1 2))

(deep-reverse x)
((4 3) (2 1))

(define (deep-reverse lls)
    (if (pair? lls) (reverse (map deep-reverse lls))
        lls))

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, 

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

(define (fringe ls)
    (cond ((null? ls) (list))
          ((not (pair? (car ls))) (cons (car ls) (fringe (cdr ls))))
          (else (append (fringe (car ls)) (fringe (cdr ls))))))

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

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

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

(define (left-branche    car)
(define (right-branch x) (car (cdr x)))
(define branche-length car)
(define branche-structure (lambda (x) (car (cdr x))))

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

(define (total-weight mobile)
    (define (struct-weight st)
        (if (pair? st) (total-weight st) st))
    (let ((sl (branche-structure (left-branche  mobile)))
          (sr (branche-structure (right-branche mobile))))
    (+ (struct-weight sl) (struct-weight sr))))

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. 

(define (balance? m)
    (let ((sl (branche-structure (left-branche  m)))
          (sr (branche-structure (right-branche m)))
          (ll (branche-length (left-branche  m)))
          (lr (branche-length (right-branche m))))
    (if (and (pair? sl) (pair? sr))
        (= (* ll sl) (* lr sr))
        (and (balance? sl) (balance? sr)
             ( = (* ll (total-weight sl))
                 (* lr (total-weight sr)))))))

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

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

Only these selectors 

(define left-branche  car)
(define right-branche cdr)
(define branche-length    car)
(define branche-structure cdr)

Exercise 2.33

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations: 

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

Exercise 2.34

Evaluating a polynomial in \(x\) at a given value of \(x\) can be formulated as an accumulation. We evaluate the polynomial \(f(x)=\sum_{i=1}^n a_ix^i\) using a well-known algorithm called Horner's rule, which structures the computation as \(f(x)=(\cdots(a_nx+a_{n-1})x+\cdots +a_1)x+a_0\). In other words, we start with \(a_n\), multiply by \(x\), add \(a_{n-1}\), multiply by \(x\), and so on, until we reach \(a_0\). 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 \(a_0\) through \(a_n\). 

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))

For example, to compute \(1+3x+5x^3+x^5\) at \(x=2\) you would evaluate 

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

Only the lambda part: 

(lambda (this-coeff higher-terms) (+ this-coeff (* x higher-terms)))

The porpurse of Horner's rule is to reduce the arithmetic operation being used when evaluation, which reduce the times of multiplication from \(2n-1\), when evaluating term by term, to \(n\), while the times of addition is both \(n\).

Exercise 2.35

Redefine count-leaves from section 2.2.2 as an accumulation: 

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

(define (count-leaves t)
    (accumulate + 0 (map (lambda (x) 1) (enumerate-tree 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: 

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

; first <??>
(map car seqs)
; second <??>
(map cdr seqs)

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

\[ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 6 \\ 6 & 7 & 8 & 9 \end{bmatrix} \]

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: 

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

(define (martix-*-vector m v)
  (map (lambda (r) (dot-product r v) m)))
(define (transpose mat)
  (accumulate-n cons nil mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (r) (matrix-*-vector col r) 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))

Give a property that op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

Consider (fold-left op init (list a1 a2 a3 a4)) and (fold-right op init (list a1 a2 a3 a4)), the resule is something like this (using Haskell style infix notion to make thing clear): 

-- fold-left
((((a1 `op` a2) `op` a3) `op` a4) `op` init)
-- fold-right
(a1 `op` (a2 `op` (a3 `op` (a4 `op` init))))

Their difference lies in the order of computation, which clear suggests that the fold-right and fold-left return the same result for any list when the op satisfy the Rule of Combination, whohich means that in a "chain" of same op, which op gets computed first does not affact the result.

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

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))
(define (reverse sequence)
  (fold-left (lambda (x y) (cons 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\le j\lt i\le n\). Use unique-pairs to simplify the definition of prime-sum-pairs given above. 

(define (unique-pairs n)
  (accumulate append '()
              (map (lambda (i)
                           (map (lambda (j) (list i j))
                                (enumerate-interval (- i 1))))
                   (enumerate-interval n))))
(define (prime-sum-pairs n)
  (map (lambda (p) (append p (list (+ p))))
       (filter (lambda (p) (prime? (+ p)))
               (unique-pairs 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. 

(define (find-sum-s n s)
  (filter (lambda (t) (= (+ t) s)) (uniq-triple n)))
(define (uniq-triple n)
  (flatmap (lambda (i) (map (lambda (p) (cons i p)) (unique-pqir i)))
           (enumerate-interval n)))