列表折叠（Folds）与扫描（Scans）¶

“折叠”（Fold，在一些语言中叫 Reduce 或 Accumulate）是处理集合最基本的高阶抽象之一。它用一个二元函数把列表中的所有元素依次“聚合”成一个结果。

从递归到折叠¶

看两个常见的递归函数，求和与求积：

mySum :: Num a => [a] -> a
mySum []     = 0
mySum (x:xs) = x + mySum xs

myProduct :: Num a => [a] -> a
myProduct []     = 1
myProduct (x:xs) = x * myProduct xs

两者的骨架完全相同：

一个面对空列表时的初始值（0 或 1）。
一个把当前头元素与后续递归结果结合起来的二元运算（+ 或 *）。

把这个模式抽出来，就得到了折叠。

右折叠：foldr¶

定义在 Prelude 中：

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

展开结构¶

foldr 的计算是右结合的：

foldr f z [1, 2, 3]
==> 1 `f` (2 `f` (3 `f` z))

画成树，最外层的 f 接收的是第一个元素和“剩余部分的折叠结果”：

        graph TD
  R1["f 1 (...)"] --> A1["1"]
  R1 --> R2["f 2 (...)"]
  R2 --> A2["2"]
  R2 --> R3["f 3 z"]
  R3 --> A3["3"]
  R3 --> Z["z"]

可以把 foldr 理解为：把列表构造中的每个 (:) 换成函数 f，把末尾的 [] 换成初始值 z：

-- 原始列表：
1 : (2 : (3 : []))

-- foldr (+) 0 展开后：
1 + (2 + (3 + 0))

foldr 的惰性短路与无限列表¶

foldr 是从外层向内层展开的。如果合并函数 f 只看第一个参数就能决定结果，不需要求值第二个参数，那么剩下的计算就不会发生。

这意味着 foldr 可以用于无限列表：

-- 检查列表中是否存在偶数：
myAnyEven :: [Integer] -> Bool
myAnyEven = foldr (\x acc -> if even x then True else acc) False

ghci> myAnyEven ([1, 3, 5, 8] ++ [9, 11 ..])
True  -- 遇到 8 之后直接返回 True，后面的无限奇数序列不会被计算

左折叠：foldl 与严格版本 foldl’¶

定义与展开¶

foldl 从左向右累加，计算是左结合的：

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

展开形式：

foldl f z [1, 2, 3]
==> ((z `f` 1) `f` 2) `f` 3

画成树，最外层的 f 接收的是“前面部分的累加结果”和最后一个元素，与 foldr 的树正好左右相反：

        graph TD
  L3["f (...) 3"] --> L2["f (...) 2"]
  L3 --> B3["3"]
  L2 --> L1["f z 1"]
  L2 --> B2["2"]
  L1 --> Z["z"]
  L1 --> B1["1"]

foldl 的空间泄漏问题¶

在惰性求值下，普通 foldl 存在性能隐患。

计算 foldl (+) 0 [1..1000000] 时，每一步的 (0 + 1)、((0 + 1) + 2) 都不会立即算出数值，而是在堆上构造一个不断增长的待计算表达式（Thunk 链）。遍历到列表末尾后，程序才开始展开这个一百万层的嵌套表达式。结果是内存占用随列表长度线性增长，速度也明显变慢，列表足够大时会耗尽内存。

严格左折叠：Data.List.foldl’¶

Data.List 提供了严格求值的 foldl'：

import Data.List (foldl')

sumStrict :: Num a => [a] -> a
sumStrict = foldl' (+) 0

foldl' 在进入下一步之前，会先把累加器求值到弱头范式（WHNF），因此内存占用保持在 O(1)。

不需要初始值的折叠：foldr1 与 foldl1’¶

当列表保证非空，并且希望直接用第一个（或最后一个）元素作为初始值时，可以使用 foldr1 与 foldl1'：

import Data.List (foldl1')

myMaximum :: Ord a => [a] -> a
myMaximum = foldl1' max

警告

foldr1 与 foldl1' 在空列表 [] 上会抛出运行时异常。如果不能保证列表非空，应搭配 Data.List.NonEmpty 或自己做模式匹配。

foldr 与 foldl’ 的选择¶

foldr 与 foldl’ 对比¶
对比维度	foldr	Data.List.foldl’
结合方向	从右向左（右结合）	从左向右（左结合）
求值策略	惰性，由消费者的需求驱动	每一步严格求值累加器
无限列表	支持（只要合并函数能短路）	不支持（必须遍历到末尾）
适用场景	生成新列表、管道式转换、短路判断	有限列表的数值聚合（求和、计数）
使用建议	常用	常用；不带撇号的 `foldl` 一般没有理由使用

扫描：scanl 与 scanr¶

扫描（Scan）与折叠类似，区别在于折叠只返回最终结果，而扫描会把每一个中间累加状态收集成列表。

scanl¶

-- 记录累加的每一步部分和：
ghci> scanl (+) 0 [1, 2, 3, 4]
[0,1,3,6,10]

scanr¶

-- 从右向左扫描：
ghci> scanr (+) 0 [1, 2, 3, 4]
[10,9,7,4,0]

示例：无限斐波那契数列¶

利用 scanl 与惰性求值，可以用一行定义无限斐波那契数列：

fibs :: [Integer]
fibs = 0 : scanl (+) 1 fibs

ghci> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]

用 foldr 实现其他列表函数¶

foldr 可以看作列表的通用消解原语，许多标准库函数都能用它直接写出：

-- 用 foldr 实现 map
myMap :: (a -> b) -> [a] -> [b]
myMap f = foldr (\x acc -> f x : acc) []

-- 用 foldr 实现 filter
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter p = foldr (\x acc -> if p x then x : acc else acc) []

-- 用 foldr 实现 concat
myConcat :: [[a]] -> [a]
myConcat = foldr (++) []

-- 用 foldr 实现 reverse
myReverse :: [a] -> [a]
myReverse = foldr (\x acc -> acc ++ [x]) [] -- 仅作演示，这个写法是 O(n²)，实际应使用 foldl' (flip (:)) []

编译器的融合优化（Fusion）¶

读者可能会担心：链式调用 map、filter 与折叠，会不会在内存中反复创建和销毁中间列表？

GHC 有重写规则（Rewrite Rules）与列表融合（Fusion / Deforestation）机制。在开启 -O 或 -O2 优化后，例如：

map f (map g xs)  ==优化为==>  map (f . g) xs

许多情况下中间列表根本不会被分配，多个遍历会被合并成一个循环。也就是说，把逻辑拆成多个小的高阶函数组合，通常不需要为性能付出额外代价。

小结¶

foldr 是右结合的惰性折叠，支持短路与无限列表。
Data.List.foldl' 是严格的左折叠，适合有限列表的数值聚合，不会堆积 Thunk。
scanl/scanr 返回折叠的中间状态序列，可以用来定义递归的无限流。
GHC 的融合优化会消除大部分中间列表，高阶函数组合通常不会带来额外开销。

← 字符串与文本处理常用容器与文本类型：Map、Set、Vector、Seq 与 Text →