Option、Either等类型的fold与Traversable上的fold有什么关系？

Question

Scalaz提供了一个名为fold的方法，用于各种ADT，例如Boolean，Option[_]，Validation[_, _]，Either[_, _]等。该方法基本上需要使用与给定ADT的所有可能情况对应的函数。换句话说，就是下面所示的模式匹配：

x match {
  case Case1(a, b, c) => f(a, b, c)
  case Case2(a, b) => g(a, b)
  .
  .
  case CaseN => z
}

等同于：

x.fold(f, g, ..., z)

一些示例：

scala> (9 == 8).fold("foo", "bar")
res0: java.lang.String = bar

scala> 5.some.fold(2 *, 2)
res1: Int = 10

scala> 5.left[String].fold(2 +, "[" +)
res2: Any = 7

scala> 5.fail[String].fold(2 +, "[" +)
res6: Any = 7

同时，Traversable[_] 类型也有一个同名操作，它遍历集合并对其元素执行某些操作，并累积结果值。例如：

scala> List(2, 90, 11).foldLeft("Contents: ")(_ + _.toString + " ")
res9: java.lang.String = "Contents: 2 90 11 "

scala> List(2, 90, 11).fold(0)(_ + _)
res10: Int = 103

scala> List(2, 90, 11).fold(1)(_ * _)
res11: Int = 1980

为什么这两个操作要使用相同的名称——fold/catamorphism？我没有看到它们之间有任何相似性或关系。我错过了什么吗？

- missingfaktor

Answer 1

我认为你遇到的问题是你基于实现而不是类型来看待这些东西。考虑一下类型的简单表示：

List[A] = Nil 
        | Cons head: A tail: List[A]

Option[A] = None
          | Some el: A

现在，让我们考虑一下“Option”的折叠功能：

fold[B] = (noneCase: => B, someCase: A => B) => B

因此，在 Option 中，它将每种可能的情况都缩减为 B 中的某个值，并返回该值。现在，让我们看看 List 的情况：

fold[B] = (nilCase: => B, consCase: (A, List[A]) => B) => B

然而请注意，我们在List[A]上有一个递归调用。我们必须以某种方式折叠它，但是我们知道在List[A]上的fold[B]将始终返回B，因此我们可以像这样重写它：

fold[B] = (nilCase: => B, consCase: (A, B) => B) => B

换句话说，我们用B替换了List[A]，因为根据fold的类型签名，将其折叠总是会返回一个B。现在，让我们看看Scala中foldRight的用例类型签名：

foldRight[B](z: B)(f: (A, B) ⇒ B): B

你觉得这让你想起了什么吗？

- Daniel C. Sobral

---

哦，所以它必须递归应用！有道理，谢谢。 - missingfaktor

维基百科关于“折叠映射”（catamorphism）的页面(http://en.wikipedia.org/wiki/Catamorphism)上说，“在函数式编程中，折叠映射是对列表上已知的折叠操作进行泛化，适用于可以被描述为初始代数的任意代数数据类型。” 然后它指向了Erik Meijer的论文“Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”。我认为我应该阅读这篇论文以更好地理解这个主题。 - missingfaktor

@missingfaktor，在维基百科页面的末尾，有一个关于范畴折叠的6部分博客，似乎非常易懂。我正在阅读它。虽然是F#语言，但我相信这对您不会构成问题。 - huynhjl

@huynhjl：哦，我最初错过了那个。谢谢你指出来！ - missingfaktor

Answer 2

如果您把"折叠"看作是通过一种带有种子值的操作将容器中的所有值压缩到一起，而将Option视为一个最多只能包含一个值的容器，那么这就开始变得合理了。

实际上，如果您在空列表和None上使用它，以及在仅有一个元素和Some的列表上使用它，则foldLeft具有相同的签名，并且会给您完全相同的结果。

scala> val opt : Option[Int] = Some(10)
opt: Option[Int] = Some(10)

scala> val lst : List[Int] = List(10)
lst: List[Int] = List(10)

scala> opt.foldLeft(1)((a, b) => a + b)
res11: Int = 11

scala> lst.foldLeft(1)((a, b) => a + b)
res12: Int = 11

fold 在 Scala 标准库中也定义在 List 和 Option 上，具有相同的签名（实际上我认为它们都是从一个 trait 继承而来）。同样地，在单例列表和 Some 上使用时，你会得到相同的结果：

scala> opt.fold(1)((a, b) => a * b)
res25: Int = 10

scala> lst.fold(1)((a, b) => a * b)
res26: Int = 10

对于 Scalaz 中 Option/Either/等类型的 fold，我不是完全确定，你提出了一个很好的观点。它似乎有着与我所熟悉的“折叠”操作相当不同的签名和操作方式。

- Ben