Monadic Fold in Constant Space

Question

Как я могу сложить ленивый список, используя монадическое действие в постоянном пространстве? Проблема, которую я пытаюсь решить, заключается в агрегировании большого файла, и я считаю, что ради производительности мне нужна изменчивость. У меня есть реализация, работающая в ST с использованием изменяемых векторов, но она использует слишком много памяти. Ниже приведен пример того, что я пытаюсь сделать. Я также коротко экспериментировал с Conduit, но, похоже, это не улучшило.

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 

Эта программа, чья единственная разница находится на writeSTRef линии, не выделяет почти ничего:

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

Разница между этими двумя частями кода является хорошим намек на то, что Продолжайте: в первом вы создаете ссылку на глубоко вложенный кусок с 10000000 слоями приложений +; тогда как последний сглаживает удар на каждом шаге.

Кстати, эта общая ошибка составляет explicitly called out in the documentation for modifySTRef.