Haskell:替换monad变压器堆栈中的mapM以实现惰性评估(无空间泄漏) [英] Haskell: Replace mapM in a monad transformer stack to achieve lazy evaluation (no space leaks)

问题描述

已经讨论过 mapM 本质上不是惰性的，例如此处和

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.

这是一个使用LevelDB从具体的，有效的(但占用空间)的示例中提取的函数，我在其中输入了 gist.github.com :

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"

此函数读取与键 [1..n] 相对应的值，并检查它们是否正确. ResourceT IO a monad内的麻烦行是

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]

一种解决方案是使用流媒体库，例如 pipes ， conduit 等.但是这些看起来很繁重，我也不知道如何使用它们.在这种情况下.

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.

我研究过的另一条路径是 ListT ，如此处.但是 ListT.fromFoldable :: [Bool]-> ListT Bool 和 ListT.fold ::(r-> a-> m r)->的类型签名；r->t m a->mr (其中 m = IO 和 a ， r = Bool )与当前问题不符.

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?

更新:请注意，此问题与monad变压器堆栈无关！以下是建议的解决方案的摘要:

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

1)使用流式传输:

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

2)使用 Control.Monad.foldM :

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

3)使用 Control.Monad.Loops.allM

allM check' [1..n]

推荐答案

我知道您提到您不想使用流媒体库，但是使用

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

我们使用每个[1..n] 而不是 [1..n] 来获取元素流:

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.

(我们也可以编写类似 S.take n $ S.enumFrom 1 的东西).

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

我们使用 S.mapM check' 代替 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

然后，我们用 S.all_ id :

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

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

将它们放在一起:

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.

这篇关于Haskell:替换monad变压器堆栈中的mapM以实现惰性评估(无空间泄漏)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！