在 48 小時內編寫自己的 Scheme/標準庫
我們的 Scheme 現在幾乎完成了，但它仍然很難使用。至少，我們想要一個標準列表操作函式庫，我們可以用它來執行一些常見的計算。
與其使用典型的 Scheme 實現，將每個列表函式定義為列表遞迴，我們將實現兩個原始遞迴運算子（fold 和 unfold），然後基於它們定義整個庫。這種風格被 Haskell Prelude 使用：它為提供更簡潔的定義、更少的錯誤空間和使用 fold 來捕獲迭代的良好實踐。
我們將從定義一些明顯的輔助函式開始。not 和 null 的定義與您期望的一樣，使用 if 語句
(define (not x) (if x #f #t))
(define (null? obj) (if (eqv? obj '()) #t #f))
我們可以使用可變引數功能來定義 list，它只是返回其引數的列表
(define (list . objs) objs)
我們還需要一個 id 函式，它只是返回其引數不變。這似乎完全沒有用 - 如果你已經有一個值，為什麼你需要一個函式來返回它？但是，我們的一些演算法需要一個函式來告訴我們如何處理給定值。透過定義 id，我們允許這些高階函式工作，即使我們不想對值做 任何 操作。
(define (id obj) obj)
同樣，擁有一個 flip 函式會很不錯，以防我們想傳遞一個以錯誤順序獲取其引數的函式
(define (flip func) (lambda (arg1 arg2) (func arg2 arg1)))
最後，我們新增 curry 和 compose，它們的工作方式與它們的 Haskell 等效項（部分應用和點運算子）相同。
(define (curry func arg1) (lambda (arg) (apply func (cons arg1 (list arg)))))
(define (compose f g) (lambda (arg) (f (apply g arg))))
我們不妨定義一些出現在 Scheme 標準中的簡單庫函式
(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?。我們將變數 zero? 繫結到 curry 返回的函式，這為我們提供了當其引數等於零時返回 true 的一元函式。
接下來，我們想定義一個 fold 函式，該函式捕獲了列表遞迴的基本模式。思考 fold 的最佳方式是將列表想象成其中綴建構函式：[1, 2, 3, 4] = 1:2:3:4:[] 在 Haskell 中或 (1 . (2 . (3 . (4 . NIL)))) 在 Scheme 中。一個 fold 函式用二元運算替換每個建構函式，並將 NIL 替換為累加器。因此，例如，(fold + 0 '(1 2 3 4)) = (1 + (2 + (3 + (4 + 0))))。
有了這個定義，我們就可以編寫我們的 fold 函數了。從一個右結合版本開始，以模仿上面的例子
(define (foldr func end lst)
(if (null? lst)
end
(func (car lst) (foldr func end (cdr lst)))))
此函式的結構幾乎與我們的定義完全一致。如果列表為空，則用結束值替換它。如果不是，則將函式應用於列表的 car 以及將此函式和結束值摺疊到列表其餘部分的結果。由於右運算元首先摺疊，因此您最終得到一個右結合 fold。
我們還需要一個左結合版本。對於大多數結合運算子，如 + 和 *, 它們兩者完全等效。但是，至少有一個重要的二元運算子 不 是結合的：cons。因此，對於我們所有的列表操作函式，我們需要在左結合 fold 和右結合 fold 之間進行有意選擇。
(define (foldl func accum lst)
(if (null? lst)
accum
(foldl func (func accum (car lst)) (cdr lst))))
這與右結合版本以相同的方式開始，對 null 進行測試，它返回累加器。但是，這次我們將函式應用於累加器和列表的第一個元素，而不是將其應用於第一個元素和摺疊列表的結果。這意味著我們首先處理開頭，從而為我們提供左結合性。到達列表末尾 '() 後，我們將返回我們一直在逐步構建的結果。
請注意，func 獲取其引數的順序與 foldr 相反。在 foldr 中，累加器代表要附加到列表末尾的 最右 值，在您完成對它的遞迴後。在 foldl 中，它代表列表 最左側 部分的完成計算。為了保持我們對運算子可交換性的直覺，因此它應該是在 foldl 中的運算的左引數，但在 foldr 中是右引數。
有了基本的 folds 後，我們可以定義幾個便利名稱以匹配典型的 Scheme 使用情況
(define fold foldl)
(define reduce foldr)
這些只是繫結到現有函式的新變數：它們不定義新函式。大多數 Schemes 將 fold 稱為“reduce”或簡單的“fold”，並沒有區分 foldl 和 foldr。我們將其定義為 foldl，它恰好是尾遞迴的，因此比 foldr 執行效率更高（它不必遞迴到列表的末尾才能開始構建計算）。但是，並非所有運算子都是結合的；我們將在後面看到一些情況，在這種情況下，我們 必須 使用 foldr 才能獲得正確的結果。
接下來，我們想定義一個與 fold 相反的函式。給定一個一元函式、一個初始值和一個一元謂詞，它會繼續將函式應用於最後一個值，直到謂詞為真，並在過程中構建一個列表。
(define (unfold func init pred)
(if (pred init)
(cons init '())
(cons init (unfold func (func init) pred))))
和往常一樣，我們的函式結構基本上與定義相匹配。如果謂詞為真，那麼我們將 '() 連線到最後一個值，終止列表。否則，將展開下一個值 (func init) 的結果連線到當前值。
在學術函數語言程式設計文獻中，folds 通常被稱為 catamorphisms，unfolds 通常被稱為 anamorphisms，而兩者的組合通常被稱為 hylomorphisms。它們很有趣，因為 每個 for-each 迴圈都可以表示為一個 catamorphism。要從迴圈轉換為 foldl，將迴圈中所有可變變數打包成一個數據結構（記錄適合此目的，但您也可以使用代數資料型別或列表）。初始狀態成為累加器；迴圈體成為一個函式，該函式以迴圈變數作為其第一個引數，以迭代變數作為其第二個引數；列表則變成了列表本身。fold 函式的結果是所有可變變數的新狀態。
類似地，每個 for 迴圈（沒有提前退出）都可以表示為一個 hylomorphism。for 迴圈的初始化、終止和步進條件定義了一個 anamorphism，它構建了一個迭代變數可以取的值列表。然後，您可以將其視為一個 for-each 迴圈，並使用一個 catamorphism 將其分解成您希望修改的任何狀態。
讓我們來舉幾個例子。我們將從典型的 sum、product、and & or 函式開始
(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))))
由於所有這些運算子都是結合的，因此我們使用 foldr 還是 foldl 都沒關係。我們將 cons 建構函式替換為運算子，並將 nil 建構函式替換為該運算子的標識元素。
接下來，讓我們嘗試一些更復雜的運算子。max 和 min 分別找到其引數中的最大值和最小值
(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 的操作，因為沒有一個內建函式完全符合要求。相反，回想一下 fold 作為 foreach 迴圈的表示。累加器表示我們在迴圈的先前迭代中維護的任何狀態，因此我們希望它成為我們迄今為止找到的最大值。這為我們提供了初始化值：我們希望從列表中的最左側變數開始（因為我們正在執行 foldl）。現在回想一下，操作的結果在每個步驟中都會成為新的累加器，我們得到了我們的函式。如果前一個值更大，則保留它。如果新值更大，或者它們相等，則返回新值。反轉 min 的操作。
length 怎麼樣？我們知道可以透過對列表進行計數來找到它的長度，但我們如何將其轉換為 fold？
(define (length lst) (fold (lambda (x y) (+ x 1)) 0 lst))
同樣，以迴圈的定義來思考。累加器從 0 開始，並在每次迭代中加 1。這為我們提供了初始化值 0 和函式 (lambda (x y) (+ x 1))。另一種看待它的方式是“列表的長度為 1 加上它左側子列表的長度”。
讓我們嘗試更棘手一點的東西：reverse。
(define (reverse lst) (fold (flip cons) '() lst))
這裡的函式相當明顯：如果您想反轉兩個 cons 單元格，您只需 flip cons，以便它以相反的順序獲取其引數。但是，這裡有一些微妙之處。普通列表是 右 結合的：(1 2 3 4) = (1 . (2 . (3 . (4 . NIL))))。如果您想反轉它，則需要您的 fold 是 左 結合的：(reverse '(1 2 3 4)) = (4 . (3 . (2 . (1 . NIL))))。嘗試使用 foldr 而不是 foldl，看看您得到了什麼。
有一系列 member 和 assoc 函式，所有這些函式都可以用 folds 來表示。不過，特定的 lambda 表示式相當複雜，所以讓我們將其分解
(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))
輔助函式透過要使用的謂詞和要應用於找到的結果的操作來引數化。它的累加器表示迄今為止找到的第一個值：它從 #f 開始，並採用滿足其謂詞的第一個值。我們透過測試非 #f 值並在它已經設定時返回現有累加器來避免找到後續值。我們還提供了一個操作，它將在每次謂詞測試時應用於下一個值：這使我們可以定製 mem-helper 來檢查值本身（對於 member）或僅檢查值的鍵（對於 assoc）。
其餘函式只是 eq?、eqv?、equal? 和 id、car 的各種組合，它們被摺疊到列表中，初始值為 #f。
接下來，讓我們定義 map 和 filter 函式。map 將函式應用於列表的每個元素，返回一個包含轉換值的新列表
(define (map func lst) (foldr (lambda (x y) (cons (func x) y)) '() lst))
請記住，foldr 函式的引數順序與 fold 相反，當前值位於左側。Map 的 lambda 函式將函式應用於當前值，然後將其與對映列表的其餘部分（由右側引數表示）連線起來。它本質上是用一個既連線又將函式應用於其左側引數的函式替換了每個中綴連線建構函式。
filter 保留列表中滿足謂詞的元素，丟棄所有其他元素。
(define (filter pred lst) (foldr (lambda (x y) (if (pred x) (cons x y) y)) '() lst))
這是透過將當前值與謂詞進行比較來實現的。如果為真，則用 cons 替換連線，即不做任何操作。如果為假，則丟棄連線並只返回列表的其餘部分。這將消除所有不滿足謂詞的元素，連線一個新的列表，該列表僅包含滿足謂詞的元素。
我們可以透過啟動 Lisp 直譯器並輸入 (load "stdlib.scm") 來使用標準庫。
$ ./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
標準庫中還有許多其他有用的函式，包括 list-tail、list-ref、append 和各種字串操作函式。嘗試將它們實現為摺疊。請記住，成功摺疊程式設計的關鍵是隻考慮每次迭代發生的事情。Fold 捕獲了列表遞迴的模式，遞迴問題最好透過一次一步地解決。