为什么 s ++大s不会导致堆栈溢出吗？

Question

我想知道为什么

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

不会导致堆栈溢出错误。前奏中的 ++ 看起来很简单并且非尾递归：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

编辑：最初，我认为这个问题与前奏中定义 ++ 的方式有关，特别是与重写规则有关，因此问题继续为以下。讨论告诉我事实并非如此。我现在认为一些惰性求值效应会导致代码在没有堆栈溢出的情况下运行，但我不太清楚如何实现。

所以仅仅这样，它应该会遇到堆栈溢出，对吗？所以我认为这可能与遵循 ++ 定义的 ghc 魔法有关：

{-# RULES “++”[~1] 代表所有 xs ys。 xs ++ ys = 增强 (\cn ->foldr cn xs) ys #-}

*这有助于避免堆栈溢出吗？有人可以提供一些关于这段代码中发生的事情的提示吗？**

Answer 1

前奏中的 ++ 看起来很简单并且非尾递归......所以仅仅这样，它应该会遇到堆栈溢出，对吧？

在 Haskell 中，非尾递归通常比尾递归更好，因为非尾递归的东西可能会很懒。您列出的定义比尾递归定义要好得多，因为尾递归定义会继续递归并生成整个列表，即使您只需要第一个元素；而非尾递归则只会做必要的工作。

Answer 2

这不会堆栈溢出 - 即使在没有优化和重写规则的解释器中 - 因为它不使用堆栈。

看一下 (++) 的定义，例如：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

关键是 x : (xs ++ ys) ，也就是说，它是由 (:) “cons” 守护的递归构造函数。因为 Haskell 是惰性的，所以它为 cons 操作分配一个 thunk，并且递归调用会进入这个（堆分配的）thunk。所以你的堆栈分配现在是堆分配，它可以扩展很多。所以这一切所做的就是遍历大列表，在堆上分配新的 cons 对象来替换它正在遍历的对象。简单的！

“reverse”有点不同：

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

这是一个尾递归、累加器样式的函数，因此它会在堆上分配。

所以你看，这些函数依赖于在堆上使用 cons 单元，而不是在堆栈上，因此没有堆栈溢出。

为了真正解决这个问题，请查看 GC 虚拟机的运行时统计信息：

$ time ./B +RTS -s
99

         833 MB total memory in use (13 MB lost due to fragmentation)
         Generation 0:  3054 collections,     0 parallel,  0.99s,  1.00s elapsed
         %GC time      82.2%  (85.8% elapsed)

这是一个大列表 - 它是在堆上分配的，我们花费 80% 的时间来清理由 (++) 创建的 cons 节点。

经验教训：您通常可以用堆栈换取堆。

Answer 3

编辑：下面的答案即使不是完全错误，也是完全无关的。 Don Stewart 证明了他实际上理解惰性求值，他有正确的解释。

---

如果运行 ghc -ddump-simpl ，您将看到正在使用的函数是 GHC.Base.++ 和 GHC.List.reverse 。代码>.这些函数经过精心设计，不会在大型列表上溢出堆栈。您在 Prelude 中看到的是“参考实现”，而不是实际编译的代码。

以下是我从 GHC 源代码分发中挖掘出的一些代码：

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

以及：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)     ys
  #-}

在第一种情况下，应该清楚发生了什么。在第二个中，我对重写规则有点模糊......