堆栈空间溢出与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

回答

相关问题