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

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

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

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

5.1 Common Lisp 的演化

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

(remove-if-not #'pred lst)

就和下面語句等價:

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

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

(remove-if-not #'pred lst)

換成與之等價的:

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

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

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

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

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

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

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

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

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

在第12頁，我們見到了另一個用來返回函數(shù)的函數(shù)，它就依賴于詞法作用域：

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

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

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

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

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

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

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

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

5.2 正交性

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

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

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

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

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

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

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

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

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

圖5.1： 返回破壞性的等價物

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

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

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

就可以把

(delete-if #'oddp lst)

取而代之，換成

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

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

((! remove-if) oddp lst)

除了更強的正交性，!操作符還帶來了一系列其它的好處。它讓程序更清晰明了，因為我們可以一下子就看出來 （! #'foo）是與foo 對應(yīng)的破壞性版本。另外，它還讓破壞性操作在源代碼里總是一目了然。這樣的好處在于當(dāng)我們在找bug 時，會更小心這些地方。

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

5.3 記住過去

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

(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： 記憶性的實用工具

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

的版本 即一個閉包，該閉包含有存儲以往調(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)然，這也帶來了每次調(diào)用開始時進行查找導(dǎo)致的額外開銷，但是既然我們只會把那些計算開銷足夠大的函數(shù)進行記憶化的處理， 那么就可以認為付出這個代價是值得的。

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

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

函數(shù) 的補被記為～ 。第5.1 節(jié)展示了使用閉包可以將～ 定義為一個Lisp 函數(shù)的可能性。另一個常見的函數(shù)操作是復(fù)合，它被記作?。如果 和 是兩個函數(shù)，那么 ? 也是函數(shù)，并且 ? 。同樣的，通過使用閉包的方式，也可以把? 定義為一個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 定義了一個名為 compose 的函數(shù)，它接受任意數(shù)量的函數(shù)，并返回它們的復(fù)合。比如說

(compose #'list #'1+)

會返回一個函數(shù)，該函數(shù)等價于

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

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

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

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

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

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

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

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

(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ù)被用來生成常見的函數(shù)類型。其中第二個構(gòu)造函數(shù)是為下面的情形預(yù)備的：

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

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

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

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

5.5 在cdr 上遞歸

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?在一些實現(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 在子樹上遞歸

在Lisp 程序里還有另外一種常用的遞歸形式： 即在子樹上進行遞歸。當(dāng)你開始使用嵌套列表，而且希望遞歸地訪問列表的car 和cdr 之時， 這種遞歸形式就出現(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： 用列表表示的樹

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

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

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

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

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

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

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

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

我們可以自己定義一個copy-tree ，見下面的代碼：

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

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

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

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

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

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

在上一章中，我們定義了幾個用來操作樹的實用工具。比如說，flatten （第32 頁） 接受一顆樹，并返回一個含有樹上所有原子的列表。換句話說，如果你傳給flatten 一個嵌套列表，你所得到的返回列表和前面的列表形式相同，不過除了最外面那對之外，其它的括弧都不見了：

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

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

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

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

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

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

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

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

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

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

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

(ttrav #'cons #'identity)

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

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

在ttrav 的幫助下，我們可以重新定義除rfind-if 之外前面提到的所有函數(shù)。（這些函數(shù)在圖5.9 中可以找到。） 要定義rfind-if ，需要更通用的樹結(jié)構(gòu)遞歸操作函數(shù)的生成器， 這種函數(shù)生成器能讓我們控制遞歸調(diào)用發(fā)生的時機，以及是否繼續(xù)遞歸。我們把一個函數(shù)作為傳給ttrav 的第一個參數(shù)，這個函數(shù)的參數(shù)將是遞歸調(diào)用的返回值。對于通常的情形， 我們會改用另一個函數(shù)，讓它接受兩個閉包，閉包分別自行表示調(diào)用操作。這樣，就可以編寫那些能自主控制遞歸過程的遞歸函數(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è)計的函數(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 實現(xiàn)的函數(shù)通常會遍歷整顆樹。這樣做對于像 count-leaves 或者flatten 這樣的函數(shù)是沒有問題的， 它們不管如何都會遍歷全樹。然而，我們需要rfind-if 一發(fā)現(xiàn)它所要找的元素就停止遍歷。這個函數(shù)必須交給更通用的trec 來生成， 見圖5.10。trec 的第二個參數(shù)應(yīng)當(dāng)是一個具有三個參數(shù)的函數(shù)，三個參數(shù)分別是： 當(dāng)前的對象，以及兩個遞歸調(diào)用。后兩個參數(shù)將是用來表示對左子樹和右子樹進行遞歸的兩個閉包。使用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è)計的函數(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 何時構(gòu)造函數(shù)

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

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

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

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

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