11

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

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？我看不出两者之间有任何相似之处/关系。我错过了什么？

4

2 回答 2

7

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

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

但是请注意，我们在那里有一个递归调用， on List[A]。我们必须以某种方式折叠它，但我们知道fold[B]a List[A]will always return B，所以我们可以像这样重写它：

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

换句话说，我们替换List[A]为B，因为折叠它总是会返回一个B，给定的类型签名fold。现在，让我们看看 Scala 的（用例）类型签名foldRight：

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

说，这是否让你想起了什么？

于 2011-12-16T21:30:54.280 回答
5

如果您将“折叠”视为“通过操作将容器中的所有值压缩为种子值”，并且您将 Option 视为最多可以具有一个值的容器，那么这开始有意义.

事实上，foldLeft如果您在空列表 vs None 以及只有一个元素 vs Some 的列表上使用它，则具有相同的签名并给出完全相同的结果：

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和OptionScala标准库中定义，具有相同的签名（我相信他们都从一个特征继承它，事实上）。再一次，你在单例列表上得到与在 Some 上相同的结果：

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

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

我不是 100% 确定/等fold上来自 Scalaz 的，你在那里提出了一个很好的观点。它似乎与我习惯的“折叠”有很大不同的签名和操作。OptionEither

于 2011-12-17T01:47:09.780 回答