第 5 章 函數(shù)作為返回值

第 5 章 函數(shù)作為返回值

上一章展示了 Lisp "把函數(shù)作為參數(shù)傳遞" 的能力，它開(kāi)闊了我們進(jìn)行抽象的思路。我們對(duì)函數(shù)能做的事情越多，就越能充分利用這些思想方法。如果能定義一種函數(shù)，讓它產(chǎn)生并返回新的函數(shù)，那就可以成倍放大那些以函數(shù)作為參數(shù)的實(shí)用工具的威力。

這一章要介紹的實(shí)用工具就被用來(lái)操作函數(shù)。要是把它們中的多數(shù)寫成宏，讓這些宏來(lái)操縱表達(dá)式會(huì)顯得更自然一些，至少在 Common Lisp 里是這樣的。在第 15 章會(huì)把一層宏加到這些操作符之上。不管怎樣，就算最終這些函數(shù)僅僅被宏調(diào)用，"了解哪些工作能由函數(shù)來(lái)完成" 這一點(diǎn)也至關(guān)重要。

5.1 Common Lisp 的演化

Common Lisp 最初提供了幾組互補(bǔ)的函數(shù)。remove-if 和 remove-if-not 就是這樣的一對(duì)。倘若 pred 是一個(gè)參數(shù)的謂詞，那么:

(remove-if-not #'pred lst)

就和下面語(yǔ)句等價(jià):

(remove-if #'(lambda (x) (not (pred x))) lst)

只要把其中一個(gè)語(yǔ)句的函數(shù)參數(shù)換一下，就能獲得和另一語(yǔ)句完全相同的效果。既然如此，為什么要同時(shí)保留兩個(gè)語(yǔ)句呢?C???2 里提供了一個(gè)新的函數(shù)，它就是為了解決上述問(wèn)題而生的： complement 需要一個(gè)謂詞 p 作為參數(shù)，它返回一個(gè)函數(shù)，這個(gè)函數(shù)的返回值總是和謂詞得到的返回值相反。當(dāng)p 返回真的時(shí)候， 它的補(bǔ)（complement） 就返回假，反之亦然?，F(xiàn)在我們可以把:

(remove-if-not #'pred lst)

換成與之等價(jià)的:

(remove-if (complement #'pred) lst)

有了 complement ，就沒(méi)有什么理由再用那些-if-not 函數(shù)了。 事實(shí)上， ???2（391 頁(yè)） 提到那些函數(shù)現(xiàn)在已經(jīng)淘汰了。如果它們還在 Common Lisp 里面，那只是為了照顧兼容性。

新的complement 操作符僅是冰山一角： 即一種返回函數(shù)的函數(shù)。這在很早就是 Scheme 的習(xí)慣用法中重要的一部分了。Scheme 是Lisp 家族中第一個(gè)能把函數(shù)作為詞法閉包（lexicalclosures） 的語(yǔ)言，而且正是這一點(diǎn)讓"函數(shù)作為返回值" 變得有趣起來(lái)。

這并不意味著我們不能在動(dòng)態(tài)作用域的Lisp 里返回函數(shù)。下面的函數(shù)能同時(shí)在動(dòng)態(tài)作用域和詞法作用域下工作：

(defun joiner (obj)
 (typecase obj
  (cons #'append)
  (number #'+)))

上面的函數(shù)以一個(gè)對(duì)象作為參數(shù)，按照參數(shù)的類型，返回相應(yīng)的函數(shù)把這種對(duì)象累加起來(lái)。通過(guò)它，我們可以定義一個(gè)多態(tài)（polymorphic） 的join 函數(shù)，這個(gè)函數(shù)可以用于一組數(shù)字或者列表。

remove-if-not 可能是個(gè)例外，它比remove-if 更常用一些。

(defun join (&rest args)
(apply (joiner (car args)) args))

然而，"只能返回一個(gè)常量函數(shù)" 是動(dòng)態(tài)作用域的限制之一。由于這個(gè)限制， 我們所無(wú)法做到（或者說(shuō)無(wú)法做得好） 的是在運(yùn)行期構(gòu)造函數(shù)： 盡管joiner 可以返回兩個(gè)函數(shù)之一，但是這兩個(gè)選擇是事先給定的，無(wú)法變更。

在第12頁(yè)，我們見(jiàn)到了另一個(gè)用來(lái)返回函數(shù)的函數(shù)，它就依賴于詞法作用域：

(defun make-adder (n)
#'(lambda (x) (+ x n)))

調(diào)用make-adder 后，會(huì)得到一個(gè)閉包，閉包的行為視當(dāng)初傳入函數(shù)的參數(shù)值而定：

> (setq add3 (make-adder 3))
#<Interpreted-Function BF1356>
> (funcall add3 2)
5

在詞法作用域下，我們不再僅僅是從一組預(yù)先確定的函數(shù)中選一個(gè)，而是在運(yùn)行時(shí)創(chuàng)造新的閉包。但要是動(dòng)態(tài)作用域的話，這個(gè)技術(shù)就行不通了。 如果想一想complement 是怎么寫的，也可以推知它返回的必定也是一個(gè)閉包：

(defun complement (fn)
#'(lambda (&rest args) (not (apply fn args))))

complement 返回的函數(shù)使用了之前調(diào)用complement 時(shí)傳入的參數(shù)值fn。因此，complement 不再只是從幾個(gè)常量函數(shù)里挑一個(gè)返回，而是定制了一個(gè)函數(shù)，讓它返回任何函數(shù)的反：

> (remove-if (complement #'oddp) '(1 2 3 4 5 6))
(1 3 5)

在進(jìn)行抽象時(shí)，把函數(shù)作為參數(shù)的能力不啻為一個(gè)強(qiáng)有力的工具。而能夠編寫返回函數(shù)的函數(shù)，讓我們可以把這個(gè)能力發(fā)揮到極致。接下來(lái)的幾個(gè)小節(jié)將會(huì)展示幾個(gè)實(shí)用工具的例子， 它們都是能返回函數(shù)的函數(shù)。

5.2 正交性

正交的語(yǔ)言讓我們只需運(yùn)用多種方式對(duì)數(shù)量有限的操作符加以組合，就能獲得強(qiáng)大的表達(dá)能力。玩具積木是非常正交的，而套裝塑料模型就很難說(shuō)它是正交的。complement 的主要優(yōu)點(diǎn)就是它讓語(yǔ)言更正交化。在complement 出現(xiàn)之前，Common Lisp 曾有成對(duì)的函數(shù)，如remove-if 和remove-if-not、subst-if 和subst-if-not ，等等。自從有了complement ，我們可以只用一半數(shù)量的函數(shù)就完成全部的功能。

同樣，setf 宏也增強(qiáng)了Lisp 的正交性。Lisp 的早期方言常會(huì)用成對(duì)的函數(shù)分別實(shí)現(xiàn)讀數(shù)據(jù)和寫數(shù)據(jù)的功能。舉例來(lái)說(shuō)，對(duì)于屬性列表（property-list），就用一個(gè)函數(shù)設(shè)置屬性，而用另一個(gè)函數(shù)來(lái)查詢屬性。

在Common Lisp 里面，我們只有后者，即get 。為了加入一個(gè)屬性，我們把get 和 setf 一同使用：

(setf (get 'ball 'color) 'red)

我們或許無(wú)法讓Common Lisp 變得更精簡(jiǎn)，但是可以作些努力達(dá)到差不多的效果，即： 使用這門語(yǔ)言的一個(gè)較小的子集。可以定義一些新的操作符，讓它們像complement 和setf 那樣幫助我們更接近這個(gè)目標(biāo)嗎 至少另外還有一種方式讓函數(shù)成對(duì)出現(xiàn)。許多函數(shù)都有其破壞性（destructive） 的版本： 像remove-if 和delete-if、reverse 和nreverse、append 和nconc 。定義一個(gè)操作符，讓它返回一個(gè)函數(shù)的破壞性版本，這樣就可以不直接使用那些破壞性的函數(shù)了。

或許在動(dòng)態(tài)作用域里可以寫出類似 make-adder 的代碼，但是它基本上不會(huì)正常工作。由于 的綁定將取決于函數(shù)最終被調(diào)用時(shí)所處的環(huán)境，因此我們對(duì)這個(gè)過(guò)程很難有什么控制。

(defvar *!equivs* (make-hash-table))

(defun ! (fn)
(or (gethash fn *!equivs*) fn))

(defun def! (fn fn!)
(setf (gethash fn *!equivs*) fn!))

圖5.1： 返回破壞性的等價(jià)物

圖5.1 中的代碼實(shí)現(xiàn)了破壞性版本的標(biāo)記。全局的哈希表!equivs?把函數(shù)映射到其對(duì)應(yīng)的破壞性版

本； !返回函數(shù)的破壞性版本； 最后，def! 更新和設(shè)置它們。之所以用 !（驚嘆號(hào)） 的原因，是源于Scheme 的一個(gè)命名習(xí)慣。在Scheme 里面，有副作用的函數(shù)名后面都會(huì)加上 !?，F(xiàn)在，我們一旦定義了

(def! #'remove-if #'delete-if)

就可以把

(delete-if #'oddp lst)

取而代之，換成

(funcall (! #'remove-if) #'oddp lst)

上面的代碼中，Common Lisp 有些許尷尬，它模糊了這個(gè)思路的良好初衷，要是用Scheme 就明了多了：

((! remove-if) oddp lst)

除了更強(qiáng)的正交性，!操作符還帶來(lái)了一系列其它的好處。它讓程序更清晰明了，因?yàn)槲覀兛梢砸幌伦泳涂闯鰜?lái) （! #'foo）是與foo 對(duì)應(yīng)的破壞性版本。另外，它還讓破壞性操作在源代碼里總是一目了然。這樣的好處在于當(dāng)我們?cè)谡襜ug 時(shí)，會(huì)更小心這些地方。

由于函數(shù)及其對(duì)應(yīng)的破壞性版本的取舍經(jīng)常在運(yùn)行期之前就能確定下來(lái)， 因此把!定義成一個(gè)宏會(huì)是最高效的選擇，或者也可以為它提供一個(gè)讀取宏（readmacro）。

5.3 記住過(guò)去

如果某些函數(shù)的計(jì)算量非常大，而且我們有時(shí)會(huì)對(duì)它們執(zhí)行相同的調(diào)用，這時(shí)"記住過(guò)去" 就有用了： 就是讓函數(shù)把所有以往調(diào)用的返回值都緩存下來(lái)， 以后每次調(diào)用時(shí)，都先在緩存里找一下，看看返回值是不是以前算過(guò)。

(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal))))
#'(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
val
(setf (gethash args cache)
(apply fn args))))))

圖5.2： 記憶性的實(shí)用工具

圖5.2 中展示了一個(gè)通用化了的記憶性實(shí)用工具。我們傳給memoize 一個(gè)函數(shù)，它就能返回對(duì)應(yīng)的有記憶

的版本 即一個(gè)閉包，該閉包含有存儲(chǔ)以往調(diào)用結(jié)果的哈希表。

> (setq slowid (memoize #'(lambda (x) (sleep 5) x)))
#<Interpreted-Function C38346>
> (time (funcall slowid 1))
Elapsed Time = 5.15 seconds
1
> (time (funcall slowid 1))
Elapsed Time = 0.00 seconds
1

有了具有記憶的函數(shù)，重復(fù)的調(diào)用就變成哈希表的查找操作。當(dāng)然，這也帶來(lái)了每次調(diào)用開(kāi)始時(shí)進(jìn)行查找導(dǎo)致的額外開(kāi)銷，但是既然我們只會(huì)把那些計(jì)算開(kāi)銷足夠大的函數(shù)進(jìn)行記憶化的處理， 那么就可以認(rèn)為付出這個(gè)代價(jià)是值得的。

盡管對(duì)絕大多數(shù)情況來(lái)說(shuō)，這個(gè)memoize 實(shí)現(xiàn)已經(jīng)夠好了，不過(guò)它還是有些局限。它認(rèn)為只有參數(shù)列表equal 的調(diào)用才是等同的，這個(gè)要求可能對(duì)那些有關(guān)鍵字參數(shù)的函數(shù)過(guò)于嚴(yán)格了。而且這個(gè)函數(shù)僅適用于那些返回單值的函數(shù)，因而無(wú)法保存多值，更不用說(shuō)返回了。

5.4 復(fù)合函數(shù)

函數(shù) 的補(bǔ)被記為～ 。第5.1 節(jié)展示了使用閉包可以將～ 定義為一個(gè)Lisp 函數(shù)的可能性。另一個(gè)常見(jiàn)的函數(shù)操作是復(fù)合，它被記作?。如果 和 是兩個(gè)函數(shù)，那么 ? 也是函數(shù)，并且 ? 。同樣的，通過(guò)使用閉包的方式，也可以把? 定義為一個(gè)Lisp 函數(shù)。

(defun compose (&rest fns)
(if fns
(let ((fn1 (car (last fns)))
(fns (butlast fns)))
#'(lambda (&rest args)
(reduce #'funcall fns
:from-end t
:initial-value (apply fn1 args))))
#'identity))

圖5.3： 復(fù)合函數(shù)的操作符

圖5.3 定義了一個(gè)名為 compose 的函數(shù)，它接受任意數(shù)量的函數(shù)，并返回它們的復(fù)合。比如說(shuō)

(compose #'list #'1+)

會(huì)返回一個(gè)函數(shù)，該函數(shù)等價(jià)于

#'(lambda (x) (list (1+ x)))

? 所有傳給compose 作為參數(shù)的函數(shù)都必須只接受一個(gè)參數(shù)，不過(guò)最后一個(gè)函數(shù)參數(shù)可以例外。它沒(méi)有這樣的限制，不管這個(gè)函數(shù)接受什么樣的參數(shù)，都會(huì)返回復(fù)合后的函數(shù)：

> (funcall (compose #'1+ #'find-if) #'oddp '(2 3 4))
4

由于not 是一個(gè)Lisp 函數(shù)，所以complement 是 compose 的特例。它可以這樣定義：

(defun complement (pred)
(compose #'not pred))

把函數(shù)結(jié)合在一起使用的方法并不止復(fù)合一種。舉例來(lái)說(shuō)，我們經(jīng)常會(huì)看到下面這樣的表達(dá)式

(mapcar #'(lambda (x)
(if (slave x)
(owner x)
(employer x)))
people)

也可以定義操作符，借助它來(lái)自動(dòng)地構(gòu)造這種函數(shù)。用圖5.4 中定義的fif， 下面的語(yǔ)句一樣可以達(dá)到這種效果：

(mapcar (fif #'slave #'owner #'employer)
people)

(defun fif (if then &optional else)
#'(lambda (x)
(if (funcall if x)
(funcall then x)
(if else (funcall else x)))))

(defun fint (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fint fns)))
#'(lambda (x)
(and (funcall fn x) (funcall chain x))))))

(defun fun (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fun fns)))
#'(lambda (x)
(or (funcall fn x) (funcall chain x))))))

圖5.4： 更多的函數(shù)構(gòu)造操作符

圖5.3 中給出的幾種構(gòu)造函數(shù)被用來(lái)生成常見(jiàn)的函數(shù)類型。其中第二個(gè)構(gòu)造函數(shù)是為下面的情形預(yù)備的：

(find-if #'(lambda (x)
(and (signed x) (sealed x) (delivered x)))
docs)

作為第二個(gè)參數(shù)傳給find-if 的謂詞函數(shù)定義了一個(gè)由三個(gè)謂詞確定的交集，這三個(gè)謂詞將會(huì)在這個(gè)謂詞函數(shù)里被調(diào)用。fint 的名字取意"functionintersection"， 借助它，可以把代碼寫成這樣：

(find-if (fint #'signed #'sealed #'delivered) docs)

另外，我們還可以定義類似的操作符，讓它返回一組謂詞操作的并集。fun 與fint 類似，不過(guò)前者用的是or 而非and。

5.5 在cdr 上遞歸

由于遞歸函數(shù)對(duì)于Lisp 程序非常之重要，因此有必要設(shè)計(jì)一些實(shí)用工具來(lái)構(gòu)造它。本節(jié)和下一節(jié)將會(huì)介紹一些函數(shù)，它們能構(gòu)造兩種最常用的遞歸函數(shù)。在Common Lisp 里使用這些函數(shù)會(huì)顯得有些不自然。

一旦我們接觸到宏的內(nèi)容，就可以了解如何把這個(gè)機(jī)制包裝得更優(yōu)雅一些。第15.2 節(jié)和 15.3 節(jié)將會(huì)介紹那些用來(lái)生成遞歸函數(shù)的宏。

如果同一個(gè)模式在程序里頻頻出現(xiàn)，這就是一個(gè)標(biāo)志，它意味著這個(gè)程序應(yīng)該用更高層次的抽象改寫。

在Lisp 程序里，有什么模式比下面這個(gè)函數(shù)更常見(jiàn)的呢：

(defun our-length (lst)
(if (null lst)
0
(1+ (our-length (cdr lst)))))

或者比這個(gè)函數(shù)更眼熟：

(defun our-every (fn lst)
(if (null lst)
t
(and (funcall fn (car lst))
(our-every fn (cdr lst)))))

這兩個(gè)函數(shù)在結(jié)構(gòu)上有頗多共同點(diǎn)。它們兩個(gè)都遞歸地在一個(gè)列表的cdr 上依次操作，每一步對(duì)同一個(gè)表達(dá)式求值，不過(guò)初始條件下除外，初始條件下兩個(gè)函數(shù)都會(huì)返回一個(gè)特定的值。這種模式在Lisp 程序中屢次出現(xiàn)，使得有經(jīng)驗(yàn)的程序員能夠不假思索地讀懂或?qū)懗鲞@樣的代碼。事實(shí)上，我們可以從這個(gè)例子中迅速吸取教訓(xùn)，即為什么把一個(gè)模式封裝成新的抽象層的需求遲遲沒(méi)有出現(xiàn)，其原因就在于習(xí)慣成自然。

不管怎么樣，它仍然還是一個(gè)模式。我們不應(yīng)再直接手寫這些函數(shù)，而該轉(zhuǎn)而設(shè)計(jì)一個(gè)新的函數(shù)，由它代勞生成函數(shù)的工作。圖5.5 中的函數(shù)構(gòu)造器名叫l(wèi)rec （"listrecurser"），它可以滿足那些在列表上對(duì)其cdr 進(jìn)行遞歸操作的絕大多數(shù)需要。

(defun lrec (rec &optional base)
(labels ((self (lst)
(if (null lst)
(if (functionp base)
(funcall base)
base)
(funcall rec (car lst)
#'(lambda ()
(self (cdr lst)))))))
#'self))

圖5.5： 用來(lái)定義線性列表的遞歸函數(shù)的函數(shù)

lrec 的第一個(gè)參數(shù)必須是一個(gè)接受兩個(gè)參數(shù)的函數(shù)，一個(gè)參數(shù)是列表的當(dāng)前car，另一個(gè)參數(shù)是個(gè)函數(shù)，通過(guò)調(diào)用這個(gè)函數(shù)，遞歸得以進(jìn)行。有了lrec， 可以把our-length 寫成：

(lrec #'(lambda (x f) (1+ (funcall f))) 0)

為了得到列表的長(zhǎng)度，我們不需要關(guān)心列表中的元素到底是什么，也不會(huì)中途停止，因此對(duì)象x 的值總是被忽略不用，而函數(shù)f 卻總是被調(diào)用。不過(guò)我們需要同時(shí)利用這兩個(gè)可能性才能重寫our-every。舉例來(lái)說(shuō)， 可以用oddp：

(lrec #'(lambda (x f) (and (oddp x) (funcall f))) t)

在lrec 的定義里使用了labels 來(lái)生成一個(gè)局部的遞歸函數(shù)，函數(shù)名叫 self。如果要執(zhí)行遞歸，會(huì)傳兩個(gè)參數(shù)給rec 函數(shù)，兩個(gè)參數(shù)分別是當(dāng)前列表的car，和一個(gè)含有遞歸調(diào)用的函數(shù)。以our-every 為例，是否繼續(xù)遞歸由and 決定。如果and 的第一個(gè)參數(shù)返回的是假，那么就此中止。換句話說(shuō)，傳到遞歸結(jié)構(gòu)里面的不能是個(gè)值，而只能是函數(shù)。這樣才能獲得返回值 （如果有需要的話）。

圖5.6 展示了一些用lrec 定義的 Common Lisp 的內(nèi)建函數(shù)。? 用lrec 定義的函數(shù)，其效率并不一定會(huì)最理想。事實(shí)上，用lrec 和其它本章將要定義的其它遞歸函數(shù)生成器的方法來(lái)實(shí)現(xiàn)函數(shù)的辦法，是與尾遞歸的思想背道而馳的。鑒于這個(gè)原因，這些生成器最適合在程序的最初版本里使用，或者用在那些速度不太關(guān)鍵的地方。

在一個(gè)使用較廣的Common Lisp 實(shí)現(xiàn)中，functionp 在碰到t 和nil 時(shí)都會(huì)返回真。在這個(gè)實(shí)現(xiàn)下，不管把這兩個(gè)值中哪一個(gè)作為第二個(gè)參數(shù)傳給lrec 都無(wú)法使程序正常工作。

?在一些實(shí)現(xiàn)里，如果要顯示這些函數(shù)，你必須事先把?print-circle?設(shè)置成t 。

; copy-list
(lrec #'(lambda (x f) (cons x (funcall f))))

; remove-duplicates
(lrec #'(lambda (x f) (adjoin x (funcall f))))

; find-if,for some function fn
(lrec #'(lambda (x f) (if (fn x) x (funcall f))))

; some,for some function fn
(lrec #'(lambda (x f) (or (fn x) (funcall f))))

圖5.6： 用lrec 生成的函數(shù)

5.6 在子樹(shù)上遞歸

在Lisp 程序里還有另外一種常用的遞歸形式： 即在子樹(shù)上進(jìn)行遞歸。當(dāng)你開(kāi)始使用嵌套列表，而且希望遞歸地訪問(wèn)列表的car 和cdr 之時(shí)， 這種遞歸形式就出現(xiàn)了。

a

b

a nil

b c

a b c nil d nil

(a) (a b) (b) (a b c) (c) (a b (c d))

圖5.7： 用列表表示的樹(shù)

Lisp 的列表是一種全能型的數(shù)據(jù)結(jié)構(gòu)。舉例來(lái)說(shuō)，列表能表示序列，集合，映射，數(shù)組， 以及樹(shù)。目前有幾種不同的方法來(lái)用列表表示樹(shù)。最常用的一種是把列表看作二叉樹(shù)，二叉樹(shù)的左子樹(shù)是car，右子樹(shù)則是cdr。

（實(shí)際上，這往往就是列表的內(nèi)部實(shí)現(xiàn)。） 圖5.7 中有三個(gè)例子，分別展示了列表以及它們所表示的樹(shù)。其中，樹(shù)上的每個(gè)內(nèi)部節(jié)點(diǎn)都對(duì)應(yīng)著相應(yīng)列表的點(diǎn)對(duì)表示中的一個(gè)點(diǎn)，因而把列表看成下面的形式能更容易理解這種的樹(shù)型結(jié)構(gòu)：

(a b c) = (a . (b . (c . nil)))
(a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))

任意列表都可以看成一顆二叉樹(shù)。同樣的，Common Lisp 里也有其它一些成對(duì)的函數(shù)，它們之間的區(qū)別

與copy-list 和copy-tree 兩者的區(qū)別類似。前者把列表當(dāng)作一個(gè)序列來(lái)處理，即如果碰到列表中含有子列表的情況，那么子列表作為序列里的元素，是不會(huì)被復(fù)制的：

> (setq x '(a b)
listx (list x 1))
((A B) 1)
> (eq x (car (copy-list listx)))
T

與之相對(duì)，copy-tree 會(huì)把列表當(dāng)成樹(shù)來(lái)拷貝，即把子列表視為子樹(shù)， 所以子列表也一樣會(huì)被復(fù)制：

> (eq x (car (copy-tree listx)))
NIL

我們可以自己定義一個(gè)copy-tree ，見(jiàn)下面的代碼：

(defun our-copy-tree (tree)
(if (atom tree)
tree
(cons (our-copy-tree (car tree))
(if (cdr tree) (our-copy-tree (cdr tree))))))

可以看出，上面的定義是一種常用模式的特例。（接下來(lái)，有些函數(shù)的寫法會(huì)稍顯不自然，這是為了讓這個(gè)模式變得更明顯一些。） 不妨看看下面的例子，它能夠統(tǒng)計(jì)出一棵樹(shù)里葉子節(jié)點(diǎn)的數(shù)量：

(defun count-leaves (tree)
(if (atom tree)
1
(1+ (count-leaves (car tree))
(or (if (cdr tree) (count-leaves (cdr tree)))
1))))

一棵樹(shù)上的葉子數(shù)會(huì)多于當(dāng)它被表示成列表的形式時(shí)列表中原子的數(shù)量。

> (count-leaves '((a b (c d)) (e) f))
10

而樹(shù)用點(diǎn)對(duì)的形式來(lái)表示時(shí)，你可以注意到樹(shù)上每個(gè)葉子都對(duì)應(yīng)一個(gè)原子。在點(diǎn)對(duì)表示中，（（a b （c d）） （e） f） 中有四個(gè)nil 是在列表表示中看不到的（每對(duì)括弧都有一個(gè)），所以count-leaves 的返回值是10。

在上一章中，我們定義了幾個(gè)用來(lái)操作樹(shù)的實(shí)用工具。比如說(shuō)，flatten （第32 頁(yè)） 接受一顆樹(shù)，并返回一個(gè)含有樹(shù)上所有原子的列表。換句話說(shuō)，如果你傳給flatten 一個(gè)嵌套列表，你所得到的返回列表和前面的列表形式相同，不過(guò)除了最外面那對(duì)之外，其它的括弧都不見(jiàn)了：

> (flatten '((a b (c d)) (e) f ()))
(A B C D E F)

這個(gè)函數(shù)也可以像下面那樣定義（盡管效率有點(diǎn)低）：

(defun flatten (tree)
(if (atom tree)
(mklist tree)
(nconc (flatten (car tree))
(if (cdr tree) (flatten (cdr tree))))))

最后，看一下rfind-if ，它是find-if 的遞歸版本。rfind-if 不僅能用在線性的列表上，而且對(duì)樹(shù)也一樣適用：

(defun rfind-if (fn tree)
(if (atom tree)
(and (funcall fn tree) tree)
(or (rfind-if fn (car tree))
(if (cdr tree) (rfind-if fn (cdr tree))))))

為了讓find-if 的應(yīng)用范圍更廣，使之能用于樹(shù)結(jié)構(gòu)，必須在兩者中擇一： 讓它僅僅搜索葉子節(jié)點(diǎn)，或是搜? 索整個(gè)子樹(shù)。我們的rfind-if 選擇了前者，因而調(diào)用方就可以認(rèn)為：作為第一個(gè)參數(shù)傳入的函數(shù)只會(huì)用在原子上：

> (rfind-if (fint #'numberp #'oddp) '(2 (3 4) 5))
3

copy-tree ，count-leaves ，flatten 和 rfind-if ，這四個(gè)函數(shù)的形式竟然如此相似。實(shí)際上，它們都是某個(gè)原型函數(shù)的特例，這個(gè)原型函數(shù)被用來(lái)進(jìn)行子樹(shù)上的遞歸操作。和之前對(duì)待cdr 上遞歸的態(tài)度一樣，我們不希望讓這個(gè)原型默默無(wú)聞地埋沒(méi)在代碼當(dāng)中， 相反，我們要寫一個(gè)函數(shù)來(lái)產(chǎn)生這種原型函數(shù)的實(shí)例。

要得到原型本身，讓我們先研究一下這些函數(shù)，找出哪些部分是不屬于模式的。從根本上來(lái)說(shuō)，our-copy-tree 有兩種情形：

1. 基本的情況下，函數(shù)直接把參數(shù)作為返回值返回

2. 在遞歸的時(shí)候，函數(shù)對(duì)左子樹(shù)（car） 的遞歸結(jié)果和右子樹(shù)（cdr） 的遞歸結(jié)果使用cons

因此，我們肯定可以通過(guò)調(diào)用一個(gè)有兩個(gè)參數(shù)的構(gòu)造函數(shù)，來(lái)表示our-copy-tree：

(ttrav #'cons #'identity)

圖5.8 中為ttrav （"treetraverser"） 的一種實(shí)現(xiàn)。在遞歸的情況下，我們傳入的不是一個(gè)值，而是兩個(gè)，一個(gè)

對(duì)應(yīng)左子樹(shù)，一個(gè)對(duì)應(yīng)右子樹(shù)。如果base 參數(shù)是個(gè)函數(shù)，那么將把當(dāng)前葉子節(jié)點(diǎn)作為參數(shù)傳給它。在對(duì)線性列表進(jìn)行遞歸操作時(shí)，基本情況的返回值總是nil ，不過(guò)在樹(shù)結(jié)構(gòu)的遞歸操作中，基本情況的值有可能是個(gè)更有意思的值，而且我們也許會(huì)需要用到它。

在ttrav 的幫助下，我們可以重新定義除rfind-if 之外前面提到的所有函數(shù)。（這些函數(shù)在圖5.9 中可以找到。） 要定義rfind-if ，需要更通用的樹(shù)結(jié)構(gòu)遞歸操作函數(shù)的生成器， 這種函數(shù)生成器能讓我們控制遞歸調(diào)用發(fā)生的時(shí)機(jī)，以及是否繼續(xù)遞歸。我們把一個(gè)函數(shù)作為傳給ttrav 的第一個(gè)參數(shù)，這個(gè)函數(shù)的參數(shù)將是遞歸調(diào)用的返回值。對(duì)于通常的情形， 我們會(huì)改用另一個(gè)函數(shù)，讓它接受兩個(gè)閉包，閉包分別自行表示調(diào)用操作。這樣，就可以編寫那些能自主控制遞歸過(guò)程的遞歸函數(shù)了。

(defun ttrav (rec &optional (base #'identity))
(labels ((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec (self (car tree))
(if (cdr tree)
(self (cdr tree)))))))
#'self))

圖5.8： 為在樹(shù)上進(jìn)行遞歸操作而設(shè)計(jì)的函數(shù)

; our-copy-tree
(ttrav #'cons)

; count-leaves
(ttrav #'(lambda (l r) (+ l (or r 1))) 1)

; flatten
(ttrav #'nconc #'mklist)

圖5.9： 用ttrav 表示的函數(shù)

用ttrav 實(shí)現(xiàn)的函數(shù)通常會(huì)遍歷整顆樹(shù)。這樣做對(duì)于像 count-leaves 或者flatten 這樣的函數(shù)是沒(méi)有問(wèn)題的， 它們不管如何都會(huì)遍歷全樹(shù)。然而，我們需要rfind-if 一發(fā)現(xiàn)它所要找的元素就停止遍歷。這個(gè)函數(shù)必須交給更通用的trec 來(lái)生成， 見(jiàn)圖5.10。trec 的第二個(gè)參數(shù)應(yīng)當(dāng)是一個(gè)具有三個(gè)參數(shù)的函數(shù)，三個(gè)參數(shù)分別是： 當(dāng)前的對(duì)象，以及兩個(gè)遞歸調(diào)用。后兩個(gè)參數(shù)將是用來(lái)表示對(duì)左子樹(shù)和右子樹(shù)進(jìn)行遞歸的兩個(gè)閉包。使用trec 我們可以這樣定義flatten：

(defun trec (rec &optional (base #'identiy))
(labels
((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec tree
#'(lambda ()
(self (car tree)))
#'(lambda ()
(if (cdr tree)
(self (cdr tree))))))))
#'self))

圖5.10： 為在樹(shù)上進(jìn)行遞歸操作而設(shè)計(jì)的函數(shù)

(trec #'(lambda (o l r) (nconc (funcall l) (funcall r)))

現(xiàn)在，我們同樣可以把 rfind-if 寫成這樣（下面的例子用了 oddp）：

(trec #'(lambda (o l r) (or (funcall l) (funcall r)))
#'(lambda (tree) (and (oddp tree) tree)))

5.7 何時(shí)構(gòu)造函數(shù)

很不幸，如果用構(gòu)造函數(shù)，而非 sharp-quoted 的 lambda 表達(dá)式來(lái)表示函數(shù)會(huì)在運(yùn)行時(shí)讓程序做一些不必要的工作。雖然sharp-quoted 的--表達(dá)式是一個(gè)常量，但是對(duì)構(gòu)造函數(shù)的調(diào)用將會(huì)在運(yùn)行時(shí)求值。如果你真的必須在運(yùn)行時(shí)執(zhí)行這個(gè)調(diào)用，可能使用構(gòu)造函數(shù)并非上策。不過(guò)，至少有的時(shí)候我們可以在事前就調(diào)用這個(gè)構(gòu)造函數(shù)。通過(guò)使用#. ，即 sharp-dot 讀取宏，我們可以讓函數(shù)在讀取期（read-time） 就被構(gòu)造出來(lái)。

假設(shè)compose 和它的參數(shù)在下面的表達(dá)式被讀取時(shí)已經(jīng)被定義了，那么我們可以這樣寫，舉例如下：

(find-if #.(compose #'oddp #'truncate) lst)

這樣做的話，reader 就會(huì)對(duì) compose 的調(diào)用進(jìn)行求值，求值得到的函數(shù)則被作為常量安插在我們的代碼之中。由于oddp 和truncate 兩者都是內(nèi)置函數(shù)，所以在讀取時(shí)對(duì)compose 進(jìn)行估值可以被認(rèn)為是安全可行的，當(dāng)然，前提是那個(gè)時(shí)候compose 自己已經(jīng)加載了。

一般而言，由宏來(lái)完成函數(shù)復(fù)合或者合并，既簡(jiǎn)單容易，又提高了程序的性能。這一點(diǎn)對(duì)函數(shù)擁有具有單獨(dú)名字空間的 Common Lisp 來(lái)說(shuō)尤其如此。在介紹了宏的相關(guān)知識(shí)后，我們會(huì)在第15章故地重游，再次回到這一章中曾走到過(guò)的大多數(shù)山山水水，所不同的是，到那時(shí)候你會(huì)騎上更純種的寶馬，配上更奢華的鞍具。