SICP 习题参考答案 2.2

win_hate

1. 
   
2. (define (tree-map f t)
   
3.   (let ((pf (lambda (t) (tree-map f t))))
   
4.     (if (pair? t) (map pf t)
   
5.         (* t t))))
   

复制代码

win_hate

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:

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

win_hate

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

复制代码

解释：

• 设 x in S，则 S 的子集可以分为包含  x 的和不包含 x 的两类，分别称为类 1 和类 2。
  
• 类 2 为 S\{x} 的全部子集
  
• 类 1 为 {x} 与类 2 中元素之并
  

[ 本帖最后由 win_hate 于 2008-9-30 11:36 编辑 ]

win_hate

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

win_hate

1. 
   
2. (define (accumulate op initial sequence)
   
3.   (if (null? sequence)
   
4.       initial
   
5.       (op (car sequence)
   
6.           (accumulate op initial (cdr sequence)))))
   
7. 
   
8. (define (Map p sequence)
   
9.   (accumulate (lambda (x y) (cons (p x) y)) '() sequence))
   
10. 
    
11. (define (Append seq1 seq2)
    
12.   (accumulate cons seq2 seq1))
    
13. 
    
14. (define (Length sequence)
    
15.   (accumulate (lambda (x y) (inc y)) 0 sequence))
    

复制代码

win_hate

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

[ 本帖最后由 win_hate 于 2008-9-30 12:04 编辑 ]

win_hate

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

复制代码

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

复制代码

参考资料：

Horner's rule 的相关资料：

• 维基百科：[Horner scheme]
  
• PlanetMath: [Horner's Rule]
  
• MathWorld: [Horner's Rule]

[ 本帖最后由 win_hate 于 2008-9-30 12:04 编辑 ]

win_hate

Exercise 2.35.  Redefine count-leaves from section 2.2.2 as an accumulation:

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

[ 本帖最后由 win_hate 于 2008-9-30 11:50 编辑 ]

win_hate

1. 
   
2. (define (count-leaves t)
   
3.   (accumulate + 0
   
4.               (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))
   

复制代码

win_hate

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

[ 本帖最后由 win_hate 于 2008-10-1 20:11 编辑 ]