Exercise 3.12 · 习题

Exercise 3.12: The following procedure for
appending lists was introduced in 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.

练习 3.12：2.2.1 节引入了以下用于拼接表的过程：

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

append 通过将 x 的各元素依次 cons 到 y 上来构成一个新表。过程 append! 与 append 类似，但它是一个变异操作而非构造操作。它通过拼接的方式将两个表连接起来，修改 x 的最后一个序对，使其 cdr 指向 y。（以空的 x 调用 append! 是一个错误。）

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

这里 last-pair 是返回其参数中最后一个序对的过程：

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

考虑以下交互：

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

两处 ⟨response⟩ 分别是什么？请画出序对指针图来解释你的答案。