SICP 习题参考答案 2.2

win_hate

• 先看 (cons x y)
  
  由于 (cons x '(Y)) = ( x Y)，所以
  
  
  1. 
     
  2. (cons x y) = (cons '(1 2 3) '(4 5 6)) = ( (1 2 3) 4 5 6)
     

  复制代码
  
  
• 再看 (append x y)
  
  设 x = (x1 x2 ... xn)。 由于 (append '(x X) '(Y) ) = (cons x (append '(X) '(Y)))，所以
  (append '(x1 x2 ... xn) '(Y)) = (cons (x1 (cons x2 (... (cons xn '(Y))...)。故
  
  
  1. 
     
  2. (append  x y)= (append '(1 2 3) '(4 5 6))= (1 2 3 4 5 6)
     

  复制代码
  
  
• 最后看 (list x y)
  
  由于 (list X1 X2 ... Xn) = (cons X1 (cons X2 (cons ... (cons Xn nil))...), 所以
  
  
  1. 
     
  2. (list '(1 2 3) '(4 5 6)) = ( (1 2 3) (4 5 6) )
     

  复制代码
  
  

win_hate

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

x
((1 2) (3 4))

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

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

win_hate

1. 
   
2. (define (deep-reverse x)
   
3.   (if (list? x) (reverse (map deep-reverse x))
   
4.       x))
   

复制代码

win_hate

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)

win_hate

1. 
   
2. (define (fringe x)
   
3.   (cond ((null? x) x)
   
4.         ((list? x) (append (fringe (car x)) (fringe (cdr x))))
   
5.         (else (list x))))
   

复制代码

win_hate

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.

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

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

[ 本帖最后由 win_hate 于 2008-9-28 22:47 编辑 ]

win_hate

• a.
  
  
  1. 
     
  2. (define (left-branch x)
     
  3.   (car x))
     
  4. 
     
  5. (define (right-branch x)
     
  6.   (cadr x))
     
  7. 
     
  8. (define (branch-length x)
     
  9.   (car x))
     
  10. 
      
  11. (define (branch-structure x)
      
  12.   (cadr x))
      

  复制代码
  
  
• b. 本来应该写两个函数，判断对象类型为 structure 还是 branch。但注意到 structure 必定是两个 branch，且 branch 不可以直接连 branch。所以只要在写代码的时候注意一下，就可以避免判断。
  
  
  1. 
     
  2. (define  (total-weight x)
     
  3.   (if (not (pair? x)) x
     
  4.       (+ (total-weight (branch-structure (left-branch x)))
     
  5.          (total-weight (branch-structure (right-branch x))))))
     

  复制代码
  
  
• c. 利用 total-weight 获取左右分支的结构重量，用 branch-length 获取左右分支的长度，就可以判断当前点是否平衡。递归使用这个规则，就可以判断。这里应该把效率也考虑进去，因为 total-weight 是递归计算的，如果在每个分叉上调用 total-weight，则进行了太多的重复计算。所以我把 total-weight 改进为 wwbc，全称为 weight-with-balance-check。在某个分叉上调用 wwbc，如果不平衡，则返回 false，如果平衡，则返回重量。
  
  
  1. 
     
  2. (define (wwbc x)
     
  3.   (if (not (pair? x)) x
     
  4.       (let* ((lb (left-branch x)) (rb (right-branch x))
     
  5.              (wl (wwbc (branch-structure lb)))
     
  6.              (wr (if (eq? wl #f) #f (wwbc (branch-structure rb)))))
     
  7.         (cond ((eq? #f wl) #f)
     
  8.               ((= (* wl (branch-length lb))
     
  9.                   (* wr (branch-length rb))) (+ wl wr))
     
  10.               (else #f)))))
      
  11. 
      
  12. (define (balance? x)
      
  13.   (not (eq? (wwbc x) #f)))
      

  复制代码
  
  
  简单的测试代码：
  
  1. 
     
  2. (balance? '((2 ((2 1) (1 2)))
     
  3.                (3 ((2 1) (2 1)))))
     
  4. 
     
  5. (balance? '((4 4) (2 ((5 3) (3 5)))))
     

  复制代码
  
  
• d. 只需要把选择函数略为改动即可。
  

[ 本帖最后由 win_hate 于 2008-9-29 15:59 编辑 ]

win_hate

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:

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

win_hate

不使用高阶函数

1. 
   
2. (define (Square-tree t)
   
3.     (cond ((null? t) '())
   
4.           ((pair? t) (cons (Square-tree (car t))
   
5.                            (Square-tree (cdr t))))
   
6.           (else (* t t))))
   

复制代码

使用高阶函数:

1. 
   
2. (define (square-tree t)
   
3.   (if (pair? t) (map square-tree t)
   
4.       (* t t)))
   

复制代码

[ 本帖最后由 win_hate 于 2008-9-29 16:06 编辑 ]

win_hate

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

(define (square-tree tree) (tree-map square tree))