选项上的折叠关系是什么,是等等还是折叠在Traversable上？

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

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].我们必须以某种方式折叠,但我们知道fold[B]一个List[A]将永远返回B,所以我们可以像这样重写它:

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

换句话说,我们替换List[A]为B,因为折叠它将始终返回a B,给定类型签名fold.现在,让我们看看Scala的(用例)类型签名foldRight:

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

说,这会让你想起什么吗？

Answer 2

如果你认为"折叠"是"通过一个操作使用种子值来压缩容器中的所有值",并且你认为Option是一个最多只能有一个值的容器,那么这就开始有意义了.

事实上,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也定义在两个List和Option在Scala的标准库,具有相同签名(我相信他们都继承了它从一个特质,其实).再一次,你在单身人士名单上获得与在某些人身上相同的结果:

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 Option/ Either/等等,你在那里提出了一个好点.它似乎与我习惯的"折叠"具有完全不同的签名和操作.