乐正

Actions speak louder than words.

Sicp-ex3-14

问题

下面过程相当有用,但也有些费解,

1
2
3
4
5
6
7
8
(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里面用一个临时变量temp保存xcdr原来的值,因为下一行里的set-cdr!将破坏这个cdr。请一般性地解释mystery做些什么。假定v通过(define v (list 'a 'b 'c 'd))定义,请画出v约束的表对应的盒子指针模型。假定现在求值(define w (mystery v)),请画出求值这个表达式之后结构v和结构w的盒子指针图形。vw的值打印出来是什么?

解答

要知道mystery做些什么,先看它的执行过程。将v代入mystery后展开:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(mystery (list 'a 'b 'c 'd))

(loop (list 'a 'b 'c 'd) '())

(if (null? (list 'a 'b 'c 'd))
    '()
    (let ((temp (list 'b 'c 'd)))
      (set-cdr! (list 'a 'b 'c 'd) '())
      (loop (list 'b 'c 'd) (list 'a))))

(loop (list 'b 'c 'd) (list 'a))

(if (null? (list 'b 'c 'd))
    (list 'a)
    (let ((temp (list 'c 'd)))
      (set-cdr! (list 'b 'c 'd) (list 'a))
      (loop (list 'c 'd) (list 'b 'a))))

(loop (list 'c 'd) (list 'b 'a))

(if (null? (list 'c 'd))
    (list 'b 'a)
    (let ((temp (list 'd)))
      (set-cdr! (list 'c 'd) (list 'b 'a))
      (loop (list 'd) (list 'c 'b 'a))))

(loop (list 'd) (list 'c 'b 'a))

(if (null? (list 'd))
    (list 'c 'b 'a)
    (let ((temp '()))
      (set-cdr! (list 'd) (list 'c 'b 'a))
      (loop '() (list 'd 'c 'b 'a))))

(list 'd 'c 'b 'a)

所以很明显可以看出,mystery过程的作用是将链表反序。

刚创建时,v的盒子指针模型如下:

练习3.13

求值(define w (mystery v))后,盒子指针模型如下:

练习3.13

测试

1
2
3
4
5
6
7
8
9
10
11
(define v (list 'a 'b 'c 'd))
;Value: v

(define w (mystery v))
;Value: w

v
;Value 15: (a)

w
;Value 16: (d c b a)

draft

« sicp-ex3-13 sicp-ex3-15 »

Comments