为什么Haskell的foldr不会发生堆栈溢出，而相同的Scala实现会呢？

Question

我正在阅读Scala函数式编程。

第3.10题说foldRight会溢出（参见下面的图片）。 就我所知，然而，在Haskell中foldr不会。

http://www.haskell.org/haskellwiki/

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

这种不同的行为是如何实现的？

这两种语言/编译器之间有什么区别，导致出现这种不同的行为？

这种差异来自哪里？平台？语言？编译器？

在Scala中是否可能编写一个堆栈安全的foldRight？如果是，怎么做？

- jhegedus

---

在Haskell中，foldr不是尾递归的，因此仍然容易出现堆栈溢出错误。而在Haskell中与众不同的是惰性求值语义，有时允许foldr不评估折叠操作符的两个参数。更多细节请参见：http://www.haskell.org/haskellwiki/Stack_overflow - Ionuț G. Stan

此外，Scala内置的 foldRight 方法现在不易导致堆栈溢出，因为它在反转列表上调用 foldLeft 方法，而 foldLeft 方法甚至不是递归的。https://github.com/scala/scala/blob/v2.11.2/src/library/scala/collection/immutable/List.scala#L396-L397 https://github.com/scala/scala/blob/v2.11.2/src/library/scala/collection/LinearSeqOptimized.scala#L105-L114 - Ionuț G. Stan

Scala老版本的foldRight问题票：https://issues.scala-lang.org/browse/SI-3295 - Ionuț G. Stan

在Scala中，foldRight和foldLeft是严格的。在Haskell中，foldr'和foldl'也是严格的。但是在Haskell中，foldr和foldl是惰性的。因此，foldRight、foldr'和foldl可能会溢出。 - viorior

@viorior，Haskell在Prelude或Data.List中没有foldr'，因为它根本没有用处——将一个对第二个参数严格的函数传递给foldr会得到严格的行为（如果列表很长可能会导致堆栈溢出）。 - dfeuer

Answer 1

Haskell是一种惰性编程语言。以下是其定义：

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

根据该段文字，当一个非空列表xs与组合函数f的惰性有关时，foldr f z xs的行为就被确定了。

特别地，对于调用foldr f z (x:xs)，它在堆上仅分配一个thunk，即{foldr f z xs}（用{...}表示包含表达式...的thunk），并使用两个参数x和thunk调用f。接下来发生的事情取决于f。

具体而言，如果它是一个惰性数据构造函数（例如(:) ），它将立即返回到foldr调用者（构造函数的两个插槽由（引用）两个值填充）。

如果f确实需要其右侧的值，则在最小编译器优化的情况下，不会创建任何thunk（或最多一个 - 当前的thunk），因为需要foldr f z xs的值，并且可以使用常规的基于堆栈的评估：

foldr f z [a,b,c,....,n] ==
    a `f` (b `f` (c `f` (... (n `f` z)...)))

foldr在使用严格的组合函数处理极长的输入列表时确实会导致SO问题。但如果组合函数不要求立即获取其右侧的值，或仅要求部分值，则计算将被悬挂在一个thunk中，并且由f创建的部分结果将立即返回。左侧的参数也是如此，但它们已经作为thunk存在于输入列表中。

- Will Ness

---

foldr (+) 0 [1..100000000000] 会计算出结果，因为 (+) 是一个严格（strict）函数。但是 foldr (:) [] [1..100000000000] 只会返回 1 : {foldr (:) [] [2..100000000000]}，因为 (:) 是一个惰性（lazy）数据构造器（它不要求其参数的全部值，并且只在其两个字段 head 和 tail（或者 Lisp 中的 car 和 cdr）中存储对未来计算的挂起指针）。 - Will Ness

想象一个记录，其中包含：a. 一个布尔值 has_value?，最初设置为 False；b. 一个没有参数的 lambda 函数，或者任何其他表示未来计算的方式，可以调用该函数以获取该值；c. 存储计算后的值的位置。这就是懒计算（thunk）的概念。 - Will Ness

你的例子 foldr (+) 0 [1..10000000000] 会导致 SO，但是 foldl (+) 0 [1..10000000000] 不会导致 SO？这样说对吗？ - jhegedus

foldl (+) 0 [1..10000000000] 会以另一种方式导致 SO。关于这个问题有一个很好的答案，我马上会搜索链接。在这里：https://dev59.com/sGcs5IYBdhLWcg3wOBNC#13052612 （不用谢 :)) - Will Ness

“thunk”是“think”的方言过去式和过去分词。也就是说，表达式在第一次需要时才被评估，然后它会被评估并且其结果值被存储 - 所以下次需要它时我们就不必再“思考”，因为它已经被“thunk”了。这就是故事的来由。 - Will Ness

Answer 2

Haskell是一种惰性语言。 因此，foldr分配在堆上而不是栈上。 根据参数函数的严格性，它可能会分配单个（小）结果或大型结构。

与严格的尾递归实现相比，您仍然会损失空间，但它看起来不太明显，因为您已经将堆栈交换了。

- Don Stewart

---

考虑 foldr 中的递归函数 go: http://hackage.haskell.org/package/base-4.7.0.1/docs/src/GHC-Base.html#foldr 。go 在堆上返回一个挂起的操作。 - Don Stewart

我已经澄清了，这不应该与简单的foldl (+)惰性堆空间泄漏混淆。如果k合适，foldr可以在恒定空间中运行。 - Don Stewart

Answer 3

请注意，作者在这里并不是指Scala标准库中的任何foldRight定义，例如List上定义的那个。他们所指的是在第3.4节中给出的foldRight的定义。

Scala标准库通过反转列表（可以在恒定的堆栈空间内完成）来将foldRight定义为foldLeft，然后使用传递函数的参数的反转调用foldLeft。这适用于列表，但对于不能安全地反转的结构，例如：它将无法工作。

scala> Stream.continually(false)
res0: scala.collection.immutable.Stream[Boolean] = Stream(false, ?)

scala> res0.reverse
java.lang.OutOfMemoryError: GC overhead limit exceeded

现在让我们思考一下这个操作应该得到什么结果：

。

Stream.continually(false).foldRight(true)(_ && _)

答案应该是false，无论流中有多少个假值或者它是否是无限的，如果我们要用“与”运算符结合它们，结果将是false。

当然，Haskell毫不费力地实现了这一点。

Prelude> foldr (&&) True (repeat False)
False

这是由于两个重要的原因：Haskell的foldr将从左到右遍历流，而不是从右到左，并且Haskell默认是惰性的。 第一个项目在这里是，foldr实际上从左到右遍历列表可能会让一些人感到惊讶或困惑，他们认为右折叠从右边开始，但正确折叠的重要特征不在于它开始的结构的哪一端，而在于结合性的方向。 因此，给定一个列表[1,2,3,4]和一个名为op的操作符，左折叠是：

((1 op 2) op 3) op 4)

右折叠是这样的

(1 op (2 op (3 op 4)))

但是评估的顺序不应该有所区别。在第3章中，作者们给出了一个从左到右遍历列表的折叠，但是由于Scala默认是严格的，我们仍然无法遍历无限假流，但是请耐心等待，他们将在第5章中处理这个问题 :) 让我们来看一下Scala标准库中定义的foldRight与scalaz中定义的Foldable类型类之间的差异：

这是Scala标准库中的实现：

def foldRight[B](z: B)(op: (A, B) => B): B

以下是scalaz的Foldable的定义：

def foldRight[B](z: => B)(f: (A, => B) => B): B

区别在于所有的B都是惰性的，现在我们需要再次折叠我们的无限流，只要我们提供一个在其第二个参数中足够惰性的函数：

scala> Foldable[Stream].foldRight(Stream.continually(false),true)(_ && _)
res0: Boolean = false

- stew

Answer 4

在Haskell中演示这一点的一个简单方法是使用等式推理来演示惰性求值。让我们用foldr函数编写find函数：

-- Return the first element of the list that satisfies the predicate, or `Nothing`.
find :: (a -> Bool) -> [a] -> Maybe a
find p = foldr (step p) Nothing 
    where step pred x next = if pred x then Just x else next

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

在急切求值语言中，如果你使用foldr写find函数，它会遍历整个列表并使用O(n)的空间。而在惰性求值中，它会在第一个满足条件的元素处停止，并且仅使用O(1)的空间（垃圾回收除外）。

find odd [0..]
    == foldr (step odd) Nothing [0..]
    == step odd 0 (foldr (step odd) Nothing [1..])
    == if odd 0 then Just 0 else (foldr (step odd) Nothing [1..])
    == if False then Just 0 else (foldr (step odd) Nothing [1..])
    == foldr (step odd) Nothing [1..]
    == step odd 1 (foldr (step odd) Nothing [2..])
    == if odd 1 then Just 1 else (foldr (step odd) Nothing [2..])
    == if True then Just 1 else (foldr (step odd) Nothing [2..])
    == Just 1

这个评价会在有限的步骤中停止，尽管列表[0..]是无限的，所以我们知道我们没有遍历整个列表。此外，每一步表达式的复杂度都有一个上限，这意味着在评估时需要的内存有一个常量的上限。

关键在于我们正在进行折叠操作的step函数具有这个属性：不管x和next的值是什么，它要么：

1.计算出Just x，而不调用next； 2.调用next（事实上，即使不是字面意义上的调用，也是tail-call）。

- Luis Casillas