scala - foldLeft诉foldRight-有关系吗？

以前，Nicolas Rinaudo回答了我有关Scala的List foldRight Always Using foldLeft?的问题

目前正在研究Haskell，我的理解是，在可以使用foldRight(前置)而不是foldLeft(附加)的情况下，::比++更可取。

据我了解，原因是性能-前者出现在O(1)中，即在前面添加项目-持续时间。后者需要O(N)，即遍历整个列表并添加一个项目。

在Scala中，假设foldLeft是根据foldRight实现的，那么由于:+颠倒了然后是++，使用foldRight而不是将foldRight与foldLeft'd一起使用的好处是否重要？

作为示例，请考虑此简单的fold..操作，以简单地按顺序返回列表的元素。
foldLeft折叠每个元素，通过:+将每个项目添加到列表中。

scala> List("foo", "bar").foldLeft(List[String]()) {
                                                    (acc, elem) => acc :+ elem }
res9: List[String] = List(foo, bar)

foldRight在每个项目上使用::运算符执行foldLeft，但随后反转。

scala> List("foo", "bar").foldRight(List[String]()) {
                                                    (elem, acc) => elem :: acc }
res10: List[String] = List(foo, bar)

实际上，考虑到foldLeft使用foldRight，在Scala中使用哪个foldRight或foldRight无关紧要？

最佳答案

@Rein Henrichs的答案确实与Scala无关，因为Scala对foldLeft和foldRight的实现是完全不同的(对于初学者来说，Scala渴望评估)。
foldLeft和foldRight本身实际上与程序性能无关。两者都是(一般而言)O(n * c_f)，其中c_f是一次调用给定的函数f的复杂性。但是，由于增加了foldRight，reverse的速度降低了一个常数。

因此，将一个人与另一个人区分开的真正因素是您提供的匿名函数的复杂性。有时，编写用于foldLeft的高效函数(有时甚至是foldRight)更容易。在您的示例中，foldRight版本是最好的，因为您赋予foldRight的匿名函数为O(1)。相反，您给foldLeft提供的匿名函数本身就是O(n)(分期偿还，这很重要)，因为acc一直从0增长到n-1，并且附加到n个元素的列表上就是O(n )。

因此，实际上是选择foldLeft还是foldRight都很重要，但这不是因为这些函数本身，而是因为赋予了它们匿名函数。如果两者相等，则默认情况下选择foldLeft。

关于scala - foldLeft诉foldRight-有关系吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24370549/