SICP

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)) SOLUTION The code and tests are here .

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. SOLUTION The code and tests are here . Notes: 'op' should satisfy the associative property to guarantee that fold-right and fold-left  will produce the same values for an

Exercise 2.37.    Suppose we represent vectors  v  = ( v i ) as sequences of numbers, and matrices  m  = ( m i j ) 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))) SOLUTION The code and tests are here .

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 < ?? >)))) SOLUTION The code and tests are here . The test results are also pasted and highlighted below. ; Tests Welcome to DrRacket, version 6.11 [3m]. Language: racket, with

Exercise 2.35.   Redefine  count-leaves  from section  2.2.2  as an accumulation: (define (count-leaves t)   (accumulate < ?? > < ?? > (map < ?? > < ?? >))) SOLUTION The code and tests are here .

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  a n , multiply by  x , add  a n -1 , multiply by  x , and so on, until we reach  a 0 . 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  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 + 3 x  + 5 x 3  +  x 5  at  x  = 2 you would evaluate (horner-eval 2 (list 1 3 0 5 0 1)) SOLUTION The code and tests are here .

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)) SOLUTION The code and tests are here .