fold 是一切：map 与 filter 的原产地

三个函数，一个形状

照第 9 章的配方，写三个最普通的列表函数：

(define (sum lst)
  (cond [(null? lst) 0]
        [else (+ (car lst) (sum (cdr lst)))]))

(define (product lst)
  (cond [(null? lst) 1]
        [else (* (car lst) (product (cdr lst)))]))

(define (length* lst)
  (cond [(null? lst) 0]
        [else (+ 1 (length* (cdr lst)))]))

盯着这三个函数看五秒钟。

它们的骨架一模一样。不同的只有两个地方：

• 空表时返回什么（0 / 1 / 0）—— 叫它初始值
• 怎么把「头」和「尾巴的结果」合起来（+ / * / 加一）—— 叫它合并函数

那就把这两个地方挖成参数。

(define (foldr f init lst)
  (cond
    [(null? lst) init]                            ; ← 空表时返回初始值
    [else (f (car lst)                            ; ← 用 f 合并「头」
             (foldr f init (cdr lst)))]))         ;    和「尾巴折完的结果」

然后那三个函数就都不用写了：

(define (sum lst)     (foldr + 0 lst))
(define (product lst) (foldr * 1 lst))
(define (length* lst) (foldr (lambda (x acc) (+ 1 acc)) 0 lst))
;                                     ↑ 不看元素，只数个数

看着它折

「fold」这个词的意思是「折叠」，而这个比喻是精确的。下面这台机器把折叠的过程一步步展开了 —— 特别注意最后两个例子，它们会把「方向」这件事一次说清。

两个方向：foldr 和 foldl

上面那个 foldr 是非尾递归的 —— 它得先一路走到底，再从里往外算（你在 demo 里看到括号一层层堆起来了）。

另一个方向：带一个累加器，从左往右边走边算（这就是第 8 章的累加器模式）：

(define (foldl f init lst)
  (cond
    [(null? lst) init]
    [else (foldl f (f (car lst) init) (cdr lst))]))
;            ↑ 尾递归！先把 f 算掉，结果作为新的 init 传下去

两者的区别，一张表说完：

那个「把 + 换成 cons」的调试技巧

这是我能给你的、关于 fold 最有用的一条建议。

方向记不住的时候，把合并函数换成 cons，初始值换成 '()，跑一遍。因为 cons + '() 恰好就是「重新造一个列表」—— 所以结果的形状，会把 fold 的方向直接画出来：

> (foldr cons '() '(1 2 3))
'(1 2 3)                      ; ← 原样复制。foldr 保形

> (foldl cons '() '(1 2 3))
'(3 2 1)                      ; ← 反转了。foldl 反向

为什么？把它展开就看得一清二楚：

(foldr cons '() '(1 2 3))
= (cons 1 (cons 2 (cons 3 '())))
;  ↑ 这正好就是 '(1 2 3) 的定义（第 9 章）—— 所以它是恒等变换

(foldl cons '() '(1 2 3))
= (cons 3 (cons 2 (cons 1 '())))
;  ↑ 每一步都把新元素 cons 到累加器的前面 —— 所以顺序反了

把标准库造一遍

现在，用 fold 把你天天用的那些函数全造出来（下面每一行我都在 Racket 里跑过）：

(define (my-map f lst)
  (foldr (lambda (x acc) (cons (f x) acc)) '() lst))
;                          ↑ 把 f 作用于头，再 cons 上去

(define (my-filter p lst)
  (foldr (lambda (x acc) (if (p x) (cons x acc) acc)) '() lst))
;                          ↑ 通过就 cons，不通过就跳过

(define (my-length lst)
  (foldr (lambda (x acc) (+ 1 acc)) 0 lst))

(define (my-reverse lst)
  (foldl cons '() lst))              ; ← 一行。因为 foldl 天然反转

(define (my-append a b)
  (foldr cons b a))                  ; ← 把 b 当初始值，把 a 拆开重装上去

(define (my-max lst)
  (foldr max (car lst) lst))

(define (my-count p lst)
  (foldl (lambda (x acc) (if (p x) (add1 acc) acc)) 0 lst))

七个函数，全都是一行。

my-append 那个尤其漂亮 —— 停下来想三十秒：把 b 当作初始值，然后用 cons 把 a 的元素一个个装回去，装完自然就接在 b 前面了。这不是技巧，这是 foldr 的定义直接推出来的。

参数顺序：一个必须小心的陷阱

现在回答第 1 章题 9。但先给你一个警告 —— 不同语言的参数顺序不一样，这是真实的 bug 来源：

注意 Racket 的怪异之处：它的 foldl 也是 (elem acc)，和 Kotlin/Haskell 的 (acc, elem) 反着来。这是 Racket 为了和 foldr 保持一致做的选择（两者签名统一），代价是和其他语言不一致。写的时候查一下文档，别凭记忆。

而 Kotlin 为什么 fold 和 foldRight 的顺序反着？因为它反映了展开式里的位置：

// fold: acc 在左边被一路推着走
listOf(1,2,3).fold("") { acc, x -> acc + x }
// = ((("" + 1) + 2) + 3) = "123"
//     ↑ acc 一直在左

// foldRight: elem 在左，acc 是「右边折完的结果」
listOf(1,2,3).foldRight("") { x, acc -> x + acc }
// = (1 + (2 + (3 + ""))) = "123"
//    ↑ elem 在左，acc 在右

参数顺序不是随手拍的，它是展开式的倒影。一旦你能把展开式写出来，顺序就不用记了。

什么时候该用哪个

回流

// 你常写的
var total = 0L
for (item in items) { total += item.price * item.qty }

// 它是一个 fold
val total = items.fold(0L) { acc, it -> acc + it.price * it.qty }
// 或者更直白：
val total = items.sumOf { it.price * it.qty }

// ✗ 炫技，难读
val grouped = items.fold(mutableMapOf<String, MutableList<Item>>()) { m, i ->
    m.getOrPut(i.category) { mutableListOf() }.add(i); m
}

// ✓ 用那个专门为此而生的函数
val grouped = items.groupBy { it.category }

list.fold(0) { a, b -> a + b }   // 有初始值 → 空列表返回 0，安全
list.reduce { a, b -> a + b }    // 没有初始值 → 空列表直接抛异常！
// Kotlin 提供了 reduceOrNull()，JS 的 reduce 没有初始值时空数组也会 TypeError

下一章

我们已经能优雅地处理列表了。但真实的数据不只是列表 —— 它有形状，有多种情况。

下一章：struct 和 match。你会看到 Kotlin 的 sealed class + when、TypeScript 的判别联合、Rust 的 enum + match，祖籍全在这里。