Haskell中的懶惰和尾遞歸，爲什麼會崩潰？

Question

我有這個相當簡單的函數來計算一個大名單的元素的平均值，使用兩個蓄能器至今持有的總和，到目前爲止計數：

mean = go 0 0 
    where 
     go s l []  = s/fromIntegral l 
     go s l (x:xs) = go (s+x) (l+1) xs 

main = do 
    putStrLn (show (mean [0..10000000])) 

現在，在嚴格的語言，這將是尾遞歸的，並且沒有問題。然而，由於Haskell是懶惰的，我的谷歌搜索讓我明白，（s + x）和（l + 1）將作爲thunk傳遞給遞歸。所以這整個事情的崩潰和燒傷：

Stack space overflow: current size 8388608 bytes. 

進一步谷歌搜索後，我發現seq和$!。這似乎是我不明白的，因爲我在這方面的所有嘗試都是徒勞的，錯誤信息是關於無限類型的。

終於讓我找到-XBangPatterns，解決了這一切改變的遞歸調用：

go !s !l (x:xs) = go (s+x) (l+1) xs 

但我不是很滿意這一點，因爲-XBangPatterns當前的延伸。我想知道如何在不使用-XBangPatterns的情況下進行嚴格的評估。 （！也許學的東西太多）

只要你明白我缺乏瞭解，這裏是我試了一下（唯一嘗試編譯，這是）：

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs 

從我能理解，以次應該在這裏強制評估s和l的論點，從而避免thunk造成的問題。但是我仍然遇到堆棧溢出。

Answer 1

我已經對這個擁有廣泛的著述：

• Real World Haskell, ch 24: controlling evaluation
• On recursion and strictness in Haskell

首先，是的，如果你想需要嚴格評估的蓄電池使用seq並留在Haskell 98 ：

mean = go 0 0 
    where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = s `seq` l `seq` 
         go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

*Main> main 
5000000.0 

其次：如果你給某些類型的註釋嚴格分析會踢，並與-O2編譯：

mean :: [Double] -> Double 
mean = go 0 0 
where 
    go :: Double -> Int -> [Double] -> Double 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

$ ghc -O2 --make A.hs 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.0 
./A 0.46s user 0.01s system 99% cpu 0.470 total 

由於「雙師型」是在嚴格的原子類型雙＃的包裝，對優化和精確類型，GHC運行嚴格性分析並推斷嚴格版本可以。

import Data.Array.Vector 

main = print (mean (enumFromToFracU 1 10000000)) 

data Pair = Pair !Int !Double 

mean :: UArr Double -> Double 
mean xs = s/fromIntegral n 
    where 
    Pair n s  = foldlU k (Pair 0 0) xs 
    k (Pair n s) x = Pair (n+1) (s+x) 

$ ghc -O2 --make A.hs -funbox-strict-fields 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.5 
./A 0.03s user 0.00s system 96% cpu 0.038 total 

正如上述RWH章節所述。

Answer 2

根據您的理解，seq s (s+x)強制s的評估是正確的。但它不強制s+x，因此你仍然在構建thunk。

通過使用$!您可以強制添加的評估（兩次，對於兩個參數）。這實現了相同的效果使用爆炸的模式：

mean = go 0 0 
where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = ((go $! s+x) $! l+1) xs 

---

使用該$!函數將轉化的go $! (s+x)到相當於：

let y = s+x 
in seq y (go y) 

因此y首先被迫進入弱頭正常形式，這意味着最外面的函數被應用。在y的情況下，最外面的函數是+，因此y在被傳遞到go之前被完全評估爲數字。

---

噢，你可能得到了無限類型的錯誤信息，因爲你沒有在正確的地方使用括號。我得到了同樣的錯誤，當我第一次寫程序下來:-)

因爲$!運算符是右結合的，沒有括號go $! (s+x) $! (l+1)手段一樣：go $! ((s+x) $! (l+1))，這顯然是錯誤的。

Answer 3

seq函數在調用該函數後強制評估第一個參數。當您通過seq s (s+x)作爲參數時，seq函數是而不是立即調用，因爲不需要評估該參數的值。您希望在遞歸調用之前對seq進行求值，以便反過來可以強制對其參數進行求值。

通常這樣做此鏈接：

go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs 

這是seq s (seq l (go (s+x) (l+1) xs))句法的變化。這裏對seq的調用是表達式中最外面的函數調用。由於Haskell的懶惰，這使得它們首先被評估：seq被稱爲仍未評估的參數s和seq l (go (s+x) (l+1) xs)，評估參數被推遲到某個人實際嘗試訪問它們的值的點。

現在seq可以強制其第一個參數在返回表達式的其餘部分之前進行評估。那麼評估的下一步將是第二個seq。如果seq的調用被埋在某些參數的某處，它們可能不會長時間執行，從而破壞它們的用途。

隨着seq的位置改變，程序可以正常執行，而不會使用過多的內存。

該問題的另一個解決方案是簡單地在編譯程序時啓用GHC優化（-O或-O2）。優化器識別不必要的懶惰，並生成不分配不必要內存的代碼。