为什么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（\ c n - > foldr c n xs）ys ＃ - }

*这是否有助于避免堆栈溢出？可能有人提供了一些提示，这段代码是怎么回事？**

Answer 1

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

看的定义（++），例如，：

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

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

“反向”是有点不同：

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％的时间清理利弊由（++）创建的节点。

课程：你可以经常堆栈堆栈。

Answer 2

编辑：下面的答案是完全不相干的，如果不是彻头彻尾的错误。唐·斯图尔特，他证明他其实明白懒惰的评价，有正确的解释。

---

如果运行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 
    #-} 

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

Answer 3

在前奏中的++似乎是直接和非尾递归...所以只是与此，它应该碰到堆栈溢出，对吗？

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