foldLeft v.collyRight - 这有关系吗？

Question

以前,Nicolas Rinaudo回答了我关于Scala 列表的问题foldRight总是使用foldLeft？

目前正在研究Haskell,我的理解是,在(prepend)可以使用(append)的情况下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).

因此,无论你选择是什么,或者不是因为这些函数本身,而是因为赋予它们的匿名函数,它实际上很重要.如果两者都是等效的,则默认选择.foldLeftfoldRightfoldLeft

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的递归调用.对于foldl,它是最外面的.对于foldr,它在f的应用程序内.这有几个重要的含义:

1. 如果f是数据构造函数,那么该数据构造函数将是最左侧的,最外层的是foldr.这意味着foldr实现了保护递归,因此可以实现以下功能:

   > take 5 . foldr (:) [] $ [1..]
   [1,2,3,4]
   

   这意味着,例如,foldr既可以是良好的生产者,也可以是短切融合的良好消费者.(是的,foldr (:) []是列表的身份态射.)

   对于foldl,这是不可能的,因为构造函数将在对foldl的递归调用内,并且不能进行模式匹配.

2. 相反,因为对foldl的递归调用位于最左侧,最外侧位置,所以它将通过延迟求值来减少,并且不会占用模式匹配堆栈上的空间.结合适当的严格注释(例如foldl'),这允许函数像sum或length在恒定空间中运行.

有关这方面的更多信息,请参阅Haskell的Lazy Evaluation.

Answer 3

事实上,无论你是使用foldLeft还是foldRight在Scala中,至少在列表中,至少在默认实现中是这样.我相信这个答案并不适用于像scalaz这样的图书馆.

如果你看看源代码foldLeft,并foldRight为LinearSeqOptimized,你会看到:

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

foldLeft因此是安全的,而foldRight可能为长列表堆栈溢出.

编辑 要完成我的答案,因为它只能解决您的部分问题:根据您打算做的事情,您使用哪一个也很重要.

举个例子,我认为最佳解决方案是使用foldLeft,将结果预先添加到累加器,以及reverse结果.

这条路:

• 整个操作是O(n)
• 无论列表的大小如何,它都不会溢出堆栈

这基本上是你认为你foldRight在假设它是按照实现的方式做的foldLeft.

如果你使用foldRight,你会得到一个稍微快一点的实现(好吧,稍微......两倍的速度,真的,但仍然是O(n))以安全为代价.

有人可能会说,如果你知道你的名单足够小,就没有安全问题,你可以使用foldRight.我觉得,但这只是一个意见,如果你的名单足够小,你不必担心你的堆栈,它们足够小,你也不必担心性能损失.

Answer 4

这取决于以下因素：

scala> val l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> l.foldLeft(List.empty[Int]) { (acc, ele) => ele :: acc }
res0: List[Int] = List(3, 2, 1)

scala> l.foldRight(List.empty[Int]) { (ele, acc) => ele :: acc }
res1: List[Int] = List(1, 2, 3)

如您所见，foldLeft从列表遍历head到最后一个元素。 foldRight另一方面，它从最后一个元素遍历到head。

如果将折叠用于聚合，则应该没有区别：

scala> l.foldLeft(0) { (acc, ele) => ele + acc }
res2: Int = 6

scala> l.foldRight(0) { (ele, acc) => ele + acc }
res3: Int = 6