Scala 中的折叠操作详解

1. 简介

在本篇文章中，我们将深入探讨如何在 Scala 中对列表（List）进行折叠（fold）操作。Scala 的 List 类提供了多个折叠方法：fold、foldLeft 和 foldRight。这些方法接受一个初始值和一个组合函数，通过递归地将函数应用于列表中的元素，最终生成一个结果值。

虽然这三种折叠方式在功能上类似，但它们的执行顺序、性能表现和适用场景却各不相同。掌握它们之间的差异，有助于我们在实际开发中做出更合理的选择。

✅ 示例代码：

val list = List(1, 2, 3, 4, 5)
val sum = list.fold(0)((x, y) => x + y)
assert(sum == 15)

这个例子展示了最基本的用法：从左到右依次累加列表中的每个元素，初始值为 0。

2. 折叠操作的基本原理

折叠操作本质上是一种高阶函数，它遍历递归数据结构（如 List），并使用给定的组合函数逐步归约数据结构中的元素，最终得到一个单一的结果。

2.1 执行过程解析

折叠操作的核心在于组合函数的递归应用。以加法为例：

Step 1: x(0) + y(1) = 1
Step 2: x(1) + y(2) = 3
Step 3: x(3) + y(3) = 6
Step 4: x(6) + y(4) = 10
Step 5: x(10) + y(5) = 15 

可以看到，每一步的输出都会作为下一步的第一个操作数参与运算，直到整个列表被处理完毕。

为了方便后续演示，我们定义一个简单的 Person 类型：

case class Person(name: String, sex: String)

val persons = List(
  Person("Thomas", "male"),
  Person("Sowell", "male"),
  Person("Liz", "female")
)

3. foldLeft：从左向右折叠

foldLeft 是最常用的折叠方式之一，它的特点是 从左到右遍历列表，并且将累积值放在组合函数的左侧参数位置。

✅ 示例代码：

val foldedList = persons.foldLeft(List[String]()) { (accumulator, person) =>
  val title = person.sex match {
    case "male" => "Mr."
    case "female" => "Ms."
  }
  accumulator :+ s"$title ${person.name}"
}
assert(foldedList == List("Mr. Thomas", "Mr. Sowell", "Ms. Liz"))

⚠️ 注意：foldLeft 的执行顺序是固定的，适用于需要保持原始顺序的场景。

更正式地说，foldLeft 是左结合的：

List(1, 2, 3).foldLeft(0)(f) = f(f(f(0, 1), 2), 3)

4. foldRight：从右向左折叠

与 foldLeft 相反，foldRight 会 从右向左遍历列表，并将累积值放在组合函数的右侧参数位置。

✅ 示例代码：

val foldedList = persons.foldRight(List[String]()) { (person, accumulator) =>
  val title = person.sex match {
    case "male" => "Mr."
    case "female" => "Ms."
  }
  accumulator :+ s"$title ${person.name}"
}
assert(foldedList == List("Ms. Liz", "Mr. Sowell", "Mr. Thomas"))

⚠️ 注意：由于是从右往左处理，最终结果的顺序与原列表相反。

同样地，foldRight 是右结合的：

List(1, 2, 3).foldRight(0)(f) = f(1, f(2, f(3, 0)))

5. fold：支持并行的通用折叠

fold 与前两者最大的区别在于它是 无序的，可以支持并行计算。换句话说，fold 并不能保证元素的处理顺序。

5.1 并行计算支持

在某些简单场景下，三种折叠方法的结果可能一致，但这并不意味着它们的行为相同。我们可以借助 .par 将普通 List 转换为并行集合来观察差异。

✅ 示例代码：

val parallelNumSeq = List(1, 2, 3, 4, 5).par

使用 foldLeft：

val foldLeftResult =
  parallelNumSeq.foldLeft(0) { (acc, currNum) =>
    val sum = acc + currNum
    println(s"FoldLeft: acc($acc) + currNum($currNum) = $sum ")
    sum
  }
println(foldLeftResult)

输出：

FoldLeft: acc(0) + currNum(1) = 1 
FoldLeft: acc(1) + currNum(2) = 3 
FoldLeft: acc(3) + currNum(3) = 6 
FoldLeft: acc(6) + currNum(4) = 10 
FoldLeft: acc(10) + currNum(5) = 15 
15

使用 foldRight：

val foldRightResult = 
  parallelNumSeq.foldRight(0) { (currNum, acc) =>
    val sum = acc + currNum
    println(s"FoldRight: acc($acc) + currNum($currNum) = $sum")
    sum
  }
println(foldRightResult)

输出：

FoldRight: acc(0) + currNum(5) = 5
FoldRight: acc(5) + currNum(4) = 9
FoldRight: acc(9) + currNum(3) = 12
FoldRight: acc(12) + currNum(2) = 14
FoldRight: acc(14) + currNum(1) = 15
15

使用 fold（并行模式）：

val foldResult = parallelNumSeq.fold(0) { (acc1, acc2) =>
    val sum = acc1 + acc2
    println(s"Fold: acc1($acc1) + acc2($acc2) = $sum")
    sum
  }
println(foldResult)

输出示例：

Fold: acc1(0) + acc2(1) = 1
Fold: acc1(0) + acc2(4) = 4
Fold: acc1(0) + acc2(2) = 2
Fold: acc1(0) + acc2(5) = 5
Fold: acc1(0) + acc2(3) = 3
Fold: acc1(4) + acc2(5) = 9
Fold: acc1(1) + acc2(2) = 3
Fold: acc1(3) + acc2(9) = 12
Fold: acc1(3) + acc2(12) = 15
15

可以看到，fold 在并行模式下会对子集分别折叠，然后合并结果。此时组合函数的两个参数都是“累积值”。

5.2 方法签名对比

三种折叠方法的签名如下：

fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1

foldLeft[B](z: B)(f: (B, A) => B): B

foldRight[B](z: B)(f: (A, B) => B): B

• 对于 foldLeft 和 foldRight，初始值和返回值类型必须一致（均为 B），但列表元素类型可以不同。
• 对于 fold，初始值和返回值必须是列表元素类型或其父类型（即 A1 >: A）。这是为了确保并行计算中各子集结果可以正确合并。

✅ 示例代码：

val stringifiedInts = List("1", "2", "3", "4", "5")
val foldLeftSum = stringifiedInts.foldLeft(0)((acc, currNum) => acc + currNum.toInt)
val foldRightSum = stringifiedInts.foldRight(0)((currNum, acc) => currNum.toInt + acc)
assert(foldLeftSum == 15)
assert(foldRightSum == 15)

在这个例子中，列表元素是 String，而初始值是 Int，这种类型混用在 foldLeft/foldRight 中是允许的。

❌ 但在 fold 中就不行：

// ❌ 编译错误！因为 fold 要求初始值和返回值必须与列表元素类型兼容
List("1", "2", "3").fold(0)(_ + _)

5.3 中性元素的重要性

在使用 fold 进行并行计算时，初始值必须是操作的 中性元素（neutral element），否则结果将不可预测。

✅ 正确示例：

List(1, 2, 3, 4, 5).fold(0)(_ + _) // ✅ 加法的中性元素是 0

❌ 错误示例：

List(1, 2, 3).fold(5)(_ + _) // ❌ 5 不是加法的中性元素，可能导致不一致结果

可能的计算路径包括：

(5 + 1 + 2) + (5 + 3) = 16
或
(5 + 1) + (5 + 2) + (5 + 3) = 21

6. 总结

本文介绍了 Scala 中三种主要的折叠操作：foldLeft、foldRight 和 fold，并对它们的使用方式、行为特点以及适用场景进行了详细说明。

方法名	遍历方向	是否有序	是否支持并行	参数位置
foldLeft	左 → 右	✅ 是	❌ 否	(acc, elem)
foldRight	右 → 左	✅ 是	❌ 否	(elem, acc)
fold	任意	❌ 否	✅ 是	(acc1, acc2)

📌 建议：

• 大多数情况下优先使用 foldLeft，性能好、逻辑清晰；
• 如果需要保留反序，可考虑 foldRight；
• 若涉及并行计算，则应使用 fold，但要注意初始值必须为中性元素。

完整代码示例请参考 GitHub 仓库。