Haskell State monad跟踪2维运动

Question

我试图在2D平面上跟踪对象的移动,该平面已被给出"向前,向左或向右"命令列表.

到目前为止,我有一些函数可以接收对象状态的组件(方向,位置和移动),并在完成所有移动或沿途传递所有位置后返回最终状态.

对象的状态是在形式中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令人困惑但觉得如果有人愿意展示如何在这里使用它,这将有助于我的理解.

Answer 1

这是一些简单的“入门”代码，通过在状态方面进行一些重新表述来扩展您的模块。我想，在摆弄它们的同时，你需要看看像 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)函数。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来“解释”或专门化涉及签名的类。这些属于具体类型StateT，并WriterT在 One 中定义Control.Monad.Trans.{State/Writer}，可以省略这些类，只需直接使用这些具体类型编写，导入这些模块。唯一的区别是，您需要lift $ tell [b]在一种情况下执行操作，即我将两种效果（状态和书写或任何您想要的名称）组合在一起。

关于你正在处理的状态分析有很多话要说，但如果你仔细考虑上述内容，你就会明白如何重新处理它。