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) вещи, используя простой s -> m (a, s) бит, но под контуром newtype его всегда просто функция 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, определенным в Control.Monad.Trans.{State/Writer}. Можно опустить классы и просто писать напрямую с помощью конкретных типов, импортируя эти модули. Единственное различие заключается в том, что вам нужно сделать lift $ tell [b] в одном случае, когда я совмещаю два эффекта, состояние и запись или все, что вы хотите назвать.

Существует много можно сказать об анализе состояния вы работаете, но он появится, как вы могли бы переделать его, если вы думаете, что выше до конца.

Answer 2

Обратите внимание, что вы напрямую не нужно использовать 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]