定数空間のMonadic Fold

Question

定数空間でのモナドアクションを使用してレイジーリストを折り畳むにはどうすればよいですか？私が解決しようとしている問題は、大きなファイルを集約することです。パフォーマンスのために私は変更可能性が必要だと考えています。私は変更可能なベクトルを使用してSTで動作する実装を持っていますが、あまりにも多くのメモリを使います。以下は、私が試みていることの例です。私もコンジットで簡単に実験しましたが、改善は見られませんでした。

ST forM_：

import Control.Monad (forM_) 
import Control.Monad.ST.Trans as STT 
import Control.Monad.Identity as Identity 

testST :: Int 
testST = do 
    Identity.runIdentity $ STT.runST $ do 
    a <- STT.newSTRef 0 
    forM_ [1..10000000] (\x -> do 
     a' <- STT.readSTRef a 
     STT.writeSTRef a (a' + x) 
    ) 
    STT.readSTRef a 

コンジット：

import Data.Conduit (($=),(=$),($$)) 
import qualified Data.Conduit as C 
import qualified Data.Conduit.List as CL 

testCL :: IO Int 
testCL = CL.sourceList [1..10000000] $$ CL.foldM (\a x -> return (a + x)) 0 

Answer 1

問題は倍ではなく、倍体ではありません。このプログラムは、多くの割り当て：

testST = runST $ do 
    ref <- newSTRef 0 
    forM_ [1..10000000] $ \x -> do 
     val <- readSTRef ref 
     writeSTRef ref $! val + x 
    readSTRef ref 

コードの2枚の違いは何に良いヒントがある：

testST = runST $ do 
    ref <- newSTRef 0 
    forM_ [1..10000000] $ \x -> do 
     val <- readSTRef ref 
     writeSTRef ref (val + x) 
    readSTRef ref 

このプログラム、その唯一の違いwriteSTRefライン上にあるが、ほとんど何も割り当てません進んでいる：前者では、+の10000000層のアプリケーションを持つ深くネストされたサンクへの参照を作成しています。後者は各ステップでサンクを平らにする。

ところで、この共通の落とし穴はexplicitly called out in the documentation for modifySTRefです。