递归与 fold:一切循环的祖先

数据是递归的,函数就是递归的

上一章末尾露过列表的真身:data List a = Nil | Cons a (List a)——空,或者头加尾。处理一个递归定义的数据,最自然的函数形状就是照着它的两个构造子各写一个分支:

sum' :: [Int] -> Int
sum' []       = 0                -- Nil 分支:空列表的和
sum' (x:xs)   = x + sum' xs      -- Cons 分支:头 + 尾的和

length' :: [a] -> Int
length' []     = 0
length' (_:xs) = 1 + length' xs

product' :: [Int] -> Int
product' []     = 1
product' (x:xs) = x * product' xs

写到第三个,任何工程师的重复代码警报都该响了:三个函数唯二的区别是「空列表给什么」和「头和尾的结果怎么合并」。把这两个可变点抽成参数,重复就死了:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

sum'     = foldr (+) 0
product' = foldr (*) 1
length'  = foldr (\_ n -> 1 + n) 0

这就是 fold(折叠)。它不是被「发明」的,是从重复里被挤出来的——你刚才目睹了整个过程。这个抽取手法本身(把递归骨架和业务逻辑分离)比 fold 更值钱,它是所有高阶函数的出生方式:map 是从「逐个变换」的重复里挤出来的,filter 是从「按条件挑选」里挤出来的。下次你在业务代码里闻到「第三次写同构循环」的味道,就是动手挤一个的时机。

括号往哪边长:foldr vs foldl

fold 有两个方向。foldr(right)括号向右长;foldl(left)带一个累加器从左往右扫,括号向左长。口说无凭,下面的观测台把每一步展开摆给你看——先用 (+) 看结构,再切到 (-) 看两个方向结果真的不同(这也是第 2 章泅渡题的答案:foldr 得 2,foldl 得 -6):

盯着 foldl 的展开多看一眼:它一路只是把表达式越攒越大,走完整个列表之前一个加法都没做。在严格求值的语言里这没什么;在惰性的 Haskell 里,这个「攒」是有实体的——每层括号是一个真实的 thunk,堆在内存里。这里先按下不表,第 16 章空间泄漏专题连本带利算这笔账。

全家福:map 和 filter 也是 fold 的孩子

map f    = foldr (\x acc -> f x : acc) []
filter p = foldr (\x acc -> if p x then x : acc else acc) []
reverse  = foldl (flip (:)) []
maximum (x:xs) = foldl max x xs

练习一下源头碑直觉,验证第一行:map f 把 1 : (2 : []) 的每个 : 换成「先 f 再 :」、[] 换成 [],得到 f 1 : (f 2 : [])。✓ 理论上列表库的所有函数都能用 fold 写——这有个正式说法:fold 是列表的「消去规则」,列表携带的全部信息,fold 都能取出来。实践中当然直接用现成的 map/filter,但知道它们同源,你对「这堆 API 会不会组合出问题」的直觉会准很多。

scanl:留下足迹的 fold

fold 的一个近亲值得单独介绍。scanl 和 foldl 做完全相同的事,区别是把每一步的中间结果都留下来:

λ> foldl (+) 0 [3,5,2,7]
17
λ> scanl (+) 0 [3,5,2,7]
[0,3,8,10,17]

「运行余额」「累计销量」「前缀和」——所有报表类需求的核心原语就是它。配合第 7 章的惰性,scanl 还能扫无限流:scanl (+) 0 [1..] 是全体三角形数的无限列表。Kotlin 1.4 加入的 runningFold、SQL 的窗口函数 SUM() OVER (...),认亲成功。

fold 与 scan 的关系值得咀嚼一句:fold 报告终点,scan 报告全程。调试一个行为怪异的 fold 时,把它临时换成同参数的 scan,中间每一步立刻摊在眼前——这是比打印累加器优雅得多的排障法,在 Kotlin 里把 fold 换成 runningFold 同理适用,值得写进肌肉记忆。

真实代码:一趟遍历,多个指标

实战里最常见的 fold 场景:对同一批数据同时算多个统计量。新手写法是遍历三次(sum 一次、count 一次、max 一次);fold 思维是把累加器做成积类型,一趟全算完:

data Stats = Stats { total :: Int, count :: Int, biggest :: Int }

step :: Stats -> Int -> Stats
step (Stats t c b) x = Stats (t + x) (c + 1) (max b x)

summarize :: [Int] -> Stats
summarize = foldl' step (Stats 0 0 minBound)

-- λ> summarize [12, 7, 45, 3]
-- Stats {total = 67, count = 4, biggest = 45}

三个注意点。其一,累加器是上一章的积类型——ADT 和 fold 在真实代码里几乎总是成对出现。其二,用的是带撇号的 foldl'(严格版),原因上面刚讲过。其三,这个模式直接平移到你的语言:Kotlin 的 fold(Stats(0,0,Int.MIN_VALUE)) { acc, x -> ... }、Java Stream 的 reduce 或 Collectors.teeing,一趟代替三趟,对大数据量就是三倍吞吐差距。

顺带把视野再抬高一档:fold 不是列表的专利。任何「有结构的容器」都能折叠——树、Map、Maybe 都行,Haskell 把这层抽象叫 Foldable(sum/length/elem 的真实签名都是 Foldable t => t a -> …,所以它们对树和 Map 照用)。你只需要在心里留个钩子:「遍历并归约」是结构无关的能力,第 9 章的 Functor 会把「遍历并变换」也抽象成同款。

foldr 的独门绝技:处理无限列表

看这个表达式,先别跑,猜猜会不会死循环:

λ> foldr (&&) True (map even ([2,4] ++ [5..]))   -- 后面跟着无限列表!
False

foldr 展开第一步是 even 2 && foldr (&&) True (…剩下的)。而 && 是惰性的:左边一旦是 False,右边根本不看。所以折到 5(第一个奇数)就短路返回,无限列表毫发无伤。foldl 做不到——它必须先走完列表才开始算,而无限列表走不完。规则由此得出:

标准库里这个家族人丁兴旺,认清族谱免得选错工具——顺手给出每位成员「体内是哪个 fold」:

规律一眼可见:需要看完全部数据的,底下是 foldl';可能提前收工的,底下是 foldr。这张表同时是下一节选型口诀的实证。