我在一个字符串列表上运行了一个右折叠 (:\),这导致了堆栈溢出。但是当我将其更改为使用左折叠 (/:) 时,它工作正常。为什么?
2 回答
由于源是开放的,您实际上可以在LinearSeqOptimized.scala中看到实现:
override /*TraversableLike*/
def foldLeft[B](z: B)(f: (B, A) => B): B = {
var acc = z
var these = this
while (!these.isEmpty) {
acc = f(acc, these.head)
these = these.tail
}
acc
}
override /*IterableLike*/
def foldRight[B](z: B)(f: (A, B) => B): B =
if (this.isEmpty) z
else f(head, tail.foldRight(z)(f))
您会注意到foldLeft
使用 while 循环 whilefoldRight
使用递归。循环策略非常有效,但递归需要为列表中的每个元素在堆栈上推送一个框架(因为它遍历到末尾)。这就是为什么foldLeft
工作正常但foldRight
导致堆栈溢出的原因。
Fold
是一组通用的通用函数,它们遍历递归数据结构并通常产生单个值(参考)。在序列和列表上,FoldLeft(一般意义上)是尾递归的,因此可以对其进行优化。FoldRight 不是尾递归的,因此不能进行尾调用优化。然而,它确实有可能应用于无限级数的好处。
scala 库的实现foldLeft
(foldRight
从@dhg 的答案盗版)反映了这种优化/缺乏。foldLeft
已使用 while 循环手动优化尾调用。foldRight
不可能是。
override /*TraversableLike*/
def foldLeft[B](z: B)(f: (B, A) => B): B = {
var acc = z
var these = this
while (!these.isEmpty) {
acc = f(acc, these.head)
these = these.tail
}
acc
}
override /*IterableLike*/
def foldRight[B](z: B)(f: (A, B) => B): B =
if (this.isEmpty) z
else f(head, tail.foldRight(z)(f))
我相信Odersky、Spoon、Venners 的 Programming in Scala, Second Edition中的折叠部分描述了foldLeft
Lists 如何是尾递归的,而它可能是foldRight
无限列表。不幸的是,我现在没有它来提供页码等。如果没有,证明这一点并不难。
另请参阅Miran Lipovača 的 Learn You a Haskell for Great Good中的折叠部分
回到我们处理递归的时候,我们注意到在许多对列表进行操作的递归函数中都有一个主题。通常,我们会有一个空列表的边缘情况。我们将引入 x:xs 模式,然后我们将执行一些涉及单个元素和列表其余部分的操作。事实证明这是一种非常常见的模式,因此引入了几个非常有用的函数来封装它。这些函数称为折叠。