选项上的折叠、etc和可遍历上的折叠是什么关系？

Question

Scalaz为不同的ADT提供了一个名为fold的方法，如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？我看不出这两者之间有什么相似之处/关系。我遗漏了什么？

Answer 1

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

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

Option[A] = None
          | Some el: A

现在，让我们考虑一下Option的fold：

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。现在，让我们看看foldRight的Scala(用例)类型签名

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

嘿，这让你想起什么了吗？

Answer 2

如果你认为“折叠”是“通过一个操作，用一个种子值压缩一个容器中的所有值”，并且你认为一个选项是一个最多可以有一个值的容器，那么这就开始有意义了。

事实上，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

在Scala标准库中，fold也在List和Option上定义，具有相同的签名(事实上，我相信它们都是从一个特征继承的)。同样，在单例列表上得到的结果与在某些列表上得到的结果相同：

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

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

我对Option/Either/etc上的Scalaz的fold不是百分之百确定，你在这里提出了一个很好的观点。它似乎有一个完全不同的签名和操作与我习惯的“折叠”。