scala - foldLeft v. foldRight - 有关系吗？

Question

以前，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)

实际上，在 Scala 中， foldLeft 是否重要？或 foldRight鉴于 foldRight使用 foldRight ?

Answer 1

@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默认。