haskell - 惰性状态转换器在 2D 递归中急切地消耗惰性列表

Question

我正在使用状态转换器在 2D 递归游走的每个点对数据集进行随机采样，从而输出一个 2D 样本网格列表，这些样本一起满足一个条件。我想懒洋洋地从结果中提取，但我的方法反而在我提取第一个结果之前在每个点都耗尽了整个数据集。

具体来说，考虑这个程序:

import Control.Monad ( sequence, liftM2 )
import Data.Functor.Identity
import Control.Monad.State.Lazy ( StateT(..), State(..), runState )

walk :: Int -> Int -> [State Int [Int]]
walk _ 0 = [return [0]]
walk 0 _ = [return [0]]
walk x y =
  let st :: [State Int Int]
      st = [StateT (\s -> Identity (s, s + 1)), undefined]
      unst :: [State Int Int] -- degenerate state tf
      unst = [return 1, undefined]
  in map (\m_z -> do
      z <- m_z
      fmap concat $ sequence [
          liftM2 (zipWith (\x y -> x + y + z)) a b -- for 1D: map (+z) <$> a
          | a <- walk x (y - 1) -- depth
          , b <- walk (x - 1) y -- breadth -- comment out for 1D
        ]
    ) st -- vs. unst

main :: IO ()
main = do
  std <- getStdGen
  putStrLn $ show $ head $ fst $ (`runState` 0) $ head $ walk 2 2

程序从 (x, y) 开始遍历矩形网格。至 (0, 0)并对所有结果求和，包括状态单子(monad)列表之一的值:非平凡的转换器 st读取和推进他们的状态，或琐碎的变压器 unst .有趣的是该算法是否探索了 st 的头部。和 unst .

在呈现的代码中，它会抛出 undefined .我将此归结为我对链接转换顺序的错误设计，特别是状态处理的问题，如使用 unst相反(即从状态转换中分离结果)确实会产生结果。然而，我随后发现，即使使用状态转换器，一维递归也能保持惰性(删除宽度步长 b <- walk... 并将 liftM2 block 交换为 fmap )。

如果我们 trace (show (x, y)) ，我们还看到它在触发之前确实遍历了整个网格:

$ cabal run
Build profile: -w ghc-8.6.5 -O1
...
(2,2)
(2,1)
(1,2)
(1,1)
(1,1)
sandbox: Prelude.undefined

我怀疑我使用 sequence这里有错，但是由于 monad 的选择和 walk 的维度会影响其成功，我不能广泛地说 sequence转换本身就是严格性的来源。

是什么导致了 1D 和 2D 递归之间的严格性差异，我怎样才能实现我想要的惰性？

Answer 1

考虑以下简化示例:

import Control.Monad.State.Lazy

st :: [State Int Int]
st = [state (\s -> (s, s + 1)), undefined]

action1d = do
  a <- sequence st
  return $ map (2*) a

action2d = do
  a <- sequence st
  b <- sequence st
  return $ zipWith (+) a b

main :: IO ()
main = do
  print $ head $ evalState action1d 0
  print $ head $ evalState action2d 0

在这里，在 1D 和 2D 计算中，结果的头部显式地仅取决于输入的头部(对于 1D Action ，仅 head a，对于 2D Action ， head a 和 head b)。但是，在 2D 计算中，隐含的依赖关系为 b。 (甚至只是它的头部)当前状态，并且该状态取决于对 a 整体的评估，而不仅仅是它的头。

您的示例中有类似的依赖关系，尽管它被状态操作列表的使用所掩盖。

假设我们要运行操作 walk22_head = head $ walk 2 2手动检查结果列表中的第一个整数:

main = print $ head $ evalState walk22_head

写状态 Action 列表的元素 st明确:

st1, st2 :: State Int Int
st1 = state (\s -> (s, s+1))
st2 = undefined

我们可以写 walk22_head作为:

walk22_head = do
  z <- st1
  a <- walk21_head
  b <- walk12_head
  return $ zipWith (\x y -> x + y + z) a b

请注意，这仅取决于定义的状态操作 st1和 walk 2 1 的负责人和 walk 1 2 .反过来，这些头可以写成:

walk21_head = do
  z <- st1
  a <- return [0] -- walk20_head
  b <- walk11_head
  return $ zipWith (\x y -> x + y + z) a b

walk12_head = do
  z <- st1
  a <- walk11_head
  b <- return [0] -- walk02_head
  return $ zipWith (\x y -> x + y + z) a b

同样，这些仅取决于定义的状态操作 st1和 walk 1 1 的负责人.

现在，让我们试着写下 walk11_head 的定义。 :

walk11_head = do
  z <- st1
  a <- return [0]
  b <- return [0]
  return $ zipWith (\x y -> x + y + z) a b

这仅取决于定义的状态操作 st1 ，所以有了这些定义，如果我们运行 main ，我们得到一个明确的答案:

> main
10

但这些定义并不准确!在每个 walk 1 2和 walk 2 1 ，头部 Action 是一系列 Action ，从调用 walk11_head 的 Action 开始。 ，但继续基于 walk11_tail 的操作.因此，更准确的定义是:

walk21_head = do
  z <- st1
  a <- return [0] -- walk20_head
  b <- walk11_head
  _ <- walk11_tail  -- side effect of the sequennce
  return $ zipWith (\x y -> x + y + z) a b

walk12_head = do
  z <- st1
  a <- walk11_head
  b <- return [0] -- walk02_head
  _ <- walk11_tail  -- side effect of the sequence
  return $ zipWith (\x y -> x + y + z) a b

和:

walk11_tail = do
  z <- undefined
  a <- return [0]
  b <- return [0]
  return [zipWith (\x y -> x + y + z) a b]

有了这些定义，运行 walk12_head 就没有问题了。和 walk21_head隔离中:

> head $ evalState walk12_head 0
1
> head $ evalState walk21_head 0
1

这里的状态副作用不需要计算答案，因此从未调用过。但是，不可能同时运行它们:

> head $ evalState (walk12_head >> walk21_head) 0
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err
  undefined, called at Lazy2D_2.hs:41:8 in main:Main

因此，尝试运行 main由于同样的原因失败:

> main
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err
  undefined, called at Lazy2D_2.hs:41:8 in main:Main

因为，在计算 walk22_head , 甚至是 walk21_head 的开头的计算取决于状态副作用 walk11_tail由 walk12_head 发起.

您的原创 walk定义的行为方式与这些模型相同:

> head $ evalState (head $ walk 1 2) 0
1
> head $ evalState (head $ walk 2 1) 0
1
> head $ evalState (head (walk 1 2) >> head (walk 2 1)) 0
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err
  undefined, called at Lazy2D_0.hs:15:49 in main:Main
> head $ evalState (head (walk 2 2)) 0
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err
  undefined, called at Lazy2D_0.hs:15:49 in main:Main

很难说如何解决这个问题。您的玩具示例非常适合说明问题，但尚不清楚在您的“真实”问题中如何使用状态以及是否 head $ walk 2 1确实对 sequence 有状态依赖。的 walk 1 1 head $ walk 1 2 引起的 Action .