折叠在Option上的关系是什么，等等，并在Traversable上折叠？ [英] What's the relation of fold on Option, Either etc and fold on Traversable?
问题描述
fold 的方法，比如 Boolean ， Option [ _] ，验证[_，_] ， [_，_] 等。这种方法基本上针对给定的ADT使用与所有可能情况相对应的函数。换句话说，模式匹配如下所示：
x匹配{
case Case1（a，b，c） => f（a，b，c）
case情况2（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 =内容：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？我没有看到两者之间有任何相似之处。我错过了什么？
解决方案我认为你遇到的问题是你看到这些东西是基于他们的实现，而不是他们的类型。考虑这种简单的表示形式：
列表[A] =无
|负责人：尾巴：名单[A]
选项[A] =无
|一些el：A
现在，让我们考虑 Option 's fold：
fold [B] =（noneCase：=> B，someCase：A => B） => B
因此，在期权每一个可能的情况下，一些价值在 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
，因为折叠它总是会返回一个 B ，给定类型签名折。现在，我们来看看Scala的（用例）类型签名： $ $ $ $ > foldRight [B]（z：B）（f：（A，B）⇒B）：B
<说，这是否提醒你一些事情？
Scalaz provides a method named fold for various ADTs such as Boolean, Option[_], Validation[_, _], Either[_, _] etc. This method basically takes functions corresponding to all possible cases for that given ADT. In other words, a pattern match shown below:
x match {
case Case1(a, b, c) => f(a, b, c)
case Case2(a, b) => g(a, b)
.
.
case CaseN => z
}
is equivalent to:
x.fold(f, g, ..., z)
Some examples:
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
At the same time, there is an operation with the same name for the Traversable[_] types, which traverses over the collection performing certain operation on its elements, and accumulating the result value. For example,
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
Why are these two operations identified with the same name - fold/catamorphism? I fail to see any similarities/relation between the two. What am I missing?
I think the problem you are having is that you see these things based on their implementation, not their types. Consider this simple representation of types:
List[A] = Nil
| Cons head: A tail: List[A]
Option[A] = None
| Some el: A
Now, let's consider Option's fold:
fold[B] = (noneCase: => B, someCase: A => B) => B
So, on Option, it reduces every possible case to some value in B, and return that. Now, let's see the same thing for List:
fold[B] = (nilCase: => B, consCase: (A, List[A]) => B) => B
Note, however, that we have a recursive call there, on List[A]. We have to fold that somehow, but we know fold[B] on a List[A] will always return B, so we can rewrite it like this:
fold[B] = (nilCase: => B, consCase: (A, B) => B) => B
In other words, we replaced List[A] by B, because folding it will always return a B, given the type signature of fold. Now, let's see Scala's (use case) type signature for foldRight:
foldRight[B](z: B)(f: (A, B) ⇒ B): B
Say, does that remind you of something?
这篇关于折叠在Option上的关系是什么，等等，并在Traversable上折叠？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
