3

次の短い Haskell プログラムは、ファイルから項目のリストをカウントすることを目的としています。を使用foldl'したバージョンは問題なく動作しますが、 を使用したバージョンで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)))

更新:回答とコメントをありがとう。ここで何が起こったのかがわかったと思います。modifySTRef' はバージョン 4.6 の新機能で、問題をうまく解決し、誰かが言及した説明が含まれています。私はData.STRefのバージョン4.5を使用しています.

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 を適用することでした。これは、おそらく将来的に使用する優れた汎用トリックです。これを整理するのを手伝ってくれてありがとう。

4

1 に答える 1

8

これは古典的なスペースリークです。

modifySTRef関数の引数を状態に適用した結果を強制しません。実際、厳密性を保証するためにその引数関数を書く方法はありません。

をご利用くださいmodifySTRef'。

于 2013-02-25T12:00:41.250 に答える