ST monad导致堆栈空间溢出 [英] Stack space overflow with the ST monad

问题描述

以下简短的Haskell程序旨在计算文件中的项目列表.使用foldl'的版本可以正常工作，但是使用ST Monad的版本会给出堆栈空间溢出消息.显然，这里存在某种形式的空间泄漏，但是我一直无法解决.真正有趣的部分是ST monad应该执行就地更新，并且不应让资源这样增长，尽管这可能仅与主内存有关，而与堆栈空间无关.有人可以解释这里发生了什么吗?

The following short Haskell program is intended to count a list of items from a file. The version using foldl' works fine, but the version using the ST Monad gives a stack space overflow message. Clearly there's a space leak of some sort here, but I haven't been able to solve it. The really interesting part is that the ST monad is supposed to be doing in-place updates and shouldn't be letting resources grow like this, although that may only pertain to main memory and not stack space. Could someone explain what's happening here?

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)))  

更新:感谢您的回答和评论.我想我知道这里发生了什么. ModifySTRef'是4.6版中的新功能，可以很好地解决该问题，并包含有人提到的解释.我正在使用Data.STRef的4.5版本，该版本在Ubuntu中似乎是标准的，并且既不包含解释也不包含ModifySTRef'.

UPDATE: Thanks for the answers and comments. I think I see what's happened here. modifySTRef' is new in version 4.6, which solves the problem nicely and includes the explanation someone mentioned. I'm using version 4.5 of Data.STRef, which appears to be standard in Ubuntu and includes neither the explanation or modifySTRef'.

查看4.6软件包版本和函数，不同之处在于它使用seq来确保函数f严格应用(并存储在x'中):

Looking into the 4.6 package version and the function, the difference is that it uses seq to insure the function f is applied strictly (and stored in 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应用于泄漏区域，这是我将来可能会使用的一个不错的通用技巧.感谢大家的帮助.

So another way to solve it would have been to copy the function's code to a new name in my own program's space and apply seq to the leaking area, which is a nice general-purpose trick I'll probably use in the future. Thanks to everyone for helping me sort this out.

推荐答案

这是 a经典的空间泄漏.

modifySTRef不会将其函数参数的应用结果强制施加到状态. 实际上，您无法编写其参数函数来确保严格性.

modifySTRef does not force the result of the application of its function argument to the state. In fact, there's no way you can write its argument function to ensure strictness.

请使用modifySTRef'.

这篇关于ST monad导致堆栈空间溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！