在 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 捕获了列表递归的模式，递归问题最好通过一次一步地解决。