折叠(fold)

定义

折叠(fold,也称 reduce、accumulate)是函数式编程中最基本的高阶函数之一:给定一个二元函数、一个初始值和一个序列,fold 依次把函数应用于累积值与序列元素,最终把整个结构归约为单一结果。求和即 fold (+) 0。

方向与变体

foldl 从左向右结合,适合累加类计算且可尾递归实现;foldr 从右向左结合,在惰性语言中能处理无限列表并保留短路能力。无初始值的变体(reduce/fold1)取首元素为起点。

理论地位

fold 是列表的"通用消解器":map、filter、length、reverse 等几乎所有列表函数都可以用 fold 定义,这一性质称为 fold 的普遍性。范畴论中它对应 catamorphism(下态射),是递归模式(recursion schemes)理论的起点。

应用

主流语言普遍内置:JavaScript 的 Array.prototype.reduce、Python 的 functools.reduce、Java Stream 的 reduce;MapReduce 框架的 Reduce 阶段与流式聚合同样是折叠思想在分布式场景的体现。