爲什麼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中的尾遞歸更好，因爲非尾遞歸的東西可能是懶惰的。您列出的定義比尾遞歸更好，因爲即使您只需要第一個元素，尾遞歸也會繼續遞歸併生成整個列表;而一個非尾遞歸的人只需要做盡可能多的工作。