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

Question

我想知道为什么

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

不会导致堆栈溢出错误.前奏中的++似乎是直接的,非尾递归的:

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

编辑:最初,我认为这个问题与前奏中定义的++的方式有关,特别是对于重写规则,因此问题继续如下.讨论向我表明情况并非如此.我现在认为一些懒惰的评估效果导致代码在没有堆栈溢出的情况下运行,但我不太明白如何.

所以就这样,它会遇到堆栈溢出,对吧？所以我认为它可能与遵循++定义的ghc魔法有关:

{ - #RULES"++"[~1] forall xs ys.xs ++ ys = augment(\ 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 l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

这是一个尾递归,累加器式函数,所以再次,它将在堆上分配.

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

要真正指出这一点,请查看GC vm中的运行时统计信息:

$ 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节点.

经验教训:你经常可以用堆栈交换堆栈.