Monadic Fold in Constant Space

Question

Come posso piegare una lista pigra usando un'azione monadica nello spazio costante? Il problema che sto cercando di risolvere è l'aggregazione di un file di grandi dimensioni, e credo che per motivi di prestazioni richieda mutabilità. Ho un'implementazione che funziona in ST usando vettori mutabili, ma usa troppa memoria. Di seguito è riportato un esempio di ciò che sto tentando. Ho anche sperimentato brevemente con Conduit, ma questo non sembrava fornire alcun miglioramento.

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 

condotto:

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

Il problema non è con la piega, ma con il corpo piega. Questo programma alloca un sacco:

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

questo programma, la cui unica differenza è sulla linea writeSTRef, alloca quasi nulla:

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

La differenza tra i due pezzi di codice è un buon suggerimento per ciò che è continua: nel primo caso, si sta creando un riferimento a un thunk profondamente annidato con 10000000 strati di applicazioni di +; mentre quest'ultimo appiattisce il thunk ad ogni passo.

A proposito, questo errore comune è explicitly called out in the documentation for modifySTRef.