第十二章：結(jié)構(gòu)

3.3 節(jié)中介紹了 Lisp 如何使用指針允許我們將任何值放到任何地方。這種說法是完全有可能的，但這并不一定都是好事。

例如，一個對象可以是它自已的一個元素。這是好事還是壞事，取決于程序員是不是有意這樣設(shè)計的。

12.1 共享結(jié)構(gòu) (Shared Structure)

多個列表可以共享?cons?。在最簡單的情況下，一個列表可以是另一個列表的一部分。

> (setf part (list 'b 'c))
(B C)
> (setf whole (cons 'a part))
(A B C)

圖 12.2 被共享的尾端

現(xiàn)在?whole1?和?whole2?共享結(jié)構(gòu)，但是它們彼此都不是對方的一部分。

當(dāng)存在嵌套列表時，重要的是要區(qū)分是列表共享了結(jié)構(gòu)，還是列表的元素共享了結(jié)構(gòu)。頂層列表結(jié)構(gòu)指的是，直接構(gòu)成列表的那些cons?，而不包含那些用于構(gòu)造列表元素的?cons?。圖 12.3 是一個嵌套列表的頂層列表結(jié)構(gòu) (譯者注：圖 12.3 中上面那三個有黑色陰影的?cons?即構(gòu)成頂層列表結(jié)構(gòu)的?cons?)。

Common Lisp 包含一些允許修改列表結(jié)構(gòu)的函數(shù)。為了提高效率，這些函數(shù)是具有破壞性的。雖然它們可以回收利用作為參數(shù)傳給它們的?cons?，但并不是因為想要它們的副作用而調(diào)用它們 (譯者注：因為這些函數(shù)的副作用并沒有任何保證，下面的例子將說明問題)。

比如，?delete?是?remove?的一個具有破壞性的版本。雖然它可以破壞作為參數(shù)傳給它的列表，但它并不保證什么。在大多數(shù)的 Common Lisp 的實現(xiàn)中，會出現(xiàn)下面的情況：

> (setf lst '(a r a b i a) )
(A R A B I A)
> (delete 'a lst )
(R B I)
> lst
(A R B I)

正如?remove?一樣，如果你想要副作用，應(yīng)該對返回值使用?setf?：

(setf lst (delete 'a lst))

破壞性函數(shù)是怎樣回收利用傳給它們的列表的呢？比如，可以考慮?nconc?——?append?的破壞性版本。[2]下面是兩個參數(shù)版本的實現(xiàn)，其清楚地展示了兩個已知列表是怎樣被縫在一起的：

(defun nconc2 ( x y)
    (if (consp x)
        (progn
           (setf (cdr (last x)) y)
            x)
         y))

我們找到第一個列表的最后一個?Cons?核 (cons cells)，把它的?cdr?設(shè)置成指向第二個列表。一個正規(guī)的多參數(shù)的?nconc?可以被定義成像附錄 B 中的那樣。

函數(shù)?mapcan?類似?mapcar?，但它是用?nconc?把函數(shù)的返回值 (必須是列表) 拼接在一起的：

> (mapcan #'list
          '(a b c)
          '(1 2 3 4))
( A 1 B 2 C 3)

這個函數(shù)可以定義如下：

(defun our-mapcan (fn &rest lsts )
       (apply #'nconc (apply #'mapcar fn lsts)))

使用?mapcan?時要謹(jǐn)慎，因為它具有破壞性。它用?nconc?拼接返回的列表，所以這些列表最好不要再在其它地方使用。

這類函數(shù)在處理某些問題的時候特別有用，比如，收集樹在某層上的所有子結(jié)點。如果?children?函數(shù)返回一個節(jié)點的孩子節(jié)點的列表，那么我們可以定義一個函數(shù)返回某節(jié)點的孫子節(jié)點的列表如下：

(defun grandchildren (x)
   (mapcan #'(lambda (c)
                (copy-list (children c)))
           (children x)))

這個函數(shù)調(diào)用?copy-list?時存在一個假設(shè) ——?chlidren?函數(shù)返回的是一個已經(jīng)保存在某個地方的列表，而不是構(gòu)建了一個新的列表。

一個?mapcan?的無損變體可以這樣定義：

(defun mappend (fn &rest lsts )
    (apply #'append (apply #'mapcar fn lsts)))

如果使用?mappend?函數(shù)，那么?grandchildren?的定義就可以省去?copy-list?：

(defun grandchildren (x)
   (mappend #'children (children x)))

12.5 示例：二叉搜索樹 (Example: Binary Search Trees)

在某些情況下，使用破壞性操作比使用非破壞性的顯得更自然。第 4.7 節(jié)中展示了如何維護(hù)一個具有二分搜索格式的有序?qū)ο蠹?(或者說維護(hù)一個二叉搜索樹 (BST))。第 4.7 節(jié)中給出的函數(shù)都是非破壞性的，但在我們真正使用BST的時候，這是一個不必要的保護(hù)措施。本節(jié)將展示如何定義更符合實際應(yīng)用的具有破壞性的插入函數(shù)和刪除函數(shù)。

圖 12.8 展示了如何定義一個具有破壞性的?bst-insert?(第 72 頁「譯者注：第 4.7 節(jié)」)。相同的輸入?yún)?shù)，能夠得到相同返回值。唯一的區(qū)別是，它將修改作為第二個參數(shù)輸入的 BST。 在第 2.12 節(jié)中說過，具有破壞性并不意味著一個函數(shù)調(diào)用具有副作用。的確如此，如果你想使用?bst-insert!?構(gòu)造一個 BST，你必須像調(diào)用?bst-insert?那樣調(diào)用它：

> (setf *bst* nil)
NIL
> (dolist (x '(7 2 9 8 4 1 5 12))
(setf *bst* (bst-insert! x *bst* #'<)))
NIL

(defun bst-insert! (obj bst <)
  (if (null bst)
      (make-node :elt obj)
      (progn (bsti obj bst <)
             bst)))

(defun bsti (obj bst <)
  (let ((elt (node-elt bst)))
    (if (eql obj elt)
        bst
        (if (funcall < obj elt)
            (let ((l (node-l bst)))
              (if l
                  (bsti obj l <)
                  (setf (node-l bst)
                        (make-node :elt obj))))
            (let ((r (node-r bst)))
              (if r
                  (bsti obj r <)
                  (setf (node-r bst)
                        (make-node :elt obj))))))))

圖 12.8: 二叉搜索樹：破壞性插入

你也可以為 BST 定義一個類似 push 的功能，但這超出了本書的范圍。(好奇的話，可以參考第 409 頁 「譯者注：即備注 204 」 的宏定義。)

與?bst-remove?(第 74 頁「譯者注：第 4.7 節(jié)」) 對應(yīng)，圖 12.9 展示了一個破壞性版本的?bst-delete?。同?delete?一樣，我們調(diào)用它并不是因為它的副作用。你應(yīng)該像調(diào)用?bst-remove?那樣調(diào)用?bst-delete?：

> (setf *bst* (bst-delete 2 *bst* #'<) )
#<7>
> (bst-find 2 *bst* #'<)
NIL

(defun bst-delete (obj bst <)
  (if bst (bstd obj bst nil nil <))
  bst)

(defun bstd (obj bst prev dir <)
  (let ((elt (node-elt bst)))
    (if (eql elt obj)
        (let ((rest (percolate! bst)))
          (case dir
            (:l (setf (node-l prev) rest))
            (:r (setf (node-r prev) rest))))
      (if (funcall < obj elt)
          (if (node-l bst)
              (bstd obj (node-l bst) bst :l <))
          (if (node-r bst)
              (bstd obj (node-r bst) bst :r <))))))

(defun percolate! (bst)
  (cond ((null (node-l bst))
         (if (null (node-r bst))
             nil
             (rperc! bst)))
        ((null (node-r bst)) (lperc! bst))
        (t (if (zerop (random 2))
               (lperc! bst)
               (rperc! bst)))))

(defun lperc! (bst)
  (setf (node-elt bst) (node-elt (node-l bst)))
  (percolate! (node-l bst)))

(defun rperc! (bst)
  (setf (node-elt bst) (node-elt (node-r bst)))
  (percolate! (node-r bst)))

圖 12.9: 二叉搜索樹：破壞性刪除

譯注:?此范例已被回報為錯誤的，一個修復(fù)的版本請造訪這里。

12.6 示例：雙向鏈表 (Example: Doubly-Linked Lists)

普通的 Lisp 列表是單向鏈表，這意味著其指針指向一個方向：我們可以獲取下一個元素，但不能獲取前一個。在雙向鏈表中，指針指向兩個方向，我們獲取前一個元素和下一個元素都很容易。這一節(jié)將介紹如何創(chuàng)建和操作雙向鏈表。

圖 12.10 展示了如何用結(jié)構(gòu)來實現(xiàn)雙向鏈表。將?cons?看成一種結(jié)構(gòu)，它有兩個字段：指向數(shù)據(jù)的?car?和指向下一個元素的?cdr?。要實現(xiàn)一個雙向鏈表，我們需要第三個字段，用來指向前一個元素。圖 12.10 中的?defstruct?定義了一個含有三個字段的對象?dl?(用于“雙向鏈接”)，我們將用它來構(gòu)造雙向鏈表。dl?的?data?字段對應(yīng)一個?cons?的?car，next?字段對應(yīng)?cdr?。?prev?字段就類似一個cdr?，指向另外一個方向。(圖 12.11 是一個含有三個元素的雙向鏈表。) 空的雙向鏈表為?nil?，就像空的列表一樣。

(defstruct (dl (:print-function print-dl))
  prev data next)

(defun print-dl (dl stream depth)
  (declare (ignore depth))
  (format stream "#<DL ~A>" (dl->list dl)))

(defun dl->list (lst)
  (if (dl-p lst)
      (cons (dl-data lst) (dl->list (dl-next lst)))
      lst))

(defun dl-insert (x lst)
  (let ((elt (make-dl :data x :next lst)))
    (when (dl-p lst)
      (if (dl-prev lst)
          (setf (dl-next (dl-prev lst)) elt
                (dl-prev elt) (dl-prev lst)))
      (setf (dl-prev lst) elt))
    elt))

(defun dl-list (&rest args)
  (reduce #'dl-insert args
          :from-end t :initial-value nil))

(defun dl-remove (lst)
  (if (dl-prev lst)
      (setf (dl-next (dl-prev lst)) (dl-next lst)))
  (if (dl-next lst)
      (setf (dl-prev (dl-next lst)) (dl-prev lst)))
  (dl-next lst))

圖 12.10: 構(gòu)造雙向鏈表

因為常量實際上是程序代碼的一部分，所以我們也不應(yīng)該修改他們，或者是不經(jīng)意地寫了自重寫的代碼。一個通過?quote?引用的列表是一個常量，所以一定要小心，不要修改被引用的列表的任何?cons。比如，如果我們用下面的代碼，來測試一個符號是不是算術(shù)運算符：

(defun arith-op (x)
(member x '(+ - * /)))

如果被測試的符號是算術(shù)運算符，它的返回值將至少一個被引用列表的一部分。如果我們修改了其返回值，

> (nconc (arith-op '*) '(as i t were))
(* / AS IT WERE)

那么我就會修改?arith-op?函數(shù)中的一個列表，從而改變了這個函數(shù)的功能：

> (arith-op 'as )
(AS IT WERE)

寫一個返回常量結(jié)構(gòu)的函數(shù)，并不一定是錯誤的。但當(dāng)你考慮使用一個破壞性的操作是否安全的時候，你必須考慮到這一點。

有幾個其它方法來實現(xiàn)?arith-op，使其不返回被引用列表的部分。一般地，我們可以通過將其中的所有引用(?quote?) 替換成?list來確保安全，這使得它每次被調(diào)用都將返回一個新的列表：

(defun arith-op (x)
        (member x (list '+ '- '* '/)))

這里，使用?list?是一種低效的解決方案，我們應(yīng)該使用?find?來替代?member：

(defun arith-op (x)
        (find x '(+ - * /)))

這一節(jié)討論的問題似乎只與列表有關(guān)，但實際上，這個問題存在于任何復(fù)雜的對象中：數(shù)組，字符串，結(jié)構(gòu)，實例等。你不應(yīng)該逐字地去修改程序的代碼段。

即使你想寫自修改程序，通過修改常量來實現(xiàn)并不是個好辦法。編譯器將常量編譯成了代碼，破壞性的操作可能修改它們的參數(shù)，但這些都是沒有任何保證的事情。如果你想寫自修改程序，正確的方法是使用閉包 (見 6.5 節(jié))。

Chapter 12 總結(jié) (Summary)

1. 兩個列表可以共享一個尾端。多個列表可以以樹的形式共享結(jié)構(gòu)，而不是共享頂層列表結(jié)構(gòu)?？赏ㄟ^拷貝方式來避免共用結(jié)構(gòu)。
2. 共享結(jié)構(gòu)通?？梢员缓雎?，但如果你要修改列表，則需要特別注意。因為修改一個含共享結(jié)構(gòu)的列表可能修改所有共享該結(jié)構(gòu)的列表。
3. 隊列可以被表示成一個?cons?，其的?car?指向隊列的第一個元素，?cdr?指向隊列的最后一個元素。
4. 為了提高效率，破壞性函數(shù)允許修改其輸入?yún)?shù)。
5. 在某些應(yīng)用中，破壞性的實現(xiàn)更適用。
6. 列表可以是?car-circular?或?cdr-circular?。 Lisp 可以表示圓形結(jié)構(gòu)和共享結(jié)構(gòu)。
7. 不應(yīng)該去修改的程序代碼段中的常量形式。

Chapter 12 練習(xí) (Exercises)

1. 畫三個不同的樹，能夠被打印成?((A)?(A)?(A))?。寫一個表達(dá)式來生成它們。
2. 假設(shè)?make-queue?，?enqueue?和?dequeue?是按照圖 12.7 中的定義，用箱子表式法畫出下面每一步所得到的隊列的結(jié)構(gòu)圖：

> (setf q (make-queue))
(NIL)
> (enqueue 'a q)
(A)
> (enqueue 'b q)
(A B)
> (dequeue q)
A

1. 定義一個函數(shù)?copy-queue?，可以返回一個 queue 的拷貝。
2. 定義一個函數(shù)，接受兩個輸入?yún)?shù)?object?和?queue?，能將?object?插入到?queue?的首端。
3. 定義一個函數(shù)，接受兩個輸入?yún)?shù)?object?和?queue，能具有破壞性地將?object?的第一個實例 (?eql?等價地) 移到?queue?的首端。
4. 定義一個函數(shù)，接受兩個輸入?yún)?shù)?object?和?lst?(?lst?可能是?cdr-circular?列表)，如果?object?是?lst?的成員時返回真。
5. 定義一個函數(shù)，如果它的參數(shù)是一個?cdr-circular?則返回真。
6. 定義一個函數(shù)，如果它的參數(shù)是一個?car-circular?則返回真。

腳注

[1] | 比如，在 Common Lisp 中，修改一個被用作符號名的字符串被認(rèn)為是一種錯誤，因為內(nèi)部的定義并沒聲明它是從參數(shù)復(fù)制來的，所以必須假定修改傳入內(nèi)部的任何參數(shù)中的字符串來創(chuàng)建新的符號是錯誤的。

[2] | 函數(shù)名稱中 n 的含義是 “non-consing”。一些具有破壞性的函數(shù)以 n 開頭。