List and Pairs

append 总是复制前面的参数,而不复制最后一个参数

(define a1 '(1 2 3))
(define a2 '(a b c))
(define x (append a1 a2))
x
; (1 2 3 a b c)

(set-car! a2 'd)
x
; (1 2 3 d b c)

(set-car! a1 4)
x
; (1 2 3 d b c)

从这里可以看到,append 返回的 list 里,把第一个参数复制了一 份,而把第二个参数原封不动挂在了第一个参数的复制品后面。

这个原因很简单,因为 append 如果不复制第一个参数,那么它就会 把第二个参数挂在真正的第一个参数后面。那么我们看到 a1 就变成 了 (1 2 3 a b c),就像我们这个函数 my-append:

(define (my-append l a)
  (let loop ((rest l))
    (if (null? (cdr rest)) 
        (set-cdr! rest a)
        (loop (cdr rest)))))
(define a1 '(1 2 3))
(define a2 '(a b c))
(define x (my-append a1 a2))
x
; (1 2 3 a b c)

a1
; (1 2 3 a b c)

(set-car! a2 'd)
x
; (1 2 3 d b c)

(set-car! a1 4)
x
; (4 2 3 d b c)

my-append 就是真正的把 a2 挂在了 a1 后面。然后返回 a1. 这时 a1 的值就变成了 (1 2 3 a b c) 跟 x 一样。

你有办法不复制 a1, 而能把 a2 附加在它后面,而不改变 a1 的值 吗?不可能。

我们继续

(my-append a1 a2)
; (1 2 3 . #0=(a b c . #0#))

为什么呢?因为 my-append 本来是从第一个参数开始不断的沿着 cdr 往后走,知道遇到 cdr 是 '() 的时候。然后把这个 cdr 指向 第二个参数。

这里,我们已经把 a2 指向的 list 挂在了 a1 后面,然后我们再进 行 my-append, 就会一直走到 a1 最后,*也就是 a2 最后*。然后把 a2 最后的 cdr 指向 a2, 我们就构造了一个循环结构。

(define y a1) 之后,不断执行

(begin (define y (cdr y)) y)

就会得到这样的结果:

> (2 3 . #0=(a b c . #0#))
> (3 . #0=(a b c . #0#))
> #0=(a b c . #0#)
> #0=(b c a . #0#)
> #0=(c a b . #0#)
> #0=(a b c . #0#)
> #0=(b c a . #0#)
> #0=(c a b . #0#)

进入 a2 之后就不断循环。我们这个 my-append 实际上功能相当于 Common Lisp 的 nconc.

结论

结论就是:append 会“共享”最后一个参数。

如果你用 append 构造了一个 list, 而后来修改了它的最后一部分, 比如例子中的 a2,那么 append 构造返回的 list 就被修改了!

这是很多 bug 的由来!小心!

示意图

(define foo '(x y z))
(define bar '(a b))
(define baz (append bar foo))


                +----------------------------------------+                  
                |                                        |
               \|/                                       |
     +---+    +---+---+     +---+---+      +---+---+     |
 foo | *-+--->| * | *-+---->| * | *-+----->| * | * |     |
     +---+    +-+-+---+     +-+-+---+      +-+-+---+     |
                |             |             |            |
               \|/           \|/           \|/           |
                x             y             z            |
                                                         |
                                                         |
     +---+    +---+---+     +---+---+                    |
 bar | *-+--->| * | *-+---->| * | * |                    |
     +---+    +-+-+---+     +-+-+---+                    |
                |             |                          |
               \|/           \|/                         |
                a             b                          |
               /|\           /|\                         |
                |             |                          |
     +---+    +---+---+     +---+---+                    |
 baz | *-+--->| * | *-+---->| * | *-+--------------------+
     +---+    +---+---+     +---+---+

list 生成一个新的 list, 其实只是生成了一些 cons cell.

list 生成一系列 cons cell, 然后把它的参数原封不动挂在这些 cell 的 car 上。以下是一个测试例子:

(define b (list 4 5 6))
(define tmp (cons b '()))

tmp
; ((4 5 6))

(eq? b (car tmp))
; #t

(define x (cons a tmp))
x
; ((1 2 3) (4 5 6))

(define y (list a b))
y
; ((1 2 3) (4 5 6))

(eq? (car x) (car y))
; #t

(eq? (cdr x) (cdr y))
; #f 因为 (cdr x) 是 tmp, 而 (cdr y) 是 list 生成的一个 cons cell

(eq? (cadr x) (cadr y))
; #t 

(set-car! b 10)
x
; ((1 2 3) (10 5 6))

y
;((1 2 3) (10 5 6))

;; 从上面的例子可见两个 cons cell 的 car 上挂的都是 b

(set-cdr! x '((b c)))
x
; ((1 2 3) (b c))
y
; ((1 2 3) (10 5 6))

reverse 构造了一些 cons cell,把原来的 car 们反着连接起来

了。

从下面的例子看出 reverse 只构造了新的 cons cell. 而没有复制 原来的结构。


(define x (list '(1 2) '(a b)))
(define xx (reverse x))

x
; ((1 2) (a b))
xx
; ((a b) (1 2))

(eq? (car xx) (cadr x))
; #t

member 返回的 list 只是指向参数 list 内部的一个指针

例子:

(define x '(a b c d))
(define y (member 'c x))

y
; (c d)

(set-car! y 2)

y
; (2 d)

x
; (a b 2 d)

结论

如果我们要修改一个 list 内部包含 'c 的那个位置,我们就可以用 member 去找到那个地方。