我正在使用状态转换器在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)并求和所有结果，包括State monad列表之一的值：st读取和提高其状态的非平凡变压器或平凡变压器unst。有趣的是该算法是否探索了st和的开头unst。
在给出的代码中，它抛出undefined。我将其归结为链接转换顺序的错误设计，尤其是状态处理方面的问题，因为使用unst替代项（即将结果与状态转换解耦）确实会产生结果。但是，我然后发现，即使使用状态转换器，一维递归也保留了惰性（删除宽度步骤b <- walk...并将liftM2块换成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的选择和步行路线的尺寸会影响其成功，因此我不能广泛地说，sequence进行转换本身就是严格性的来源。
是什么在这里导致1D和2D递归的严格性上的差异，以及如何实现我想要的懒惰？
考虑下面的简化示例：
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
在这里，在一维和二维计算两者的结果的头明确只取决于输入（只头head a的维和行动都head a和head b为2D动作）。然而，在2D计算，有一个隐含的依赖关系b（甚至只是它的头）当前状态，而且状态取决于评价整体的a，不只是它的头。
在示例中，您也有类似的依赖关系，尽管它被状态操作列表所掩盖。
假设我们要walk22_head = head $ walk 2 2手动运行操作并检查结果列表中的第一个整数：
main = print $ head $ evalState walk22_head
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 2and的每一个中walk 2 1，head动作都是一系列动作，从调用的动作开始，到walk11_head基于的动作继续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。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句