Как восстановить ленивую оценку списка, построенного в монадическом режиме, после переключения из State в StateT?

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.

1. Это правильно?

2. Могу ли я восстановить ленивую оценку списка, построенного в монадическом режиме, пока в соответствии с реализацией 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

, и оно ведет себя так же.

Проблема заключается в строгости монады ввода-вывода. Если вместо этого вы выполняете это вычисление в монаде Identity:

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, вам нужно это сделать явно с 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 []

Answer 2

Другой ответ К. А. Бура объясняет, почему State против StateT не является уместным фактором (IO есть), а также указывает, как ваш пример странно построен (в том смысле, что часть State(T) не является ' t фактически используется, поскольку каждое число использует новое состояние []). Но помимо этих моментов, я не уверен, что скажу «потерять ленивую оценку монадически сконструированного списка», потому что если мы понимаем что-то вроде «ленивая оценка = оценивается только при необходимости», то foo действительно нужно запустить для каждого элемента в списке ввода, чтобы выполнить все эффекты, поэтому ленивая оценка не теряется. Вы получаете то, что просили. (Так уж получилось, что foo не выполняет никаких операций ввода-вывода, и, возможно, кто-то другой может прокомментировать, если когда-нибудь возможно, чтобы компилятор / GH C оптимизировал его на этом основании, но вы можете легко понять, почему GH C делает здесь наивное дело.)

Это распространенная, хорошо известная проблема в Haskell. Существуют различные библиотеки (наиболее известные из которых streaming, pipes, conduit), которые решают проблему, предоставляя вам streams (в основном списки), которые ленивы в эффектах тоже. Если я воссоздаю ваш пример в потоковом стиле,

import Data.Function ((&))
import Control.Monad.State
import Streaming
import qualified Streaming.Prelude as S

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

nMax :: Int
nMax = 5000000

main :: IO ()
main = do
  mHead <- S.head_ $ S.each [0..nMax]
                   & S.mapM (flip runStateT [] . foo)
                   & S.dropWhile (not . fst)
  print $ snd <$> mHead

, тогда обе версии запускаются практически мгновенно. Чтобы сделать разницу более очевидной, представьте, что foo также называется print "hi". Тогда потоковая версия, ленивая в эффектах, будет печататься только дважды, тогда как ваши оригинальные версии будут печатать nMax раза. Поскольку они ленивы в эффектах, тогда весь список не нужно пересматривать, чтобы замкнуть накоротко и закончить sh рано.