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.
第一个 <response> 是 (b)；而第二个 <response> 是 (b c d)
我们可以这样使用图形来看这个问题。
当使用 (append x y) 的时候，append 将返回新的一个 pair，pair 的 car 部分是 x，cdr 部分是 y。x 没有变化。
z +---+---+
----->| | +------------------------------+
+-+-+---+ |
| |
| |
v v
x +---+---+ +---+---+ y +---+---+ +---+---+
----->| | +----->| | / | ----->| | +----->| | / |
+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+
| | | |
v v v v
+---+ +---+ +---+ +---+
| a | | b | | c | | d |
+---+ +---+ +---+ +---+当我们使用 (append! x y) 的时候，盒子变成了下面这样–x 的最后一个链接链接到了 y 上面。
w ---+ y -------+
| v
| +---+---+ +---+---+ +---+---+ +---+---+
x ---+->| | +----->| | +----->| | +----->| | / |
+-+-+---+ +-+-+---+ +-+-+---+ +-+-+---+
| | | |
v v v v
+---+ +---+ +---+ +---+
| a | | b | | c | | d |
+---+ +---+ +---+ +---+所以 (cdr x) 会得到 (b c d)