haskell - 从 State 切换到 StateT 后，如何恢复单子(monad)构造列表的惰性求值？

Question

使用以下代码:

(lazy_test.hs)

-- Testing lazy evaluation of monadically constructed lists, using State.
import Control.Monad.State

nMax = 5

foo :: Int -> State [Int] Bool
foo n = do
  modify $ \st -> n : st
  return (n `mod` 2 == 1)

main :: IO ()
main = do
  let ress = for [0..nMax] $ \n -> runState (foo n) []
      sts  = map snd $ dropWhile (not . fst) ress
  print $ head sts

for = flip map

我可以将 nMax 设置为 5，即 50,000,000，并且获得大致相同的运行时间:

nMax = 5:

$ stack ghc lazy_test.hs
[1 of 1] Compiling Main             ( lazy_test.hs, lazy_test.o )
Linking lazy_test ...

$ time ./lazy_test
[1]

real    0m0.019s
user    0m0.002s
sys     0m0.006s

nMax = 50,000,000:

$ stack ghc lazy_test.hs
[1 of 1] Compiling Main             ( lazy_test.hs, lazy_test.o )
Linking lazy_test ...

$ time ./lazy_test
[1]

real    0m0.020s
user    0m0.002s
sys     0m0.005s

鉴于我对惰性评估机制的理解，这正如我所期望的。

但是，如果我从 State 切换到 StateT:

(lazy_test2.hs)

-- Testing lazy evaluation of monadically constructed lists, using StateT.
import Control.Monad.State

nMax = 5

foo :: Int -> StateT [Int] IO Bool
foo n = do
  modify $ \st -> n : st
  return (n `mod` 2 == 1)

main :: IO ()
main = do
  ress <- forM [0..nMax] $ \n -> runStateT (foo n) []
  let sts  = map snd $ dropWhile (not . fst) ress
  print $ head sts

for = flip map

然后我发现各自的运行时间之间存在巨大差异:

nMax = 5:

$ stack ghc lazy_test2.hs
[1 of 1] Compiling Main             ( lazy_test2.hs, lazy_test2.o )
Linking lazy_test2 ...

$ time ./lazy_test2 
[1]

real    0m0.019s
user    0m0.002s
sys     0m0.004s

nMax = 50,000,000:

$ stack ghc lazy_test2.hs
[1 of 1] Compiling Main             ( lazy_test2.hs, lazy_test2.o )
Linking lazy_test2 ...

$ time ./lazy_test2 
[1]

real    0m29.758s
user    0m25.488s
sys     0m4.231s

我假设这是因为当我切换到基于 StateT 的实现时，我失去了对单子(monad)构造的列表的惰性评估。

1. 正确吗？

2. 我可以恢复单子(monad)构造列表的惰性求值，同时保持基于 StateT 的实现吗？

Answer 1

在您的示例中，您只运行一个 foo行动每runState ，所以您使用 State和/或StateT本质上是无关的。您可以替换使用 foo与等效:

import Control.Monad

nMax = 50000000

main :: IO ()
main = do
  ress <- forM [0..nMax] $ \n -> return (n `mod` 2 == 1, [n])
  let sts  = map snd $ dropWhile (not . fst) ress
  print $ head sts

其行为方式相同。

问题在于 IO monad 的严格性。如果您在 Identity 中运行此计算改为单子(monad):

import Control.Monad
import Data.Functor.Identity

nMax = 50000000

main :: IO ()
main = do
  let ress = runIdentity $ forM [0..nMax] $ \n -> return (n `mod` 2 == 1, [n])
  let sts  = map snd $ dropWhile (not . fst) ress
  print $ head sts

然后它就会懒惰地运行。

如果你想在 IO monad 中延迟运行，你需要使用 unsafeInterleaveIO 显式地执行。 ，因此以下内容可以工作:

import System.IO.Unsafe
import Control.Monad

nMax = 50000000

main :: IO ()
main = do
  ress <- lazyForM [0..nMax] $ \n -> return (n `mod` 2 == 1, [n])
  let sts  = map snd $ dropWhile (not . fst) ress
  print $ head sts

lazyForM :: [a] -> (a -> IO b) -> IO [b]
lazyForM (x:xs) f = do
  y <- f x
  ys <- unsafeInterleaveIO (lazyForM xs f)
  return (y:ys)
lazyForM [] _ = return []