原文枢泰。
https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours/Towards_a_Standard_Library
現(xiàn)在我們的Scheme基本是完成了爹袁，但目前它還有點難以使用。至少砸抛，我們希望能夠有一個標(biāo)準(zhǔn)的列表處理的函數(shù)庫供我們使用來進(jìn)行一些基本的計算操作。
與其使用一個傳統(tǒng)的遞歸方式來實現(xiàn)Scheme中的列表函數(shù)树枫，我們會首先定義兩個基本的遞歸操作符（fold和unfold）然后在它們的基礎(chǔ)上定義出我們的整個函數(shù)庫直焙。這是Haskell中Prelude庫的風(fēng)格：更加簡潔的定義，更少出錯的可能砂轻，使用fold在控制循環(huán)是很好的習(xí)慣奔誓。
我們從定義一些簡單有用的輔助函數(shù)開始，我們將no和null函數(shù)通過if語句定義出來：
(define (not x) (if x #f #t))
(define (null? obj) (if (eqv? obj '()) #t #f))
我們可以通過可變參數(shù)的功能來定義list函數(shù)，它會將輸入?yún)?shù)作為一個列表返回：
(define (list . objs) objs)
我們還需要一個id函數(shù)厨喂，僅僅將輸入?yún)?shù)完全不變的返回給我們和措。這雖然看起來好像完全沒用-如果你已經(jīng)持有這個值了，為什么還需要一個函數(shù)來將它再次返回給你呢蜕煌？然而派阱，我們需要的算法都會讀取一個對給定值進(jìn)行轉(zhuǎn)換的函數(shù)作為參數(shù)。而通過定義id函數(shù)斜纪，我們能在調(diào)用那些高階函數(shù)的時候達(dá)到不對值進(jìn)行任何改變的效果贫母。
(define (id obj) obj)
類似的我們也同樣需要flip函數(shù)來在傳入?yún)?shù)順序不對的時候允許我們進(jìn)行調(diào)整：
(define (flip func) (lambda (arg1 arg2) (func arg2 arg1)))
最后，我們添加curry和compose函數(shù)盒刚，它們會我們在Haskell里已經(jīng)熟悉的概念完全一樣（分別對應(yīng)部分應(yīng)用以及dot操作符的概念）腺劣。
(define (curry func arg1) (lambda (arg) (apply func (cons arg1 (list arg)))))
(define (compose f g) (lambda (arg) (f (apply g arg))))
再來一些Scheme標(biāo)準(zhǔn)庫中應(yīng)該包含的簡單函數(shù)：
(define zero? (curry = 0))
(define positive? (curry < 0))
(define negative? (curry > 0))
(define (odd? num) (= (mod num 2) 1))
(define (even? num) (= (mod num 2) 0))
這些定義基本上和想象中的一樣。注意我們是怎么使用curry來定義zero?因块，positive?和negative?的誓酒。我們將curry返回的函數(shù)綁定給zero?，從而得到一個如果參數(shù)等于0就返回True的一元函數(shù)贮聂。
接下來靠柑，我們要定義一個能夠捕獲列表的基本遞歸形式的fold函數(shù)。最好的想象這個fold函數(shù)的方法就是以中綴構(gòu)造的方式來思考整個列表：Haskell中是[1, 2, 3, 4] = 1:2:3:4:[]而Scheme中則是(1 . (2 . (3 . (4 . NIL))))吓懈。我們的fold函數(shù)會把每一個構(gòu)造器都替換成一個二元操作符歼冰，然后把Nil替代成一個累計值。舉例來說(fold + 0 '(1 2 3 4)) = (1 + (2 + (3 + (4 + 0))))耻警。
有了以上的定義隔嫡，我們就可以寫出我們的fold函數(shù)了。首先通過右結(jié)合的方式來模擬上面的例子：
(define (foldr func end lst)
(if (null? lst)
end
(func (car lst) (foldr func end (cdr lst)))))
這個函數(shù)基本上就完全模擬我們之前對它的定義甘穿。如果列表是空的腮恩，就用一個終止符取代它。如果不是温兼，我們對列表的car部分以及剩余部分和一個end值一起被fold之后的結(jié)果應(yīng)用這個函數(shù)秸滴。因為列表右側(cè)的部分會首先被fold，因此這里你首先得到了一個右結(jié)合的fold函數(shù)募判。
同樣我們也想要一個左結(jié)合的版本荡含。對于大部分像+或是*這樣的操作符，這兩者是完全一樣的届垫。然而释液，我們至少有一個重要的二元操作符是沒法這樣結(jié)合的：cons。因此對于列表操作函數(shù)装处，我們需要在左右兩種方式結(jié)合的fold中有所選擇.
(define (foldl func accum lst)
(if (null? lst)
accum
(foldl func (func accum (car lst)) (cdr lst))))
開頭的部分和我們在右結(jié)合的時候一樣误债，通過判斷來決定是否直接將累計值返回。不過接下來有點不同，我們首先對累計值和列表的頭元素應(yīng)用我們的函數(shù)寝蹈，而不是像之前那樣分別對頭元素和剩下元素fold的結(jié)果進(jìn)行應(yīng)用糟袁。這意味著我們這次會首先處理列表的頭部部分，提供給了我們左結(jié)合的功能躺盛。當(dāng)?shù)竭_(dá)列表的結(jié)尾'()的時候项戴，我們就將之前一路處理得到累計值作為結(jié)果返回。
注意傳入兩個fold的函數(shù)func讀入?yún)?shù)的順序是相反的槽惫。foldr中周叮，累計值代表的是當(dāng)前位置右邊遞歸計算直到列表結(jié)束的結(jié)果。而在foldl中界斜，它代表了列表左邊部分已經(jīng)完成了的計算仿耽。因此為了保證我們隊操作符交換性能夠有一個直觀的認(rèn)識，在foldl中累計值會作為函數(shù)的前一個參數(shù)各薇，而在foldr中會作為后一個项贺。
定義好了基本的fold函數(shù)，我們再根據(jù)它們在Scheme中的典型用途為它們定義一些別名：
(define fold foldl)
(define reduce foldr)
這里沒有定義新函數(shù)峭判，只是把定義過的函數(shù)綁定到了新的變量上开缎。大部分Scheme會把fold稱作reduce或是傳統(tǒng)的fold，并且不對foldl和foldr進(jìn)行區(qū)分林螃。我們這里把它和foldl綁定奕删，這里foldl是一個尾遞歸的函數(shù)因此它會比foldr的運行效率更高（它不需要在開始計算之前將整個列表遞歸展開）。但是不是所有操作都支持結(jié)合律的疗认。我們接下來會看到幾個需要使用foldr才能正確運行的例子完残。
接下來，我們來定義一個與fold相反的函數(shù)横漏。讀入一個一元函數(shù)谨设，一個初始值和一個一元斷言，它會不斷將函數(shù)應(yīng)用于之前的計算結(jié)果直到斷言為真缎浇，然后將所有得到的計算值組成一個列表扎拣。
(define (unfold func init pred)
(if (pred init)
(cons init '())
(cons init (unfold func (func init) pred))))
我們的函數(shù)一如既往的和上面給出的定義一致。如果斷言得到True华畏，那就將一個'()和最后的值cons起來鹏秋，將列表終止。否則的話亡笑，將當(dāng)前值和接下來的unfold結(jié)果值組合起來。
在學(xué)院派的函數(shù)式編程著作當(dāng)中横朋，folds一般會被稱作catamorphisms仑乌，unfold則是anamorphisms，而它們兩者的組合被叫做hylomorphisms。有趣的地方就是事實上所有for-each循環(huán)都可以以catamorphisms的形式表達(dá)晰甚。如果我們想要將一個循環(huán)轉(zhuǎn)換成一個foldl形式衙传，我們只需要把所有循環(huán)中會操作的變量組成一個數(shù)據(jù)結(jié)構(gòu)就可以了（例如Record類型，或者你也可以自己專門定義一個代數(shù)類型）厕九。我們把初始狀態(tài)作為累計值蓖捶；循環(huán)體作為傳入fold的func參數(shù)，循環(huán)體中的變量是一個參數(shù)而被遍歷的變量是第二個扁远；最后俊鱼，列表參數(shù)當(dāng)然就是我們需要遍歷的列表。fold函數(shù)最后計算的結(jié)果就是所有變量被更新后的狀態(tài)畅买。
相似的并闲，所有for循環(huán)（沒有事先存在的遍歷對象）也都可以用hylomorphism來表示。初始值谷羞，終止值以及for循環(huán)中的每一步判斷條件定義了一個產(chǎn)生數(shù)據(jù)列表的anamorphism來供我們遍歷帝火。接下來，你只需要把它當(dāng)做一個for-each循環(huán)然后使用catamorphism 來將它分解并按照需要做你自己的計算并對狀態(tài)進(jìn)行更新就可以了湃缎。
先來看點例子犀填。我們會從典型的sum，product嗓违，and和or函數(shù)開始：
(define (sum . lst) (fold + 0 lst))
(define (product . lst) (fold * 1 lst))
(define (and . lst) (fold && #t lst))
(define (or . lst) (fold || #f lst))
這里是它們的定義：
- (sum 1 2 3 4) = 1 + 2 + 3 + 4 + 0 = (fold + 0 '(1 . (2 . (3 . (4 . NIL)))))
- (product 1 2 3 4) = 1 * 2 * 3 * 4 * 1 = (fold * 1 '(1 . (2 . (3 . (4 . NIL)))))
- (and #t #t #f) = #t && #t && #f && #t = (fold && #t '(#t . (#t . (#f . NIL))))
- (or #t #t #f) = #t || #t || #f || #f = (fold || #f '(#t . (#t . (#f . NIL))))
因為所有操作符都滿足結(jié)合律宏浩，因此它不在乎我們是使用foldr還是foldl。我們將cons替換為操作符靠瞎，將Nil替換為操作符的幺元比庄。
接下來，試試看一些更加復(fù)雜的操作符乏盐。max和min會分別將它們傳入?yún)?shù)中的最大和最小值找出來：
(define (max first . rest) (fold (lambda (old new) (if (> old new) old new)) first rest))
(define (min first . rest) (fold (lambda (old new) (if (< old new) old new)) first rest))
這里似乎沒辦法一眼看清楚到底我們對整個列表fold了什么操作佳窑，因為似乎并沒有任何比較合適的內(nèi)置函數(shù)。這里我們將fold想象成foreach循環(huán)的一種形式父能。累計值可以代表我們在循環(huán)的上一次迭代中的任意狀態(tài)神凑，因此我們這里把它當(dāng)做目前為止發(fā)現(xiàn)的最大值。它的初始值就應(yīng)該是整個列表的最左邊的元素（因為我們使用的是foldl）何吝。注意我們的操作的結(jié)果是會變成下一步的累計值的溉委，所以我們就這樣定義傳入的函數(shù)。如果前一個值更大那就保留它爱榕，而如果后一個值更大或是它們是相等的瓣喊，那就返回新的值。min函數(shù)則是與之相反的過程黔酥。
length函數(shù)怎么樣藻三？我們知道我們可以通過累加的方式來求出一個列表的長度洪橘，那么我們怎么用fold的形式來表達(dá)它呢：
(define (length lst) (fold (lambda (x y) (+ x 1)) 0 lst))
同樣我們把這個定義想象成一個循環(huán)。累計從0開始棵帽，然后沒迭代一次就增加1熄求。因此我們得到了初始值0以及需要傳入fold的函數(shù)(lambda (x y) (+ x 1))。另一種思考的方式就是“列表的的長度就是1加上它當(dāng)前位置以左部分的子串的長度”逗概。
讓我們來看點有趣的：reverse函數(shù)：
(define (reverse lst) (fold (flip cons) '() lst))
這個函數(shù)這里就非常明顯了：如果你想要翻轉(zhuǎn)兩個cons單元弟晚，你只需要使用flip函數(shù)，這樣它們就會將參數(shù)調(diào)換到相反的位置逾苫。然而卿城，實際這里有一個很巧妙的地方。普通列表都是右結(jié)合的：(1 2 3 4) = (1 . (2 . (3 . (4 . NIL))))隶垮。如果你想要將它翻轉(zhuǎn)藻雪，你需要讓你的fold能夠支持左結(jié)合(reverse '(1 2 3 4)) = (4 . (3 . (2 . (1 . NIL))))。用foldr代替foldl試試看你會得到什么狸吞。
接下來是一大堆member和assoc函數(shù)勉耀，它們都可以用fold的形式來定義。雖然它們需要的lambda表達(dá)式都有點復(fù)雜蹋偏，讓我們來提取它們中的規(guī)律：
(define (mem-helper pred op) (lambda (acc next) (if (and (not acc) (pred (op next))) next acc)))
(define (memq obj lst) (fold (mem-helper (curry eq? obj) id) #f lst))
(define (memv obj lst) (fold (mem-helper (curry eqv? obj) id) #f lst))
(define (member obj lst) (fold (mem-helper (curry equal? obj) id) #f lst))
(define (assq obj alist) (fold (mem-helper (curry eq? obj) car) #f alist))
(define (assv obj alist) (fold (mem-helper (curry eqv? obj) car) #f alist))
(define (assoc obj alist) (fold (mem-helper (curry equal? obj) car) #f alist))
這里我們讓輔助函數(shù)能夠讀取一個斷言和一個會對結(jié)果進(jìn)行操作的函數(shù)作為參數(shù)便斥。它的累計值代表著當(dāng)前第一個被找到的匹配值：它的初始值是#f并且會變成列表中第一個滿足斷言的值。我們通過一個非#f的判斷來避免找到后續(xù)的值從而讓它在累計值已經(jīng)被設(shè)置之后直接將當(dāng)前值返回威始。我們還提供了一個在斷言檢測時每次都會應(yīng)用到next值的操作：這讓我們可以自定義我們的mem-helper函數(shù)來選擇是檢查值本身（member函數(shù)）or是只是檢查鍵（assoc函數(shù)）枢纠。
剩下的部分就只是各種eq?，eqv?黎棠，equal晋渺？，id和car的組合將整個列表從#f開始fold起來的過程了脓斩。
接下來我們來定義map和filter函數(shù)木西。map會將函數(shù)應(yīng)用到列表里的每一個元素，然后返回一個由被轉(zhuǎn)換后的元素組成的列表：
(define (map func lst) (foldr (lambda (x y) (cons (func x) y)) '() lst))
需要記住foldr的函數(shù)首先讀取的參數(shù)是當(dāng)前的迭代值随静，這是和fold不同的八千。Map函數(shù)中的lambda表達(dá)式會首先將函數(shù)應(yīng)用于當(dāng)前值，然后再講它的結(jié)果和剩下部分的map之后的列表組合起來燎猛。這本質(zhì)上來說就是將所有的中綴cons構(gòu)造器都替代成一個恋捆，然后再將函數(shù)對cons左邊的參數(shù)進(jìn)行應(yīng)用。
filter函數(shù)會將列表里滿足條件的元素留下來重绷，然后丟棄掉其它的：
(define (filter pred lst) (foldr (lambda (x y) (if (pred x) (cons x y) y)) '() lst))
它會將每個值代入斷言里計算然后如果結(jié)果為True沸停，用cons代替cons，即什么也不做论寨。如果是False星立，將cons丟棄掉爽茴，僅僅將列表剩下的部分返回葬凳。這樣我們就刪除掉了列表中所有不滿足斷言的元素绰垂，然后用cons將剩下滿足的元素組成一個新的列表。
我們可以在Lisp解釋器啟動以后通過(load "stdlib.scm")來加載我們的標(biāo)準(zhǔn)庫：
$ ./lisp
Lisp>>> (load "stdlib.scm")
(lambda ("pred" . lst) ...)
Lisp>>> (map (curry + 2) '(1 2 3 4))
(3 4 5 6)
Lisp>>> (filter even? '(1 2 3 4))
(2 4)
Lisp>>> quit
標(biāo)準(zhǔn)庫里還有很多其他有用的函數(shù)火焰，例如list-tail劲装，list-ref，append以及其他字符串操作函數(shù)昌简。嘗試著通過folds來實現(xiàn)它們占业。記住，基于fold的編程成功的關(guān)鍵就是以迭代為單位進(jìn)行思考纯赎。我們通過fold來捕捉列表中的遞歸的模式谦疾，然后一次一步的解決這個遞歸。
