Haskell中的State Monad用于跟踪二维运动

Question

我正在尝试跟踪一个物体在二维平面上的移动，该物体已经被给定了一系列指令：“前进”，“左转”或“右转”。

到目前为止，我已经编写了函数，可以接收物体状态的各个组件（方向、位置和移动），并在所有移动完成或沿途通过所有位置后返回最终状态。

物体的状态采用以下形式：Sstate (Dir dx dy) (Pos px py) [m]，其中移动由递归应用移动列表的头部来生成新状态

例如：Sstate (Dir 1 0) (Pos 0 0) "fff" -> Sstate (Dir 1 0) (Pos 0 1) "ff"

type Mov = Char

data Pos = Pos Int Int
 deriving (Show, Eq)

data Dir = Dir Int Int
 deriving (Show, Eq)

data Sstate = Sstate Dir Pos [Mov]
 deriving (Show, Eq)

move :: Sstate -> Sstate
move (Sstate (Dir dx dy) (Pos px py) []    )  = Sstate  (Dir dx dy) (Pos px py) []
move (Sstate (Dir dx dy) (Pos px py) (m:ms))
 | m == 'f'  = ss dx    dy    (dx + px) (dy + py) ms
 | m == 'l'  = ss (-dy) dx    px        py        ms
 | m == 'r'  = ss dy    (-dx) px        py        ms
 | otherwise = ss dy    dx    px        py        []
 where
   ss a b c d = Sstate (Dir a b) (Pos c d)

end :: Dir -> Pos -> [Mov] -> Sstate
end d p ms = iterate move initialState !! n
 where
   initialState = Sstate d p ms
   n = length ms + 1

position :: Sstate -> Pos
position (Sstate _ p _) = p

route :: Dir -> Pos -> [Mov] -> [Pos]
route d p ms = map position . take n . iterate  move $ initialState
 where
   initialState = Sstate d p ms
   n = length ms + 1

提供

λ: let x = Sstate (Dir 0 1) (Pos 0 2) "ff"

λ: move x
Sstate (Dir 0 1) (Pos 0 3) "f"

λ: end (Dir 0 1) (Pos 0 2) "ff"
Sstate (Dir 0 1) (Pos 0 4) ""

λ: route (Dir 0 1) (Pos 0 2) "ff"
[Pos 0 2,Pos 0 3,Pos 0 4]

这似乎可行，但它也似乎是在请求使用"State monad"。我发现"State monad"很令人困惑，但觉得如果有人能友善地展示在这里如何使用它，那将有助于我的理解。

- matt

---

阅读这份教程，其中包括一些单子，包括State单子。 - Bakuriu

我发现状态单子让人困惑的地方在于，状态本身并不是单子。一个 xmonad 是一个修改状态并返回值的函数：s -> (a, s)。 - mb14

@mb14 了解它的一种方式是，状态既是一个附加参数，也是一个附加返回值；类型为 a -> b 的函数变成了类型为 a -> s -> (b, s) 的函数。柯里化让你把它看作是接受类型为 a 的值并返回一个新函数，当给定状态时，可以返回类型为 b 和新状态的值 (a -> (s -> (b, s)))。通过 >>= 运算符，单子就是让你链接这样的函数。最终，你会得到一个类型为 s -> (t, s) 的函数，它将初始状态转换为类型为 t 的值。 - chepner

这并不相关，但我建议使用类似于 data Mov = Fwd | Lft | Rght | ... deriving (Eq, Show) 这样的东西来代替将其作为 Char 的同义词。这将使得在使用 -Wall 或 -fwarn-incomplete-patterns 时更容易让 GHC 帮助你查看是否捕获了所有情况，并且通常会使你的意图更加清晰。 - dfeuer

Answer 1

请注意，这里不需要直接使用State单子，因为一旦您将视为对状态进行操作而不是状态的一部分，则可以使用foldl'和scanl'编写end和route。 对于Sstate，记录语法也是有帮助的。请保留HTML标记。

type Mov = Char
data Pos = Pos Int Int deriving (Show, Eq)
data Dir = Dir Int Int deriving (Show, Eq)
data Sstate = Sstate {direction :: Dir, position :: Pos} deriving (Show, Eq)

-- A helper to simplify move
changeDir :: Mov -> Dir -> Dir
changeDir 'l' (Dir x y) = Dir (-y) x
changeDir 'r' (Dir x y) = Dir y (-x)
changeDir m (Dir x y) = Dir y x

move :: Mov -> Sstate -> Sstate
move 'f' oldState@(Sstate (Dir dx dy) (Pos px py))  = oldState { position = Pos (dx + px) (dy + py) }
move  m  oldState@(Sstate dir _) = oldState { direction = changeDir m dir }

end :: [Mov] -> Sstate -> Sstate
end ms initialState = foldl' (flip move) initialState ms

route :: [Mov] -> Sstate -> [Pos]
route ms initialState = map position $ scanl' (flip move) initialState ms

那么你的示例将变成：

λ: let x = Sstate {direction = Dir 0 1, position = Pos 0 2}

λ: move 'f' x
Sstate {direction = Dir 0 1, position = Pos 0 3}

λ: end "ff" x
Sstate {direction = Dir 0 1, position = Pos 0 4}

λ: route "ff" x
[Pos 0 2,Pos 0 3,Pos 0 4]

我将把它留作练习（或交给比我更有知识和不那么懒惰的人）来适应。

move :: Mov -> Sstate -> Sstate
end :: [Mov] -> Sstate -> Sstate
route :: [Mov] -> Sstate -> [Pos]

to

move :: Mov -> State Sstate ()
-- or possibly move :: Mov -> State Sstate Sstate ?
-- Like I said, more knowledgeable than me
end :: [Mov] -> State Sstate Sstate
route :: [Mov] -> State Sstate [Pos]

- chepner

---

谢谢。真的很有帮助。看到由懂行的人进行代码重构真的对我的学习过程很有帮助。 - matt

具有讽刺意味的是，重构他人的起点是我进行大部分学习的方式。 - chepner

@chepner，对我来说，() 看起来最简单和最符合惯用法。 - dfeuer

Answer 2

这里是一些简单的“入门”代码，通过状态的重新表述扩展了您的模块。在调整它们时，您需要查看像LYAH章节这样的教程。我省略了签名，这会变得越来越复杂，但在ghci中查询类型将很有启发性。您需要添加。

import Control.Monad.State
import Control.Monad.Writer -- for the position-remembering example

接下来，只要使用您定义的move，所有以下内容都应该可以正常工作

step = do                        -- step the state once with your `move`,
 sstate <- get                   -- whatever the state is
 put (move sstate)
-- this little program could also be written: `modify move` which shows the
-- link between what you wrote and State a little more clearly

steps = do                       -- repeatedly apply `step` to the state
  Sstate _ _ ls <- get           -- til there are no moves, then stop
  if null ls 
  then return ()       -- could be: unless (null ls) $ do step ; steps
  else step >> steps

stepsIO = do                     -- do all steps as with `steps`, but print
  sstate@(Sstate a b ls) <- get  -- the current state at each state update
  liftIO $ print sstate
  if null ls then liftIO (putStrLn "Done!")
             else step >> stepsIO

stepsPrintPosition = do           -- do all steps as with `steps`, printing 
  Sstate _ b ls <- get            -- only position at each state update
  liftIO $ do putStr "current position: " 
              print b
  if null ls then liftIO (putStrLn "Done!")
             else do step 
                     stepsPrintPosition  

stepsAccumulatePositions = do    -- move through all states as with `steps`
  sstate@(Sstate a b ls) <- get  -- but use `tell` to keep adding the current
  tell [b]                       -- position to the underlying list 
  if null ls then return ()      -- of positions 
             else step >> stepsAccumulatePositions

example = Sstate (Dir 0 1) (Pos 0 2) "ffff"

要使用像step、steps、stepsIO等工具，我们需要应用runState；这将给我们一个从状态到新状态的函数。

runStateT :: StateT s m a -> s -> m (a, s)

这当然只是新类型定义的访问器。

newtype StateT s m a  = StateT {runStateT :: s -> m (a, s)}

使用包装可以让我们编写复杂的 s -> m (a, s) 代码，但在新类型下，我们始终只是在 do 表达式中编写一个函数 s -> m (a, s)。

当然，一旦我们使用 runStateT 解除包装并获得函数 s -> m (a, s)，我们需要提供它一个初始状态。最简单的方法是在 ghci 中进行测试以了解其工作原理。

>>> example
Sstate (Dir 0 1) (Pos 0 2) "ffff"

>>> runStateT step example            -- we step the state once with move
((),Sstate (Dir 0 1) (Pos 0 3) "fff")

>>> runStateT steps example           -- we keep stepping till there are no moves
((),Sstate (Dir 0 1) (Pos 0 6) "")

>>> runStateT stepsIO example         -- we print state at each state update
Sstate (Dir 0 1) (Pos 0 2) "ffff"
Sstate (Dir 0 1) (Pos 0 3) "fff"
Sstate (Dir 0 1) (Pos 0 4) "ff"
Sstate (Dir 0 1) (Pos 0 5) "f"
Sstate (Dir 0 1) (Pos 0 6) ""
Done!
((),Sstate (Dir 0 1) (Pos 0 6) "")

>>> runStateT stepsPrintPosition  example   -- print position only at state updates
current position: Pos 0 2
current position: Pos 0 3
current position: Pos 0 4
current position: Pos 0 5
current position: Pos 0 6
Done!
((),Sstate (Dir 0 1) (Pos 0 6) "") 


-- the WriterT examples accumulate a 'monoid' of things you keep
-- adding to with `tell xyz` Here we accumulate a [Position]
-- execXYZ and evalXYZ, where they exist, return less information than runXYZ

>>>  runWriterT $ runStateT stepsAccumulatePositions   example
(((),Sstate (Dir 0 1) (Pos 0 6) ""),[Pos 0 2,Pos 0 3,Pos 0 4,Pos 0 5,Pos 0 6])

>>>  execWriterT $ evalStateT stepsAccumulatePositions   example
[Pos 0 2,Pos 0 3,Pos 0 4,Pos 0 5,Pos 0 6]

在上面的代码中，我使用了mtl类型类，然后使用runStateT和runWriterT来“解释”或专门处理涉及签名的类。这些与在Control.Monad.Trans.{State/Writer}中定义的具体类型StateT和WriterT相关。可以省略这些类，并直接使用这些具体类型，在导入这些模块时。唯一的区别是，在将两种效果（状态和写入或其他你想称之为的东西）组合起来的一个案例中，您需要执行lift $ tell [b]。关于您正在处理的状态分析，有很多内容可以讲述，但如果您仔细思考上述内容，就会发现如何重新设计它。

- Michael