Scala折叠右侧和折叠左侧

Question

我正在尝试学习函数式编程和Scala，所以我正在阅读Chiusano和Bjarnason的《Scala函数式编程》。在处理列表时，我不太理解fold left和fold right方法的作用。我在这里找了一下，但没有找到适合初学者的内容。因此，书中提供的代码如下：

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match {
  case Nil => z
  case Cons(h, t) => f(h, foldRight(t, z)(f))
}

def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
  case Nil => z
  case Cons(h,t) => foldLeft(t, f(z,h))(f)
}

Cons 和 Nil 分别代表：

case class Cons[+A](head: A, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

那么，“fold left”和“fold right”到底是做什么的？为什么它们被称为“实用”方法？许多其他方法都使用它们，但我也很难理解它们，因为我不太懂这两个方法。

- jrsall92

---

请查看下一个线程。https://dev59.com/KmAf5IYBdhLWcg3wskeQ 这些操作有很多信息。在我看来，这似乎是一个重复的问题。 - Pavel

在那个问题中，似乎提问者对手头的问题有相当好的理解，而我并没有，这就是我需要帮助的地方。 - jrsall92

您提供的代码，您有任何具体问题吗？到底是什么造成了困难？语法？理解区别的关键在于递归调用本身的方式。这是不同的。请阅读有关尾递归的内容。希望这可以帮助您。更多链接：https://oldfashionedsoftware.com/2009/07/10/scala-code-review-foldleft-and-foldright/ - Pavel

如果你有时间并且真的想把所有的知识点串联起来，可以阅读 https://mitpress.mit.edu/sicp/。这需要一些时间，如果你的计算机科学基础扎实，也可以选择性地阅读。祝好运！ - Pavel

@jrsall92 你是正确的。 - michaJlS

Answer 1

根据我的经验，锻炼直觉的最佳方法之一是通过看它在非常简单的例子上如何工作：

List(1, 3, 8).foldLeft(100)(_ - _) == ((100 - 1) - 3) - 8 == 88
List(1, 3, 8).foldRight(100)(_ - _) == 1 - (3 - (8 - 100)) == -94

正如您所看到的，foldLeft/Right 只是将列表元素和先前应用的结果传递给第二个括号中的操作。

需要注意的是，如果您将这些方法应用于相同的列表，则仅当应用的操作是可结合的时，它们才会返回相等的结果。

- Aliaksei Kuzmin

---

我认为你的操作应该是'(_ - _)'，也就是减法而不是加法。除此之外，你对foldLeft和foldRight之间的区别做了非常好的解释。 - melston

@melston，减法比加法更好。一个是可交换的，而另一个则不是。 - Remis Haroon - رامز

Answer 2

假设你有一组数字，想要将它们全部加起来。你应该怎么做？

首先将第一个数和第二个数相加，然后将结果与第三个数相加，再将结果与第四个数相加……以此类推。

这就是fold能够帮助你实现的功能。

List(1,2,3,4,5).foldLeft(0)(_ + _)

“+”是您要应用的函数，其中第一个操作数是到目前为止应用其结果的元素，第二个操作数是下一个元素。 由于在第一次应用中没有“到目前为止”的结果，因此您需要提供起始值-在这种情况下为0，因为它是加法的单位元素。

假设您想使用fold来乘以所有列表元素，则为

List(1,2,3,4,5).foldLeft(1)(_ * _)

折叠有自己的维基百科页面，您可能想要查看。

当然，foldLeft和foldRight也有ScalaDoc条目。

- lutzh

Answer 3

在Scala中，另一种可视化leftFold和rightFold的方法是通过字符串连接，它清晰地展示了leftFold和rightFold的工作原理，让我们看下面的例子：

val listString = List("a", "b", "c") // : List[String] = List(a,b,c)
val leftFoldValue = listString.foldLeft("z")((el, acc) => el + acc) // : String = zabc
val rightFoldValue = listString.foldRight("z")((el, acc) => el + acc) // : abcz 

或者的简写方式

val leftFoldValue = listString.foldLeft("z")(_ + _) // : String = zabc
val rightFoldValue = listString.foldRight("z")(_ + _) // : String = abcz

Explanation:

leftFold的作用为( ( ('z' + 'a') + 'b') + 'c') = ( ('za' + 'b') + 'c') = ('zab' + 'c') = 'zabc'

而rightFold则为('a' + ('b' + ('c' + 'z'))) = ('a' + ('b' + 'cz')) = ('a' + 'bcz') = 'abcz'

- krishna Prasad