乐正

Actions speak louder than words.

Sicp-ex3-12

问题

下面是2.2.1节介绍过的拼接表的过程:

1
2
3
4
(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!将是一个错误)。

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

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

1
2
3
4
(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

考虑下面的交互:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(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>是什么?请画出盒子指针图形,解释你的回答。

解答

第一处<response>的值是(d);第二处<response>的值是(b c d)。这是因为调用append过程拼接两个表是通过构造出新的表实现;而append!拼接表将$x$的最后一个元素的cdr指针改变,从而也改变了$x$的值。

append之后$x$的盒子模型如下图:

练习3.12

调用append!之后其结构变成如下所示:

练习3.12

draft

« sicp-ex3-11 sicp-ex3-13 »

Comments