SICP 习题参考答案 3.3

win_hate

此帖为 SICP 章节 3.3 的参考答案。为保持可读性，请勿直接在本帖讨论。讨论请另开新帖。

• 本节电子版：[Modeling with Mutable Data]
  
• 答案目录：[点这里]
  

win_hate

Exercise 3.12.  The following procedure for appending lists was introduced in section 2.2.1:

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

Append forms a new list by successively consing the elements of x onto y. The procedure append! is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its cdr is now y. (It is an error to call append! with an empty x.)

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

Here last-pair is a procedure that returns the last pair in its argument:

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

Consider the interaction

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
z
(a b c d)
(cdr x)
<response>
(define w (append! x y))
w
(a b c d)
(cdr x)
<response>

What are the missing <response>s? Draw box-and-pointer diagrams to explain your answer.

win_hate

• 第一个 <response> 是 (b)
  
  此时 z 是通过 (cons 'a (cons 'b y)) 构造出来的，与 x 没有共享部分。
  
  
  1. 
     
  2. > (define x (list 'a 'b))
     
  3. > (define y (list 'c 'd))
     
  4. > (define z (append x y))
     
  5. 
     
  6. > z
     
  7. (a b c d)
     
  8. 
     
  9. > (cdr x)
     
  10. (b)
      

  复制代码
  
  
• 第二个 <response> 是 (b c d)
  
  此时 set-cdr 把 x 最后指向 NULL 的指针指向了  y 的表头。所以 x 就是 w，w 就是 x.（参考 append! 代码的最后一句）
  
  
  1. 
     
  2. > (define w (append! x y))
     
  3. 
     
  4. > w
     
  5. (a b c d)
     
  6. 
     
  7. > (cdr x)
     
  8. (b c d)
     
  9. 
     
  10. > (eq? x w)
      
  11. #t
      
  12. 
      
  13. > (eq? (list 1 2) (list 1 2))
      
  14. #f
      

  复制代码
  
  

win_hate

Exercise 3.13.  Consider the following make-cycle procedure, which uses the last-pair procedure defined in exercise 3.12:

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

Draw a box-and-pointer diagram that shows the structure z created by

(define z (make-cycle (list 'a 'b 'c)))

What happens if we try to compute (last-pair z)?

win_hate

• 表尾指向表头，构成一个环。
  
  
  1. 
     
  2. > (define z (make-cycle (list 'a 'b 'c)))
     
  3. 
     
  4. > z
     
  5. (a b c . #-2#)
     
  6. 
     
  7. > (car z)
     
  8. a
     
  9. 
     
  10. > (cadr z)
      
  11. b
      
  12. 
      
  13. > (caddr z)
      
  14. c
      
  15. 
      
  16. > (cadddr z)
      
  17. a
      

  复制代码
  
  
• 计算 (last-pair z) 将无法终止，直到耗尽所有资源。
  

win_hate

Exercise 3.14.  The following procedure is quite useful, although obscure:

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

Loop uses the ``temporary'' variable temp to hold the old value of the cdr of x, since the set-cdr! on the next line destroys the cdr. Explain what mystery does in general. Suppose v is defined by (define v (list 'a 'b 'c 'd)). Draw the box-and-pointer diagram that represents the list to which v is bound. Suppose that we now evaluate (define w (mystery v)). Draw box-and-pointer diagrams that show the structures v and w after evaluating this expression. What would be printed as the values of v and w ?

win_hate

• mystery 作用在一个列表上，它遍历并反转此列表
  
• 部分反转的列表在 y 中积累。
  
• (define w (mystery v)) 后，w 为 (d c b a)，而 v 是 (a)
  
  v 在第一次循环中被肢解成两部分。一部分是 temp = (cdr v)，用在以后的循环中，另一部分是: v 的第一个 cons 的右指针指向 y，此时它是个空表。所以 v 为 (a). 此后的循环与 v 再无关系，所以最后 v 任是 (a).
  

win_hate

Exercise 3.15.  Draw box-and-pointer diagrams to explain the effect of set-to-wow! on the structures z1 and z2 above.

win_hate

<wait: pic>

win_hate

Exercise 3.16.  Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ``It's easy,'' he reasons. ``The number of pairs in any structure is the number in the car plus the number in the cdr plus one more to count the current pair.'' So Ben writes the following procedure:

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben's procedure would return 3; return 4; return 7; never return at all.