爲什麼簡單使用State monad導致堆棧溢出？

Question

我當時玩的是國家monad，我不知道是什麼導致堆棧溢出在這段簡單的代碼中。

import Control.Monad.State.Lazy 

tick :: State Int Int 
tick = do n <- get 
     put $! (n+1) 
     return n 

million :: Int 
million = snd $ runState (mapM_ (const tick) [1..1000000]) 0 

main = print million 

注意 我只是想知道是什麼引起的問題在這一段代碼，任務本身並不重要本身。

Answer 1

問題是，Control.Monad.State.Lazy（>> =）是如此懶惰，即使（$！）也沒有幫助你。
嘗試Control.Monad.State.Strict，應達到（$！）。

懶惰狀態monad的（>> =）在（值，狀態）對上沒有看到全部，所以在達到結束之前完成一些評估的唯一方法是讓f在m >>= f解構這一對。這在這裏沒有發生，所以你會得到一個巨大的thunk，當runState最終需要結果時，這對於堆棧來說太大了。

好吧，我吃過了，現在我可以詳細說明了。讓我使用懶惰State s單元的舊（mtl-1.x）定義，在沒有內部monad的情況下看到它更容易一些。新的（mtl-2.x）定義type State s = StateT s Identity表現相同，只是更多的書寫和閱讀。的（>> =）的定義是

m >>= k = State $ \s -> let 
    (a, s') = runState m s 
    in runState (k a) s' 

現在，let綁定懶惰，因此這是

m >>= k = State $ \s -> let 
    blob = runState m s 
    in runState (k $ fst blob) (snd blob) 

僅更具有可讀性。所以（>> =）讓blob完全沒有評價。如果k需要檢查fst blob以確定如何繼續，或者k a需要檢查snd blob，則僅需要評估。 （>>），因此（>> =）的定義中的k爲const tick。（>> =）的定義爲。作爲一個常數函數，它絕對不需要檢查它的參數。所以tick >> tick成爲

State $ \s -> 
    let blob1 = (\n -> let n' = n+1 in seq n' ((),n')) s 
     blob2 = (\m -> let m' = m+1 in seq m' ((),m')) (snd blob1) 
    in blob2 

的seq沒有被觸及，直到blobN必須進行評估。但是需要評估它到最外層的構造函數 - 配對構造函數(,) - 足以觸發seq，並且這將導致在這裏完成評估。現在，在million中，在達到runState之後的最終snd之前，不需要任何評估。到那時，已經建成了一個擁有一百萬層的thunk。評估該thunk需要推動堆棧上的許多let m' = m+1 in seq m' ((),m')，直到達到初始狀態，並且如果堆棧足夠大以容納它們，則會彈出並應用它們。所以這將是三次遍歷，1.建立thunk，2.從thunk中剝離層並將它們推入堆棧，3.消耗堆棧。

Control.Monad.State.Strict的（>> =）嚴格得足以在每個綁定上強制seq，因此只有一次遍歷，沒有（非平凡）thunk被創建，並且計算運行時間不變空間。 定義是

m >>= k = State $ \s -> 
    case runState m s of 
     (a, s') -> runState (k a) s' 

最重要的區別是，圖案case表達式匹配的是嚴格的，這裏的blob必須進行評估，以最外面的構造函數來匹配它在case格局。
隨着m = tick = State (\m -> let m' = m+1 in seq m' ((),m'))主要部分變得

case let s' = s+1 in seq s' ((),s') of 
    (a, s'') -> runState (k a) s'' 

的模式匹配要求的((), s')評價[到（，）構造]，由該被綁定到的s' = s+1評價的seq，一切都完全評估上每個綁定，沒有thunk，沒有堆棧。

但是，您仍然需要小心。在這種情況下，由於seq（分別爲($!)）和相關類型的淺層結構，評估與應用(>>)保持一致。一般來說，對於更深層次的結構類型和/或沒有seq s，C.M.S.Strict也會構建可能會導致堆棧溢出的大型thunk。在這些情況下，thunk只是比C.M.S.Lazy所產生的更簡單和更少糾纏。

另一方面，C.M.S.Lazy的懶惰允許其他計算在C.M.S.Strict中是不可能的。例如，C.M.S.Lazy提供了極少數單子之一，其中

take 100 <$> mapM_ something [1 .. ] 

終止。 [但請注意，國家是無法使用的;在它可以被使用之前，它將不得不遍歷整個無限列表。所以，如果你這樣做，在恢復狀態依賴計算之前，你必須將put作爲一個新的狀態。]