告别循环——map、filter 与 fold 的列表处理

处理列表不用写循环：map 做转换、filter 筛选、fold 压成一个值、apply 把列表摊开成参数。你描述“结果是什么”，而不是指挥“每一步怎么做”。

你写过 for 循环、维护过 acc = []、在循环里用 if 挑元素、最后返回累加器。这些写法在 C、Python、Java 里像呼吸一样自然，但你有没有想过：循环到底在做什么？为什么 Racket 的代码里几乎看不到 for，列表照样被处理得干干净净？

答案不在奇技淫巧，而在一组叫做“高阶函数”的小工具。这一篇讲 Racket 里取代循环的七个函数：map、filter、foldl、foldr、apply、ormap、andmap。

把函数当值传：这就是高阶函数

高阶函数，就是把函数当参数接收的函数。在 Racket 里，函数和数字、字符串一样是一等公民——可以传来传去。

(map add1 '(1 2 3))
;; '(2 3 4)

这里的 add1 不是被“调用”，而是被“传给” map，由 map 决定什么时候用、对谁用。一旦接受了“函数也是值”，循环里大半的样板代码就消失了。

map：对每个元素做同一件事

map 接收一个函数和一个列表，把函数作用到每个元素上，返回新列表。

(map add1 '(1 2 3))
;; '(2 3 4)

(map (λ (x) (* x x)) '(1 2 3 4))
;; '(1 4 9 16)

map 还能并行处理多个列表——把对应位置的元素一起喂给函数：

(map + '(1 2 3) '(10 20 30))
;; '(11 22 33)

这个特性在做矩阵类操作时非常顺手，后面会看到它的妙用。

filter：留下满足条件的

filter 接收一个谓词（返回布尔值的函数）和一个列表，只留下谓词返回 #t 的元素。

(filter even? '(1 2 3 4 5 6))
;; '(2 4 6)

(filter (λ (s) (> (string-length s) 3))
 '("hi" "hello" "abc" "rack"))
;; '("hello" "rack")

apply：把列表摊开成参数

apply 接收一个函数和一个列表，把列表的元素“摊开”成函数的参数，专门对付吃可变参数的函数。

(apply + '(1 2 3 4))
;; 10，等价于 (+ 1 2 3 4)

(apply append '((1 2) (3 4) (5 6)))
;; '(1 2 3 4 5 6)

apply 还允许在列表前面再塞固定参数，拼字符串、做格式化时常用：

(define args '(1 2 3))
(apply format "~a ~a ~a" args)
;; "1 2 3"

foldl 与 foldr：把列表压成一个值

map 和 filter 的产出还是列表。若要把一整个列表压成单个值——求和、求积、拼成一个结构——就要用 fold。

foldl 从左往右折叠：

(foldl + 0 '(1 2 3 4))
;; 10，展开是 (+ (+ (+ (+ 0 1) 2) 3) 4)

foldr 从右往左折叠，常用来构造列表之类的结构：

(foldr cons '() '(1 2 3))
;; '(1 2 3)

有个细节要盯紧：Racket 的 foldl 和 foldr，回调参数都是“元素在前、累加器在后”，和 Haskell 的 foldl 正好相反，记错会算出离谱的结果。

ormap 与 andmap：整张列表的真假

ormap 和 andmap 用一个谓词判断整张列表。

(ormap even? '(1 3 5 6))
;; #t

(andmap number? '(1 2 3))
;; #t

但别被名字骗了：ormap 返回的是第一个非 #f 的结果，andmap 返回的是最后一个结果——把它们当 or 和 and 的列表版就对了。 当你传 even?、number? 这种谓词时，结果恰好是 #t，看起来才像纯布尔值。

循环的代价：为什么 Racket 不这么写

回到开头的问题。把一串数字里的偶数挑出来翻倍，照搬 C/Python 的习惯，写出来是这样：

(define (double-evens lst)
 (define acc '())
 (for ([x lst])
 (when (even? x)
 (set! acc (append acc (list (* x 2))))))
 acc)

能跑，但一身毛病。要维护 acc 这个可变状态，要写 set! 去改它；(append acc ...) 每次都新建一个列表，append 本身是 O(n)，在循环里调用就成了 O(n²)。更要命的是，整段代码在描述“我怎么做”——声明累加器、遍历、判断、追加、返回。

函数式的写法只要一行：

(define (double-evens lst)
 (map (λ (x) (* x 2))
 (filter even? lst)))

没有变量、没有状态变更、不用操心遍历顺序。这段代码说的是“做什么”——筛出偶数再翻倍——而不是“怎么做”。 没有了 set!，越界、错位、状态被意外改写这一类 bug 也就失去了藏身之处。

组合：小积木拼大积木

高阶函数真正的威力在组合。每个函数只做一件小事，拼起来却能解复杂问题。

map 套 filter，先筛后转换：

(map add1 (filter even? '(1 2 3 4 5 6)))
;; '(3 5 7)

apply 套 map，玩出“按列取最大值”——矩阵处理里很顺手的技巧：

(apply map max '((1 9 3)
 (4 2 6)
 (7 5 0)))
;; '(7 9 6)

apply 把三个子列表摊开成 map 的参数，于是 (map max '(1 9 3) '(4 2 6) '(7 5 0)) 就是对每一列求最大值。

foldl 甚至能模拟 map——只是返回的列表是逆序的，因为每一步都把新元素 cons 到累加器前面：

(foldl (λ (x acc) (cons (* x x) acc))
 '()
 '(1 2 3 4))
;; '(16 9 4 1)

这不是为了取代 map，而是理解 fold 的好办法。fold 比 map 更底层——map 能做的，fold 都能做。

从”怎么做”到”是什么”

说到底，for 循环并没有在 Racket 里消失——它有 for、for/list、for/fold 一整套。但当你习惯了高阶函数，会发现自己越来越少需要它们。因为绝大多数循环的本质，不外乎三种：对每个元素做转换（map）、挑出满足条件的（filter）、把列表压成一个值（fold）。

找问题，再改对

下面三段代码都能跑，但都把 Racket 当 C 在写——能用，却没用上这一章的任何工具。先说出每段“别扭在哪”，再改对：

1. 有人想数一数列表里有几个偶数：

(define (count-evens lst)
  (define n 0)
  (for-each (λ (x) (when (even? x) (set! n (+ n 1))))
            lst)
  n)

2. 有人想求一组数的最大值：

(define (my-max lst)
  (define m (first lst))
  (for ([x (rest lst)])
    (when (> x m) (set! m x)))
  m)

3. 有人想求一组数的乘积：

(define (product lst)
  (define p 1)
  (for ([x lst])
    (set! p (* p x)))
  p)

改完想一想：三段原代码都养了一个 set! 累加器。你改后的版本里，这个累加器去哪了？被哪个函数接手了？

当你不再告诉计算机“每一步怎么做”，而是描述“结果是什么”时，循环就消失了，剩下的是一组可以随便拼装的小积木。