第三章：列表

列表是 Lisp 的基本數(shù)據(jù)結(jié)構(gòu)之一。在最早的 Lisp 方言里，列表是唯一的數(shù)據(jù)結(jié)構(gòu)： “Lisp” 這個名字起初是 “LISt Processor” 的縮寫。但 Lisp 已經(jīng)超越這個縮寫很久了。 Common Lisp 是一個有著各式各樣數(shù)據(jù)結(jié)構(gòu)的通用性程序語言。

Lisp 程序開發(fā)通常呼應(yīng)著開發(fā) Lisp 語言自身。在最初版本的 Lisp 程序，你可能使用很多列表。然而之后的版本，你可能換到快速、特定的數(shù)據(jù)結(jié)構(gòu)。本章描述了你可以用列表所做的很多事情，以及使用它們來演示一些普遍的 Lisp 概念。

3.1 構(gòu)造 (Conses)

在 2.4 節(jié)我們介紹了?cons?,?car?, 以及?cdr?，基本的 List 操作函數(shù)。?cons?真正所做的事情是，把兩個對象結(jié)合成一個有兩部分的對象，稱之為?Cons?對象。概念上來說，一個?Cons?是一對指針；第一個是?car?，第二個是?cdr?。

Cons?對象提供了一個方便的表示法，來表示任何類型的對象。一個?Cons?對象里的一對指針，可以指向任何類型的對象，包括?Cons對象本身。它利用到我們之后可以用?cons?來構(gòu)造列表的可能性。

我們往往不會把列表想成是成對的，但它們可以這樣被定義。任何非空的列表，都可以被視為一對由列表第一個元素及列表其余元素所組成的列表。 Lisp 列表體現(xiàn)了這個概念。我們使用?Cons?的一半來指向列表的第一個元素，然后用另一半指向列表其余的元素(可能是別的?Cons?或?nil?)。 Lisp 的慣例是使用?car?代表列表的第一個元素，而用?cdr?代表列表的其余的元素。所以現(xiàn)在?car?是列表的第一個元素的同義詞，而?cdr?是列表的其余的元素的同義詞。列表不是不同的對象，而是像?Cons?這樣的方式連結(jié)起來。

當(dāng)我們想在?nil?上面建立東西時(shí)，

> (setf x (cons 'a nil))
(A)

圖 3.2 三個元素的列表

> (cdr y)
(B C)

在一個有多個元素的列表中，?car?指針讓你取得元素，而?cdr?讓你取得列表內(nèi)其余的東西。

一個列表可以有任何類型的對象作為元素，包括另一個列表：

> (setf z (list 'a (list 'b 'c) 'd))
(A (B C) D)

當(dāng)這種情況發(fā)生時(shí)，它的結(jié)構(gòu)如圖 3.3 所示；第二個?Cons?的?car?指針也指向一個列表：

> (car (cdr z))
(B C)

學(xué)生在學(xué)習(xí)遞歸時(shí)，有時(shí)候是被鼓勵在紙上追蹤 (trace)遞歸程序調(diào)用 (invocation)的過程。 (288頁「譯注：附錄 A 追蹤與回溯」可以看到一個遞歸函數(shù)的追蹤過程。)但這種練習(xí)可能會誤導(dǎo)你：一個程序員在定義一個遞歸函數(shù)時(shí)，通常不會特別地去想函數(shù)的調(diào)用順序所導(dǎo)致的結(jié)果。

如果一個人總是需要這樣子思考程序，遞歸會是艱難的、沒有幫助的。遞歸的優(yōu)點(diǎn)是它精確地讓我們更抽象地來設(shè)計(jì)算法。你不需要考慮真正函數(shù)時(shí)所有的調(diào)用過程，就可以判斷一個遞歸函數(shù)是否是正確的。

要知道一個遞歸函數(shù)是否做它該做的事，你只需要問，它包含了所有的情況嗎？舉例來說，下面是一個尋找列表長度的遞歸函數(shù)：

> (defun len (lst)
    (if (null lst)
        0
        (+ (len (cdr lst)) 1)))

我們可以借由檢查兩件事情，來確信這個函數(shù)是正確的：

1. 對長度為?0?的列表是有效的。
2. 給定它對于長度為?n?的列表是有效的，它對長度是?n+1?的列表也是有效的。

如果這兩點(diǎn)是成立的，我們知道這個函數(shù)對于所有可能的列表都是正確的。

我們的定義顯然地滿足第一點(diǎn)：如果列表(?lst?) 是空的(?nil?)，函數(shù)直接返回?0?。現(xiàn)在假定我們的函數(shù)對長度為?n?的列表是有效的。我們給它一個?n+1?長度的列表。這個定義說明了，函數(shù)會返回列表的?cdr?的長度再加上?1?。?cdr?是一個長度為?n?的列表。我們經(jīng)由假定可知它的長度是?n?。所以整個列表的長度是?n+1?。

我們需要知道的就是這些。理解遞歸的秘密就像是處理括號一樣。你怎么知道哪個括號對上哪個？你不需要這么做。你怎么想像那些調(diào)用過程？你不需要這么做。

更復(fù)雜的遞歸函數(shù)，可能會有更多的情況需要討論，但是流程是一樣的。舉例來說， 41 頁的?our-copy-tree?，我們需要討論三個情況： 原子，單一的?Cons?對象，?n+1?的?Cons?樹。

第一個情況（長度零的列表）稱之為基本用例(?base case?)。當(dāng)一個遞歸函數(shù)不像你想的那樣工作時(shí)，通常是處理基本用例就錯了。下面這個不正確的?member?定義，是一個常見的錯誤，整個忽略了基本用例：

(defun our-member (obj lst)
  (if (eql (car lst) obj)
      lst
      (our-member obj (cdr lst))))

我們需要初始一個?null?測試，確保在到達(dá)列表底部時(shí)，沒有找到目標(biāo)時(shí)要停止遞歸。如果我們要找的對象沒有在列表里，這個版本的?member?會陷入無窮循環(huán)。附錄 A 更詳細(xì)地討論了這種問題。

能夠判斷一個遞歸函數(shù)是否正確只不過是理解遞歸的上半場，下半場是能夠?qū)懗鲆粋€做你想做的事情的遞歸函數(shù)。 6.9 節(jié)討論了這個問題。

3.10 集合 (Sets)

列表是表示小集合的好方法。列表中的每個元素都代表了一個集合的成員：

> (member 'b '(a b c))
(B C)

當(dāng)?member?要返回“真”時(shí)，與其僅僅返回?t?，它返回由尋找對象所開始的那部分。邏輯上來說，一個?Cons?扮演的角色和?t?一樣，而經(jīng)由這么做，函數(shù)返回了更多資訊。

一般情況下，?member?使用?eql?來比較對象。你可以使用一種叫做關(guān)鍵字參數(shù)的東西來重寫缺省的比較方法。多數(shù)的 Common Lisp 函數(shù)接受一個或多個關(guān)鍵字參數(shù)。這些關(guān)鍵字參數(shù)不同的地方是，他們不是把對應(yīng)的參數(shù)放在特定的位置作匹配，而是在函數(shù)調(diào)用中用特殊標(biāo)簽，稱為關(guān)鍵字，來作匹配。一個關(guān)鍵字是一個前面有冒號的符號。

一個?member?函數(shù)所接受的關(guān)鍵字參數(shù)是?:test?參數(shù)。

如果你在調(diào)用?member?時(shí)，傳入某個函數(shù)作為?:test?參數(shù)，那么那個函數(shù)就會被用來比較是否相等，而不是用?eql?。所以如果我們想找到一個給定的對象與列表中的成員是否相等(?equal?)，我們可以：

> (member '(a) '((a) (z)) :test #'equal)
((A) (Z))

關(guān)鍵字參數(shù)總是選擇性添加的。如果你在一個調(diào)用中包含了任何的關(guān)鍵字參數(shù)，他們要擺在最后; 如果使用了超過一個的關(guān)鍵字參數(shù)，擺放的順序無關(guān)緊要。

另一個?member?接受的關(guān)鍵字參數(shù)是?:key?參數(shù)。借由提供這個參數(shù)，你可以在作比較之前，指定一個函數(shù)運(yùn)用在每一個元素：

> (member 'a '((a b) (c d)) :key #'car)
((A B) (C D))

在這個例子里，我們詢問是否有一個元素的?car?是?a?。

如果我們想要使用兩個關(guān)鍵字參數(shù)，我們可以使用其中一個順序。下面這兩個調(diào)用是等價(jià)的：

> (member 2 '((1) (2)) :key #'car :test #'equal)
((2))
> (member 2 '((1) (2)) :test #'equal :key #'car)
((2))

兩者都詢問是否有一個元素的?car?等于(?equal?) 2。

如果我們想要找到一個元素滿足任意的判斷式像是──?oddp?，奇數(shù)返回真──我們可以使用相關(guān)的?member-if?：

> (member-if #'oddp '(2 3 4))
(3 4)

我們可以想像一個限制性的版本?member-if?是這樣寫成的：

(defun our-member-if (fn lst)
  (and (consp lst)
       (if (funcall fn (car lst))
           lst
           (our-member-if fn (cdr lst)))))

函數(shù)?adjoin?像是條件式的?cons?。它接受一個對象及一個列表，如果對象還不是列表的成員，才構(gòu)造對象至列表上。

> (adjoin 'b '(a b c))
(A B C)
> (adjoin 'z '(a b c))
(Z A B C)

通常的情況下它接受與?member?函數(shù)同樣的關(guān)鍵字參數(shù)。

集合論中的并集 (union)、交集 (intersection)以及補(bǔ)集 (complement)的實(shí)現(xiàn)，是由函數(shù)?union?、?intersection?以及?set-difference?。

這些函數(shù)期望兩個（正好 2 個）列表（一樣接受與?member?函數(shù)同樣的關(guān)鍵字參數(shù)）。

> (union '(a b c) '(c b s))
(A C B S)
> (intersection '(a b c) '(b b c))
(B C)
> (set-difference '(a b c d e) '(b e))
(A C D)

因?yàn)榧现袥]有順序的概念，這些函數(shù)不需要保留原本元素在列表被找到的順序。舉例來說，調(diào)用?set-difference?也有可能返回(d?c?a)?。

3.11 序列 (Sequences)

另一種考慮一個列表的方式是想成一系列有特定順序的對象。在 Common Lisp 里，序列(?sequences?)包括了列表與向量 (vectors)。本節(jié)介紹了一些可以運(yùn)用在列表上的序列函數(shù)。更深入的序列操作在 4.4 節(jié)討論。

函數(shù)?length?返回序列中元素的數(shù)目。

> (length '(a b c))
3

我們在 24 頁 (譯注：2.13節(jié)?our-length?)寫過這種函數(shù)的一個版本（僅可用于列表）。

要復(fù)制序列的一部分，我們使用?subseq?。第二個（需要的）參數(shù)是第一個開始引用進(jìn)來的元素位置，第三個（選擇性）參數(shù)是第一個不引用進(jìn)來的元素位置。

> (subseq '(a b c d) 1 2)
(B)
>(subseq '(a b c d) 1)
(B C D)

如果省略了第三個參數(shù)，子序列會從第二個參數(shù)給定的位置引用到序列尾端。

函數(shù)?reverse?返回與其參數(shù)相同元素的一個序列，但順序顛倒。

> (reverse '(a b c))
(C B A)

一個回文 (palindrome) 是一個正讀反讀都一樣的序列 —— 舉例來說，?(abba)?。如果一個回文有偶數(shù)個元素，那么后半段會是前半段的鏡射 (mirror)。使用?length?、?subseq?以及?reverse?，我們可以定義一個函數(shù)

(defun mirror? (s)
  (let ((len (length s)))
    (and (evenp len)
         (let ((mid (/ len 2)))
           (equal (subseq s 0 mid)
                  (reverse (subseq s mid)))))))

來檢測是否是回文：

> (mirror? '(a b b a))
T

Common Lisp 有一個內(nèi)置的排序函數(shù)叫做?sort?。它接受一個序列及一個比較兩個參數(shù)的函數(shù)，返回一個有同樣元素的序列，根據(jù)比較函數(shù)來排序：

> (sort '(0 2 1 3 8) #'>)
(8 3 2 1 0)

你要小心使用?sort?，因?yàn)樗?em>破壞性的(destructive)。考慮到效率的因素，?sort?被允許修改傳入的序列。所以如果你不想你本來的序列被改動，傳入一個副本。

使用?sort?及?nth?，我們可以寫一個函數(shù)，接受一個整數(shù)?n?，返回列表中第?n?大的元素：

(defun nthmost (n lst)
  (nth (- n 1)
       (sort (copy-list lst) #'>)))

我們把整數(shù)減一因?yàn)?nth?是零索引的，但如果?nthmost?是這樣的話，會變得很不直觀。

(nthmost 2 '(0 2 1 3 8))

多努力一點(diǎn)，我們可以寫出這個函數(shù)的一個更有效率的版本。

函數(shù)?every?和?some?接受一個判斷式及一個或多個序列。當(dāng)我們僅輸入一個序列時(shí)，它們測試序列元素是否滿足判斷式：

> (every #'oddp '(1 3 5))
T
> (some #'evenp '(1 2 3))
T

如果它們輸入多于一個序列時(shí)，判斷式必須接受與序列一樣多的元素作為參數(shù)，而參數(shù)從所有序列中一次提取一個：

> (every #'> '(1 3 5) '(0 2 4))
T

如果序列有不同的長度，最短的那個序列，決定需要測試的次數(shù)。

3.12 棧 (Stacks)

用?Cons?對象來表示的列表，很自然地我們可以拿來實(shí)現(xiàn)下推棧 (pushdown stack)。這太常見了，以致于 Common Lisp 提供了兩個宏給堆使用：?(push?x?y)?把?x?放入列表?y?的前端。而?(pop?x)?則是將列表 x 的第一個元素移除，并返回這個元素。

兩個函數(shù)都是由?setf?定義的。如果參數(shù)是常數(shù)或變量，很簡單就可以翻譯出對應(yīng)的函數(shù)調(diào)用。

表達(dá)式

(push?obj?lst)

等同于

(setf?lst?(cons?obj?lst))

而表達(dá)式

(pop?lst)

等同于

(let ((x (car lst)))
  (setf lst (cdr lst))
  x)

所以，舉例來說：

> (setf x '(b))
(B)
> (push 'a x)
(A B)
> x
(A B)
> (setf y x)
(A B)
> (pop x)
(A)
> x
(B)
> y
(A B)

以上，全都遵循上述由?setf?所給出的相等式。圖 3.9 展示了這些表達(dá)式被求值后的結(jié)構(gòu)。

[4]?，以及一個關(guān)聯(lián)列表來表示網(wǎng)絡(luò)本身。

3.16 垃圾 (Garbages)

有很多原因可以使列表變慢。列表提供了順序存取而不是隨機(jī)存取，所以列表取出一個指定的元素比數(shù)組慢，同樣的原因，錄音帶取出某些東西比在光盤上慢。電腦內(nèi)部里，?Cons?對象傾向于用指針表示，所以走訪一個列表意味著走訪一系列的指針，而不是簡單地像數(shù)組一樣增加索引值。但這兩個所花的代價(jià)與配置及回收?Cons?核 (cons cells)比起來小多了。

自動內(nèi)存管理(Automatic memory management)是 Lisp 最有價(jià)值的特色之一。 Lisp 系統(tǒng)維護(hù)著一段內(nèi)存稱之為堆(Heap)。系統(tǒng)持續(xù)追蹤堆當(dāng)中沒有使用的內(nèi)存，把這些內(nèi)存發(fā)放給新產(chǎn)生的對象。舉例來說，函數(shù)?cons?，返回一個新配置的?Cons?對象。從堆中配置內(nèi)存有時(shí)候通稱為?consing?。

如果內(nèi)存永遠(yuǎn)沒有釋放， Lisp 會因?yàn)閯?chuàng)建新對象把內(nèi)存用完，而必須要關(guān)閉。所以系統(tǒng)必須周期性地通過搜索堆 (heap)，尋找不需要再使用的內(nèi)存。不需要再使用的內(nèi)存稱之為垃圾 (garbage)，而清除垃圾的動作稱為垃圾回收 (garbage collection或 GC)。

垃圾是從哪來的？讓我們來創(chuàng)造一些垃圾：

> (setf lst (list 'a 'b 'c))
(A B C)
> (setf lst nil)
NIL

一開始我們調(diào)用?list?，?list?調(diào)用?cons?，在堆上配置了一個新的?Cons?對象。在這個情況我們創(chuàng)出三個?Cons?對象。之后當(dāng)我們把lst?設(shè)為?nil?，我們沒有任何方法可以再存取?lst?，列表?(a?b?c)?。?[5]

因?yàn)槲覀儧]有任何方法再存取列表，它也有可能是不存在的。我們不再有任何方式可以存取的對象叫做垃圾。系統(tǒng)可以安全地重新使用這三個?Cons?核。

這種管理內(nèi)存的方法，給程序員帶來極大的便利性。你不用顯式地配置 (allocate)或釋放 (dellocate)內(nèi)存。這也表示了你不需要處理因?yàn)檫@么做而可能產(chǎn)生的臭蟲。內(nèi)存泄漏 (Memory leaks)以及迷途指針 (dangling pointer)在 Lisp 中根本不可能發(fā)生。

但是像任何的科技進(jìn)步，如果你不小心的話，自動內(nèi)存管理也有可能對你不利。使用及回收堆所帶來的代價(jià)有時(shí)可以看做?cons?的代價(jià)。這是有理的，除非一個程序從來不丟棄任何東西，不然所有的?Cons?對象終究要變成垃圾。 Consing 的問題是，配置空間與清除內(nèi)存，與程序的常規(guī)運(yùn)作比起來花費(fèi)昂貴。近期的研究提出了大幅改善內(nèi)存回收的演算法，但是 consing 總是需要代價(jià)的，在某些現(xiàn)有的 Lisp 系統(tǒng)中，代價(jià)是昂貴的。

除非你很小心，不然很容易寫出過度顯式創(chuàng)建 cons 對象的程序。舉例來說，?remove?需要復(fù)制所有的?cons?核，直到最后一個元素從列表中移除。你可以借由使用破壞性的函數(shù)避免某些 consing，它試著去重用列表的結(jié)構(gòu)作為參數(shù)傳給它們。破壞性函數(shù)會在 12.4 節(jié)討論。

當(dāng)寫出?cons?很多的程序是如此簡單時(shí)，我們還是可以寫出不使用?cons?的程序。典型的方法是寫出一個純函數(shù)風(fēng)格，使用很多列表的第一版程序。當(dāng)程序進(jìn)化時(shí)，你可以在代碼的關(guān)鍵部分使用破壞性函數(shù)以及/或別種數(shù)據(jù)結(jié)構(gòu)。但這很難給出通用的建議，因?yàn)橛行?Lisp 實(shí)現(xiàn)，內(nèi)存管理處理得相當(dāng)好，以致于使用?cons?有時(shí)比不使用?cons?還快。這整個議題在 13.4 做更進(jìn)一步的細(xì)部討論。

無論如何 consing 在原型跟實(shí)驗(yàn)時(shí)是好的。而且如果你利用了列表給你帶來的靈活性，你有較高的可能寫出后期可存活下來的程序。

Chapter 3 總結(jié) (Summary)

1. 一個?Cons?是一個含兩部分的數(shù)據(jù)結(jié)構(gòu)。列表用鏈結(jié)在一起的?Cons?組成。
2. 判斷式?equal?比?eql?來得不嚴(yán)謹(jǐn)?；旧?，如果傳入?yún)?shù)印出來的值一樣時(shí)