foldLeft诉foldRight -有关系吗？

Question

以前，尼古拉斯·里诺多在Scala的列表foldRight总是使用foldLeft？上回答了我的问题

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

正如我所理解的，原因是性能--前者发生在O(1)中，即将一个项添加到前面的恒定时间。而后者则需要O(N)，即遍历整个列表并添加一个项。

在Scala中，考虑到foldLeft是按照foldRight实现的，那么使用:+ over ++和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的答案确实与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。

Answer 2

我可以为Haskell提供一个答案，但我怀疑它是否与Scala相关：

让我们从两者的来源开始，

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

现在，让我们看看对foldl或foldr的递归调用在哪里出现在右侧。对于叶酸来说，它是最外面的。对于foldr，它位于f的应用程序中。这有几个重要的含义：

1. 如果f是一个数据构造函数，则该数据构造函数将是最左边的，最外层的为foldr。这意味着foldr实现了保守递归，这样就有可能实现以下操作：走5路。(1)$.

这意味着，例如，foldr既可以是一个好的生产者，也可以是短途融合的好消费者。(是的，foldr (:) []是列表的同一性态射。)

对于foldl来说，这是不可能的，因为构造函数将在对foldl的递归调用中，并且不能被模式匹配。

1. 相反，由于对foldl的递归调用位于最左边、最外层的位置，因此它将通过延迟计算而减少，并且不会占用模式匹配堆栈上的空间。结合适当的严格注释(例如foldl')，这允许像sum或length这样的函数在常量空间中运行。

有关这方面的更多信息，请参见哈斯克尔的懒惰评价。

Answer 3

实际上，无论是在Scala中使用foldLeft还是foldRight (至少在默认实现中)，至少在lists中使用是很重要的。不过，我相信这个答案并不适用于库拉兹这样的图书馆。

如果您查看foldLeft和foldRight for LinearSeqOptimized的源代码，您将看到：

• foldLeft是用循环和局部可变变量实现的，适合于一个堆栈帧。
• foldRight是递归的，但不是尾递归的，因此在列表中每个元素使用一个堆栈帧。

因此，foldLeft是安全的，而foldRight可能会对长列表堆叠溢出。

编辑来完成我的答案，因为它只包含你的问题的一部分:它也是重要的，你使用哪一个取决于你打算做什么。

以您的例子为例，我认为最优的解决方案是使用foldLeft，将结果先于累加器，并将结果放在reverse上。

这条路：

• 整个操作是O(n)
• 它不会使堆栈溢出，而不管列表的大小如何。

假设foldRight是用foldLeft实现的，这基本上就是您认为您在使用它时所做的事情。

如果您使用foldRight，您将得到一个更快的实现(嗯，稍微.两倍的速度，真的，但仍然是O(N)，以安全为代价。

有人可能会说，如果您知道您的列表足够小，那么就没有安全问题，您可以使用foldRight。我觉得，但这只是一个观点，如果你的列表足够小，你不必担心你的堆栈，它们也足够小，你也不必担心性能的影响。