CODEWITHSUNDEEP
haskellmonadslazy-evaluationmonad-transformers
mcmayer
mcmayer

Reputation: 2023

Haskell: Replace mapM in a monad transformer stack to achieve lazy evaluation (no space leaks)

It has already been discussed that mapM is inherently not lazy, e.g. here and here. Now I'm struggling with a variation of this problem where the mapM in question is deep inside a monad transformer stack.

Here's a function taken from a concrete, working (but space-leaking) example using LevelDB that I put on gist.github.com:

-- read keys [1..n] from db at DirName and check that the values are correct
doRead :: FilePath -> Int -> IO ()
doRead dirName n = do
    success <- runResourceT $ do
        db <- open dirName defaultOptions{ cacheSize= 2048 }
        let check' = check db def in        -- is an Int -> ResourceT IO Bool
            and <$> mapM check' [1..n]      -- space leak !!!
    putStrLn $ if success then "OK" else "Fail"

This function reads the values corresponding to keys [1..n] and checks that they are all correct. The troublesome line inside the ResourceT IO a monad is

and <$> mapM check' [1..n]

One solution would be to use streaming libraries such as pipes, conduit, etc. But these seem rather heavy and I'm not at all sure how to use them in this situation.

Another path I looked into is ListT as suggested here. But the type signatures of ListT.fromFoldable :: [Bool]->ListT Bool and ListT.fold :: (r -> a -> m r) -> r -> t m a -> mr (where m=IO and a,r=Bool) do not match the problem at hand.

What is a 'nice' way to get rid of the space leak?

Update: Note that this problem has nothing to do with monad transformer stacks! Here's a summary of the proposed solutions:

1) Using Streaming:

import Streaming
import qualified Streaming.Prelude as S
S.all_ id (S.mapM check' (S.each [1..n]))

2) Using Control.Monad.foldM:

foldM (\a i-> do {b<-check' i; return $! a && b}) True [1..n]

3) Using Control.Monad.Loops.allM

allM check' [1..n]

Upvotes: 1

Views: 263

Answers (2)

David Fletcher
David Fletcher

Reputation: 2818

I think what you need is allM from the monad-loops package.

Then it would be just allM check' [1..n]

(Or if you don't want the import it's a pretty small function to copy.)

Upvotes: 3

danidiaz
danidiaz

Reputation: 27771

I know you mention you don't want to use streaming libraries, but your problem seems pretty easy to solve with streaming without changing the code too much.

import Streaming
import qualified Streaming.Prelude as S

We use each [1..n] instead of [1..n] to get a stream of elements:

each :: (Monad m, Foldable f) => f a -> Stream (Of a) m ()

Stream the elements of a pure, foldable container.

(We could also write something like S.take n $ S.enumFrom 1).

We use S.mapM check' instead of mapM check':

mapM :: Monad m => (a -> m b) -> Stream (Of a) m r -> Stream (Of b) m r

Replace each element of a stream with the result of a monadic action

And then we fold the stream of booleans with S.all_ id:

all_ :: Monad m => (a -> Bool) -> Stream (Of a) m r -> m Bool

Putting it all together:

S.all_ id (S.mapM check' (S.each [1..n]))

Not too different from the code you started with, and without the need for any new operator.

Upvotes: 5

Related Questions