Государственная монада Haskell в отслеживании движения в двух измерениях
Я пытаюсь проследить за движением объекта в двухмерной плоскости, которому был дан список команд "вперед, влево или вправо".
До сих пор у меня есть функции, которые принимают компоненты состояния объекта (направление, положение и ходы) и возвращают конечное состояние после того, как все ходы завершены или все позиции пройдены по пути.
Состояние объекта в форме 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 сбиваю с толку, но чувствую, что это поможет мне понять, если кто-то будет достаточно любезен, чтобы показать, как это можно использовать здесь.
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) вещи, используя проще s -> m (a, s) биты, но под капотом нового типа, это всегда просто функция s -> m (a, s) мы пишем в нотации do.
Конечно, когда мы развернем 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 определяется в Control.Monad.Trans.{State/Writer} Можно было бы опустить классы и просто писать напрямую с этими конкретными типами, импортируя эти модули. Единственная разница будет в том, что вам нужно сделать lift $ tell [b] в одном случае, когда я комбинирую два эффекта, состояние и запись или как вы хотите это назвать.
Можно много чего сказать об анализе состояния, с которым вы работаете, но выяснится, как вы можете его переработать, если продумаете вышесказанное.
Обратите внимание, что вам не нужно напрямую использовать State Монада здесь, как end а также route может быть написано с использованием foldl' а также scanl' когда вы считаете Mov как то, что действует на государство, а не быть частью государства. Синтаксис записи для Sstate также помогает.
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]
в
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]