第四章：特殊數(shù)據(jù)結(jié)構(gòu)

在之前的章節(jié)里，我們討論了列表，Lisp 最多功能的數(shù)據(jù)結(jié)構(gòu)。本章將演示如何使用 Lisp 其它的數(shù)據(jù)結(jié)構(gòu)：數(shù)組（包含向量與字符串），結(jié)構(gòu)以及哈希表。它們或許不像列表這么靈活，但存取速度更快并使用了更少空間。

Common Lisp 還有另一種數(shù)據(jù)結(jié)構(gòu)：實例（instance）。實例將在 11 章討論，講述 CLOS。

4.1 數(shù)組 (Array)

在 Common Lisp 里，你可以調(diào)用?make-array?來構(gòu)造一個數(shù)組，第一個實參為一個指定數(shù)組維度的列表。要構(gòu)造一個?2?x?3?的數(shù)組，我們可以：

> (setf arr (make-array '(2 3) :initial-element nil))
#<Simple-Array T (2 3) BFC4FE>

Common Lisp 的數(shù)組至少可以達到七個維度，每個維度至少可以容納 1023 個元素。

:initial-element?實參是選擇性的。如果有提供這個實參，整個數(shù)組會用這個值作為初始值。若試著取出未初始化的數(shù)組內(nèi)的元素，其結(jié)果為未定義（undefined）。

用?aref?取出數(shù)組內(nèi)的元素。與 Common Lisp 的存取函數(shù)一樣，?aref?是零索引的（zero-indexed）：

> (aref arr 0 0)
NIL

要替換數(shù)組的某個元素，我們使用?setf?與?aref?：

> (setf (aref arr 0 0) 'b)
B
> (aref arr 0 0)
B

要表示字面常量的數(shù)組（literal array），使用?#na?語法，其中?n?是數(shù)組的維度。舉例來說，我們可以這樣表示?arr?這個數(shù)組：

#2a((b nil nil) (nil nil nil))

如果全局變量?*print-array*?為真，則數(shù)組會用以下形式來顯示：

> (setf *print-array* t)
T
> arr
#2A((B NIL NIL) (NIL NIL NIL))

如果我們只想要一維的數(shù)組，你可以給?make-array?第一個實參傳一個整數(shù)，而不是一個列表：

> (setf vec (make-array 4 :initial-element nil))
#(NIL NIL NIL NIL)

一維數(shù)組又稱為向量（vector）。你可以通過調(diào)用?vector?來一步驟構(gòu)造及填滿向量，向量的元素可以是任何類型：

> (vector "a" 'b 3)
#("a" b 3)

字面常量的數(shù)組可以表示成?#na?，字面常量的向量也可以用這種語法表達。

可以用?aref?來存取向量，但有一個更快的函數(shù)叫做?svref?，專門用來存取向量。

> (svref vec 0)
NIL

在?svref?內(nèi)的 “sv” 代表“簡單向量”（“simple vector”），所有的向量缺省是簡單向量。?[1]

4.2 示例：二叉搜索 (Example: Binary Search)

作為一個示例，這小節(jié)演示如何寫一個在排序好的向量里搜索對象的函數(shù)。如果我們知道一個向量是排序好的，我們可以比（65頁）find?做的更好，?find?必須依序檢查每一個元素。我們可以直接跳到向量中間開始找。如果中間的元素是我們要找的對象，搜索完畢。要不然我們持續(xù)往左半部或往右半部搜索，取決于對象是小于或大于中間的元素。

圖 4.1 包含了一個這么工作的函數(shù)。其實這兩個函數(shù)：?bin-search?設(shè)置初始范圍及發(fā)送控制信號給?finder?，?finder?尋找向量?vec內(nèi)?obj?是否介于?start?及?end?之間。

(defun bin-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1)))))

(defun finder (obj vec start end)
  (let ((range (- end start)))
    (if (zerop range)
        (if (eql obj (aref vec start))
            obj
            nil)
        (let ((mid (+ start (round (/ range 2)))))
          (let ((obj2 (aref vec mid)))
            (if (< obj obj2)
                (finder obj vec start (- mid 1))
                (if (> obj obj2)
                    (finder obj vec (+ mid 1) end)
                    obj)))))))

圖 4.1: 搜索一個排序好的向量

如果要找的?range?縮小至一個元素，而如果這個元素是?obj?的話，則?finder?直接返回這個元素，反之返回?nil?。如果?range?大于1?，我們設(shè)置?middle?(?round?返回離實參最近的整數(shù)) 為?obj2?。如果?obj?小于?obj2?，則遞歸地往向量的左半部尋找。如果?obj大于?obj2?，則遞歸地往向量的右半部尋找。剩下的一個選擇是?obj=obj2?，在這個情況我們找到要找的元素，直接返回這個元素。

如果我們插入下面這行至?finder?的起始處：

(format t "~A~%" (subseq vec start (+ end 1)))

我們可以觀察被搜索的元素的數(shù)量，是每一步往左減半的：

> (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
#(0 1 2 3)
#(3)
3

4.3 字符與字符串 (Strings and Characters)

字符串是字符組成的向量。我們用一系列由雙引號包住的字符，來表示一個字符串常量，而字符?c?用?#\c?表示。

每個字符都有一個相關(guān)的整數(shù) ── 通常是 ASCII 碼，但不一定是。在多數(shù)的 Lisp 實現(xiàn)里，函數(shù)?char-code?返回與字符相關(guān)的數(shù)字，而?code-char?返回與數(shù)字相關(guān)的字符。

字符比較函數(shù)?char<?（小于），?char<=?（小于等于)，?char=?（等于)，?char>=?（大于等于) ，?char>?（大于)，以及?char/=?（不同)。他們的工作方式和 146 頁（譯注 9.3 節(jié))比較數(shù)字用的操作符一樣。

> (sort "elbow" #'char<)
"below"

由于字符串是字符向量，序列與數(shù)組的函數(shù)都可以用在字符串。你可以用?aref?來取出元素，舉例來說，

> (aref "abc" 1)
#\b

但針對字符串可以使用更快的?char?函數(shù)：

> (char "abc" 1)
#\b

可以使用?setf?搭配?char?（或?aref?）來替換字符串的元素：

> (let ((str (copy-seq "Merlin")))
   (setf (char str 3) #\k)
   str)

如果你想要比較兩個字符串，你可以使用通用的?equal?函數(shù)，但還有一個比較函數(shù)，是忽略字母大小寫的?string-equal?：

> (equal "fred" "fred")
T
> (equal "fred" "Fred")
NIL
>(string-equal "fred" "Fred")
T

Common Lisp 提供大量的操控、比較字符串的函數(shù)。收錄在附錄 D，從 364 頁開始。

有許多方式可以創(chuàng)建字符串。最普遍的方式是使用?format?。將第一個參數(shù)設(shè)為?nil?來調(diào)用?format?，使它返回一個原本會印出來的字符串：

> (format nil "~A or ~A" "truth" "dare")
"truth or dare"

但若你只想把數(shù)個字符串連結(jié)起來，你可以使用?concatenate?，它接受一個特定類型的符號，加上一個或多個序列：

> (concatenate 'string "not " "to worry")
"not to worry"

4.4 序列 (Sequences)

在 Common Lisp 里，序列類型包含了列表與向量（因此也包含了字符串）。有些用在列表的函數(shù)，實際上是序列函數(shù)，包括remove?、?length?、?subseq?、?reverse?、?sort?、?every?以及?some?。所以 46 頁（譯注 3.11 小節(jié)的?mirror??函數(shù)）我們所寫的函數(shù)，也可以用在其他種類的序列上：

> (mirror? "abba")
T

我們已經(jīng)看過四種用來取出序列元素的函數(shù)： 給列表使用的?nth?， 給向量使用的?aref?及?svref?，以及給字符串使用的?char?。 Common Lisp 也提供了通用的?elt?，對任何種類的序列都有效：

> (elt '(a b c) 1)
B

針對特定類型的序列，特定的存取函數(shù)會比較快，所以使用?elt?是沒有意義的，除非在代碼當中，有需要支持通用序列的地方。

使用?elt?，我們可以寫一個針對向量來說更有效率的?mirror??版本：

(defun mirror? (s)
  (let ((len (length s)))
    (and (evenp len)
         (do ((forward 0 (+ forward 1))
              (back (- len 1) (- back 1)))
             ((or (> forward back)
                  (not (eql (elt s forward)
                            (elt s back))))
              (> forward back))))))

這個版本也可用在列表，但這個實現(xiàn)更適合給向量使用。頻繁的對列表調(diào)用?elt?的代價是昂貴的，因為列表僅允許順序存取。而向量允許隨機存取，從任何元素來存取每一個元素都是廉價的。

許多序列函數(shù)接受一個或多個，由下表所列的標準關(guān)鍵字參數(shù)：

參數(shù)	用途	缺省值
:key	應(yīng)用至每個元素的函數(shù)	identity
:test	作來比較的函數(shù)	eql
:from-end	若為真，反向工作。	nil
:start	起始位置	0
:end	若有給定，結(jié)束位置。	nil

一個接受所有關(guān)鍵字參數(shù)的函數(shù)是?position?，返回序列中一個元素的位置，未找到元素時則返回?nil?。我們使用?position?來演示關(guān)鍵字參數(shù)所扮演的角色。

> (position #\a "fantasia")
1
> (position #\a "fantasia" :start 3 :end 5)
4

第二個例子我們要找在第四個與第六個字符間，第一個?a?所出現(xiàn)的位置。?:start?關(guān)鍵字參數(shù)是第一個被考慮的元素位置，缺省是序列的第一個元素。?:end?關(guān)鍵字參數(shù)，如果有給的話，是第一個不被考慮的元素位置。

如果我們給入?:from-end?關(guān)鍵字參數(shù)，

> (position #\a "fantasia" :from-end t)
7

我們得到最靠近結(jié)尾的?a?的位置。但位置是像平常那樣計算；而不是從尾端算回來的距離。

:key?關(guān)鍵字參數(shù)是序列中每個元素在被考慮之前，應(yīng)用至元素上的函數(shù)。如果我們說，

> (position 'a '((c d) (a b)) :key #'car)
1

那么我們要找的是，元素的?car?部分是符號?a?的第一個元素。

:test?關(guān)鍵字參數(shù)接受需要兩個實參的函數(shù)，并定義了怎樣是一個成功的匹配。缺省函數(shù)為?eql?。如果你想要匹配一個列表，你也許想使用?equal?來取代：

> (position '(a b) '((a b) (c d)))
NIL
> (position '(a b) '((a b) (c d)) :test #'equal)
0

:test?關(guān)鍵字參數(shù)可以是任何接受兩個實參的函數(shù)。舉例來說，給定?<?，我們可以詢問第一個使第一個參數(shù)比它小的元素位置：

> (position 3 '(1 0 7 5) :test #'<)
2

使用?subseq?與?position?，我們可以寫出分開序列的函數(shù)。舉例來說，這個函數(shù)

(defun second-word (str)
  (let ((p1 (+ (position #\  str) 1)))
    (subseq str p1 (position #\  str :start p1))))

返回字符串中第一個單字空格后的第二個單字：

> (second-word "Form follows function")
"follows"

要找到滿足謂詞的元素，其中謂詞接受一個實參，我們使用?position-if?。它接受一個函數(shù)與序列，并返回第一個滿足此函數(shù)的元素：

> (position-if #'oddp '(2 3 4 5))
1

position-if?接受除了?:test?之外的所有關(guān)鍵字參數(shù)。

有許多相似的函數(shù)，如給序列使用的?member?與?member-if?。分別是，?find?（接受全部關(guān)鍵字參數(shù)）與?find-if?（接受除了?:test之外的所有關(guān)鍵字參數(shù)）：

> (find #\a "cat")
#\a

> (find-if #'characterp "ham")
#\h

不同于?member?與?member-if?，它們僅返回要尋找的對象。

通常一個?find-if?的調(diào)用，如果解讀為?find?搭配一個?:key?關(guān)鍵字參數(shù)的話，會顯得更清楚。舉例來說，表達式

(find-if #'(lambda (x)
             (eql (car x) 'complete))
         lst)

可以更好的解讀為

(find 'complete lst :key #'car)

函數(shù)?remove?（22 頁）以及?remove-if?通常都可以用在序列。它們跟?find?與?find-if?是一樣的關(guān)系。另一個相關(guān)的函數(shù)是remove-duplicates?，僅保留序列中每個元素的最后一次出現(xiàn)。

> (remove-duplicates "abracadabra")
"cdbra"

這個函數(shù)接受前表所列的所有關(guān)鍵字參數(shù)。

函數(shù)?reduce?用來把序列壓縮成一個值。它至少接受兩個參數(shù)，一個函數(shù)與序列。函數(shù)必須是接受兩個實參的函數(shù)。在最簡單的情況下，一開始函數(shù)用序列前兩個元素作為實參來調(diào)用，之后接續(xù)的元素作為下次調(diào)用的第二個實參，而上次返回的值作為下次調(diào)用的第一個實參。最后調(diào)用最終返回的值作為?reduce?整個函數(shù)的返回值。也就是說像是這樣的表達式：

(reduce #'fn '(a b c d))

等同于

(fn (fn (fn 'a 'b) 'c) 'd)

我們可以使用?reduce?來擴充只接受兩個參數(shù)的函數(shù)。舉例來說，要得到三個或多個列表的交集(intersection)，我們可以：

> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
(A)

4.5 示例：解析日期 (Example: Parsing Dates)

作為序列操作的示例，本節(jié)演示了如何寫程序來解析日期。我們將編寫一個程序，可以接受像是 “16 Aug 1980” 的字符串，然后返回一個表示日、月、年的整數(shù)列表。

(defun tokens (str test start)
  (let ((p1 (position-if test str :start start)))
    (if p1
        (let ((p2 (position-if #'(lambda (c)
                                   (not (funcall test c)))
                               str :start p1)))
          (cons (subseq str p1 p2)
                (if p2
                    (tokens str test p2)
                    nil)))
        nil)))

(defun constituent (c)
  (and (graphic-char-p c)
       (not (char= c #\ ))))

圖 4.2 辨別符號 (token)

圖 4.2 里包含了某些在這個應(yīng)用里所需的通用解析函數(shù)。第一個函數(shù)?tokens?，用來從字符串中取出語元 （token）。給定一個字符串及測試函數(shù)，滿足測試函數(shù)的字符組成子字符串，子字符串再組成列表返回。舉例來說，如果測試函數(shù)是對字母返回真的?alpha-char-p?函數(shù)，我們得到：

> (tokens "ab12 3cde.f" #'alpha-char-p 0)
("ab" "cde" "f")

所有不滿足此函數(shù)的字符被視為空白 ── 他們是語元的分隔符，但永遠不是語元的一部分。

函數(shù)?constituent?被定義成用來作為?tokens?的實參。

在 Common Lisp 里，圖形字符是我們可見的字符，加上空白字符。所以如果我們用?constituent?作為測試函數(shù)時，

> (tokens "ab12 3cde.f gh" #'constituent 0)
("ab12" "3cde.f" "gh")

則語元將會由空白區(qū)分出來。

圖 4.3 包含了特別為解析日期打造的函數(shù)。函數(shù)?parse-date?接受一個特別形式組成的日期，并返回代表這個日期的整數(shù)列表：

> (parse-date "16 Aug 1980")
(16 8 1980)

(defun parse-date (str)
  (let ((toks (tokens str #'constituent 0)))
    (list (parse-integer (first toks))
          (parse-month (second toks))
          (parse-integer (third toks)))))

(defconstant month-names
  #("jan" "feb" "mar" "apr" "may" "jun"
    "jul" "aug" "sep" "oct" "nov" "dec"))

(defun parse-month (str)
  (let ((p (position str month-names
                         :test #'string-equal)))
    (if p
        (+ p 1)
        nil)))

圖 4.3 解析日期的函數(shù)

parse-date?使用?tokens?來解析日期字符串，接著調(diào)用?parse-month?及?parse-integer?來轉(zhuǎn)譯年、月、日。要找到月份，調(diào)用parse-month?，由于使用的是?string-equal?來匹配月份的名字，所以輸入可以不分大小寫。要找到年和日，調(diào)用內(nèi)置的?parse-integer?，?parse-integer?接受一個字符串并返回對應(yīng)的整數(shù)。

如果需要自己寫程序來解析整數(shù)，也許可以這么寫：

(defun read-integer (str)
  (if (every #'digit-char-p str)
      (let ((accum 0))
        (dotimes (pos (length str))
          (setf accum (+ (* accum 10)
                         (digit-char-p (char str pos)))))
        accum)
    nil))

這個定義演示了在 Common Lisp 中，字符是如何轉(zhuǎn)成數(shù)字的 ── 函數(shù)?digit-char-p?不僅測試字符是否為數(shù)字，同時返回了對應(yīng)的整數(shù)。

4.6 結(jié)構(gòu) (Structures)

結(jié)構(gòu)可以想成是豪華版的向量。假設(shè)你要寫一個程序來追蹤長方體。你可能會想用三個向量元素來表示長方體：高度、寬度及深度。與其使用原本的?svref?，不如定義像是下面這樣的抽象，程序會變得更容易閱讀，

(defun block-height (b) (svref b 0))

而結(jié)構(gòu)可以想成是，這些函數(shù)通通都替你定義好了的向量。

要想定義結(jié)構(gòu)，使用?defstruct?。在最簡單的情況下，只要給出結(jié)構(gòu)及字段的名字便可以了：

(defstruct point
  x
  y)

這里定義了一個?point?結(jié)構(gòu)，具有兩個字段?x?與?y?。同時隱式地定義了?make-point?、?point-p?、?copy-point?、?point-x?及point-y?函數(shù)。

2.3 節(jié)提過， Lisp 程序可以寫出 Lisp 程序。這是目前所見的明顯例子之一。當你調(diào)用?defstruct?時，它自動生成了其它幾個函數(shù)的定義。有了宏以后，你將可以自己來辦到同樣的事情（如果需要的話，你甚至可以自己寫出?defstruct?）。

每一個?make-point?的調(diào)用，會返回一個新的?point??？梢酝ㄟ^給予對應(yīng)的關(guān)鍵字參數(shù)，來指定單一字段的值：

(setf p (make-point :x 0 :y 0))
#S(POINT X 0 Y 0)

存取?point?字段的函數(shù)不僅被定義成可取出數(shù)值，也可以搭配?setf?一起使用。

> (point-x p)
0
> (setf (point-y p) 2)
2
> p
#S(POINT X 0 Y 2)

定義結(jié)構(gòu)也定義了以結(jié)構(gòu)為名的類型。每個點的類型層級會是，類型?point?，接著是類型?structure?，再來是類型?atom?，最后是t?類型。所以使用?point-p?來測試某個東西是不是一個點時，也可以使用通用性的函數(shù)，像是?typep?來測試。

> (point-p p)
T
> (typep p 'point)
T

我們可以在本來的定義中，附上一個列表，含有字段名及缺省表達式，來指定結(jié)構(gòu)字段的缺省值。

(defstruct polemic
  (type (progn
          (format t "What kind of polemic was it? ")
          (read)))
  (effect nil))

如果?make-polemic?調(diào)用沒有給字段指定初始值，則字段會被設(shè)成缺省表達式的值：

> (make-polemic)
What kind of polemic was it? scathing
#S(POLEMIC :TYPE SCATHING :EFFECT NIL)

結(jié)構(gòu)顯示的方式也可以控制，以及結(jié)構(gòu)自動產(chǎn)生的存取函數(shù)的字首。以下是做了前述兩件事的?point?定義：

(defstruct (point (:conc-name p)
                  (:print-function print-point))
  (x 0)
  (y 0))

(defun print-point (p stream depth)
  (format stream "#<~A, ~A>" (px p) (py p)))

:conc-name?關(guān)鍵字參數(shù)指定了要放在字段前面的名字，并用這個名字來生成存取函數(shù)。預設(shè)是?point-?；現(xiàn)在變成只有?p?。不使用缺省的方式使代碼的可讀性些微降低了，只有在需要常常用到這些存取函數(shù)時，你才會想取個短點的名字。

:print-function?是在需要顯示結(jié)構(gòu)出來看時，指定用來打印結(jié)構(gòu)的函數(shù) ── 需要顯示的情況比如，要在頂層顯示時。這個函數(shù)需要接受三個實參：要被印出的結(jié)構(gòu)，在哪里被印出，第三個參數(shù)通常可以忽略。?[2]?我們會在 7.1 節(jié)討論流（stream）?，F(xiàn)在來說，只要知道流可以作為參數(shù)傳給?format?就好了。

函數(shù)?print-point?會用縮寫的形式來顯示點：

> (make-point)
#<0,0>

4.7 示例：二叉搜索樹 (Example: Binary Search Tree)

由于?sort?本身系統(tǒng)就有了，極少需要在 Common Lisp 里編寫排序程序。本節(jié)將演示如何解決一個與此相關(guān)的問題，這個問題尚未有現(xiàn)成的解決方案：維護一個已排序的對象集合。本節(jié)的代碼會把對象存在二叉搜索樹里（?binary search tree?）或稱作 BST。當二叉搜索樹平衡時，允許我們可以在與時間成?log?n?比例的時間內(nèi)，來尋找、添加或是刪除元素，其中?n?是集合的大小。

第三章演示過列表可以用來表示集合（sets）與映射（mappings）。但當列表的長度大幅上升時（或是 10 個元素），使用哈希表的速度比較快。你通過調(diào)用?make-hash-table?來構(gòu)造一個哈希表，它不需要傳入?yún)?shù)：

> (setf ht (make-hash-table))
#<Hash-Table BF0A96>

和函數(shù)一樣，哈希表總是用?#<...>?的形式來顯示。

一個哈希表，與一個關(guān)聯(lián)列表類似，是一種表達對應(yīng)關(guān)系的方式。要取出與給定鍵值有關(guān)的數(shù)值，我們調(diào)用?gethash?并傳入一個鍵值與哈希表。預設(shè)情況下，如果沒有與這個鍵值相關(guān)的數(shù)值，?gethash?會返回?nil?。

> (gethash 'color ht)
NIL
NIL

在這里我們首次看到 Common Lisp 最突出的特色之一：一個表達式竟然可以返回多個數(shù)值。函數(shù)?gethash?返回兩個數(shù)值。第一個值是與鍵值有關(guān)的數(shù)值，第二個值說明了哈希表是否含有任何用此鍵值來儲存的數(shù)值。由于第二個值是?nil?，我們知道第一個?nil是缺省的返回值，而不是因為?nil?是與?color?有關(guān)的數(shù)值。

大部分的實現(xiàn)會在頂層顯示一個函數(shù)調(diào)用的所有返回值，但僅期待一個返回值的代碼，只會收到第一個返回值。 5.5 節(jié)會說明，代碼如何接收多個返回值。

要把數(shù)值與鍵值作關(guān)聯(lián)，使用?gethash?搭配?setf?：

> (setf (gethash 'color ht) 'red)
RED

現(xiàn)在如果我們再次調(diào)用?gethash?，我們會得到我們剛插入的值：

> (gethash 'color ht)
RED
T

第二個返回值證明，我們?nèi)〉昧艘粋€真正儲存的對象，而不是預設(shè)值。

存在哈希表的對象或鍵值可以是任何類型。舉例來說，如果我們要保留函數(shù)的某種訊息，我們可以使用哈希表，用函數(shù)作為鍵值，字符串作為詞條（entry）：

> (setf bugs (make-hash-table))
#<Hash-Table BF4C36>
> (push "Doesn't take keyword arguments."
        (gethash #'our-member bugs))
("Doesn't take keyword arguments.")

由于?gethash?缺省返回?nil?，而?push?是?setf?的縮寫，可以輕松的給哈希表新添一個詞條。 （有困擾的?our-member?定義在 16 頁。）

可以用哈希表來取代用列表表示集合。當集合變大時，哈希表的查詢與移除會來得比較快。要新增一個成員到用哈希表所表示的集合，把?gethash?用?setf?設(shè)成?t?：

> (setf fruit (make-hash-table))
#<Hash-Table BFDE76>
> (setf (gethash 'apricot fruit) t)
T

然后要測試是否為成員，你只要調(diào)用：

> (gethash 'apricot fruit)
T
T

由于?gethash?缺省返回真，一個新創(chuàng)的哈希表，會很方便地是一個空集合。

要從集合中移除一個對象，你可以調(diào)用?remhash?，它從一個哈希表中移除一個詞條：

> (remhash 'apricot fruit)
T

返回值說明了是否有詞條被移除；在這個情況里，有。

哈希表有一個迭代函數(shù)：?maphash?，它接受兩個實參，接受兩個參數(shù)的函數(shù)以及哈希表。該函數(shù)會被每個鍵值對調(diào)用，沒有特定的順序：

> (setf (gethash 'shape ht) 'spherical
        (gethash 'size ht) 'giant)
GIANT

> (maphash #'(lambda (k v)
               (format t "~A = ~A~%" k v))
           ht)
SHAPE = SPHERICAL
SIZE = GIANT
COLOR = RED
NIL

maphash?總是返回?nil?，但你可以通過傳入一個會累積數(shù)值的函數(shù)，把哈希表的詞條存在列表里。

哈希表可以容納任何數(shù)量的元素，但當哈希表空間用完時，它們會被擴張。如果你想要確保一個哈希表，從特定數(shù)量的元素空間大小開始時，可以給?make-hash-table?一個選擇性的?:size?關(guān)鍵字參數(shù)。做這件事情有兩個理由：因為你知道哈希表會變得很大，你想要避免擴張它；或是因為你知道哈希表會是很小，你不想要浪費內(nèi)存。?:size?參數(shù)不僅指定了哈希表的空間，也指定了元素的數(shù)量。平均來說，在被擴張前所能夠容納的數(shù)量。所以

(make-hash-table?:size?5)

會返回一個預期存放五個元素的哈希表。

和任何牽涉到查詢的結(jié)構(gòu)一樣，哈希表一定有某種比較鍵值的概念。預設(shè)是使用?eql?，但你可以提供一個額外的關(guān)鍵字參數(shù)?:test來告訴哈希表要使用?eq?，?equal?，還是?equalp?：

> (setf writers (make-hash-table :test #'equal))
#<Hash-Table C005E6>
> (setf (gethash '(ralph waldo emerson) writers) t)
T

這是一個讓哈希表變得有效率的取舍之一。有了列表，我們可以指定?member?為判斷相等性的謂詞。有了哈希表，我們可以預先決定，并在哈希表構(gòu)造時指定它。

大多數(shù) Lisp 編程的取舍（或是生活，就此而論）都有這種特質(zhì)。起初你想要事情進行得流暢，甚至賠上效率的代價。之后當代碼變得沉重時，你犧牲了彈性來換取速度。

Chapter 4 總結(jié) (Summary)

1. Common Lisp 支持至少 7 個維度的數(shù)組。一維數(shù)組稱為向量。
2. 字符串是字符的向量。字符本身就是對象。
3. 序列包括了向量與列表。許多序列函數(shù)都接受標準的關(guān)鍵字參數(shù)。
4. 處理字符串的函數(shù)非常多，所以用 Lisp 來解析字符串是小菜一碟。
5. 調(diào)用?defstruct?定義了一個帶有命名字段的結(jié)構(gòu)。它是一個程序能寫出程序的好例子。
6. 二叉搜索樹見長于維護一個已排序的對象集合。
7. 哈希表提供了一個更有效率的方式來表示集合與映射 (mappings)。

Chapter 4 習題 (Exercises)

1. 定義一個函數(shù)，接受一個平方數(shù)組（square array，一個相同維度的數(shù)組?(n?n)?)，并將它順時針轉(zhuǎn) 90 度。

> (quarter-turn #2A((a b) (c d)))
#2A((C A) (D B))

你會需要用到 361 頁的?array-dimensions?。

1. 閱讀 368 頁的?reduce?說明，然后用它來定義：

(a) copy-list
(b) reverse（針對列表）

1. 定義一個結(jié)構(gòu)來表示一棵樹，其中每個節(jié)點包含某些數(shù)據(jù)及三個小孩。定義：

(a) 一個函數(shù)來復制這樣的樹（復制完的節(jié)點與本來的節(jié)點是不相等（ `eql` ）的）
(b) 一個函數(shù)，接受一個對象與這樣的樹，如果對象與樹中各節(jié)點的其中一個字段相等時，返回真。

1. 定義一個函數(shù)，接受一棵二叉搜索樹，并返回由此樹元素所組成的，一個由大至小排序的列表。
2. 定義?bst-adjoin?。這個函數(shù)應(yīng)與?bst-insert?接受相同的參數(shù)，但應(yīng)該只在對象不等于任何樹中對象時將其插入。

勘誤:?bst-adjoin?的功能與?bst-insert?一模一樣。

1. 任何哈希表的內(nèi)容可以由關(guān)聯(lián)列表（assoc-list）來描述，其中列表的元素是?(k?.?v)?的形式，對應(yīng)到哈希表中的每一個鍵值對。定義一個函數(shù)：

(a) 接受一個關(guān)聯(lián)列表，并返回一個對應(yīng)的哈希表。
(b) 接受一個哈希表，并返回一個對應(yīng)的關(guān)聯(lián)列表。

腳注

[1] | 一個簡單數(shù)組大小是不可調(diào)整、元素也不可替換的，并不含有填充指針（fill-pointer）。數(shù)組缺省是簡單的。簡單向量是個一維的簡單數(shù)組，可以含有任何類型的元素。

[2] | 在 ANSI Common Lisp 里，你可以給一個?:print-object?的關(guān)鍵字參數(shù)來取代，它只需要兩個實參。也有一個宏叫做print-unreadable-object?，能用則用，可以用?#<...>?的語法來顯示對象。