堆棧空間溢出與ST monad

以下簡短的Haskell程序旨在計算文件中的項目列表。使用foldl'的版本可以正常工作，但使用ST Monad的版本會提供堆棧空間溢出消息。很明顯，這裏有一些空間泄漏，但我一直無法解決它。真正有趣的部分是，ST monad應該是做就地更新，不應該讓資源像這樣增長，儘管這可能只涉及主內存而不是堆棧空間。有人能解釋這裏發生了什麼嗎？堆棧空間溢出與ST monad

import Control.Monad 
import Data.List 
import Control.Monad.ST 
import Data.STRef 

--count items using foldl' 
countFold :: Num a => [b] -> a 
countFold = foldl' (\a _ -> a+1) 0 

-- count items using the ST monad 
-- derived fromt the sumST example on http://www.haskell.org/haskellwiki/Monad/ST 
-- only using +1 instead of adding the values 
countST :: Num a => [b] -> a 
countST xs = runST $ do 

    n <- newSTRef 0 

    forM_ xs (\_ -> modifySTRef n (+1)) 

    readSTRef n 



main = do 

    mydata <- readFile "data_files/values_1000000.num" 
    let trainingdata = lines mydata 

    -- this works just fine 
    --(putStrLn (show (countFold trainingdata))) 

    -- This fails with the message: 
    -- Stack space overflow: current size 8388608 bytes. 
    -- Use `+RTS -Ksize -RTS' to increase it. 
    (putStrLn (show (countST trainingdata)))

UPDATE：感謝您的答案和評論。我想我知道這裏發生了什麼。 modifySTRef'在4.6版本中是新的，它很好地解決了這個問題，並且包含了某人提到的解釋。我使用的Data.STRef版本是4.5，它在Ubuntu中似乎是標準的，並且不包含說明或modifySTRef'。

展望4.6軟件包版本和功能，所不同的是，它使用SEQ以確保函數f嚴格應用（並存儲在X'）：

modifySTRef :: STRef s a -> (a -> a) -> ST s() 
modifySTRef ref f = writeSTRef ref . f =<< readSTRef ref 

modifySTRef' :: STRef s a -> (a -> a) -> ST s() 
modifySTRef' ref f = do 
    x <- readSTRef ref 
    let x' = f x 
    x' `seq` writeSTRef ref x'

所以另一種方式來解決這個問題本來應該在我自己的程序空間中將函數的代碼複製到一個新名稱中，然後將seq應用到泄漏區域，這是一個很好的通用技巧，我將來可能會使用它。感謝大家幫我解決這個問題。

來源

2013-02-25 user2106968

您應該閱讀[文檔]（http://hackage.haskell.org/packages/archive/base/latest/doc/html/Data-STRef.html）：「請注意'modifySTRef'不適用這意味着如果程序多次調用'modifySTRef'，但很少使用該值，那麼thunk會堆積在內存中，導致空間泄漏，這是使用'STRef'作爲計數器時常犯的錯誤。「還有一個例子看起來幾乎是你的'countST'函數的代碼，來說明這個錯誤。長話短說：使用'modifySTRef'' – 2013-02-25 11:27:30

這是a classic space leak。

modifySTRef不強制將其函數參數應用到狀態的結果。事實上，你不可能寫出它的參數函數來確保嚴格性。請使用modifySTRef'。

來源

2013-02-25 12:00:41

堆棧空間溢出與ST monad

回答

相關問題