Haskell State Monad in Two Dimensional Motion Tracking

Question

I am trying to track the movement of an object on a 2D plane that has been given a list of commands "forward, left, or right."

So far, I have functions that take the state components of an object (direction, position, and movement) and return the final state after all moves are completed or all positions are passed along the path.

The state of the object is in the form Sstate (Dir dx dy) (Pos px py) [m] , and the movement consists of recursively applying the head of the movement list to create new states

ie 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 abcd = Sstate (Dir ab) (Pos cd) end :: Dir -> Pos -> [Mov] -> Sstate end dp ms = iterate move initialState !! n where initialState = Sstate dp ms n = length ms + 1 position :: Sstate -> Pos position (Sstate _ p _) = p route :: Dir -> Pos -> [Mov] -> [Pos] route dp ms = map position . take n . iterate move $ initialState where initialState = Sstate dp ms n = length ms + 1 

gives

 λ: 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] 

This seems to work, but it also seems to be what the State monad . I find State monad confusing, but I feel that it will help me understand if someone will be kind to show how this can be used here.

Answer 1

Here is a simple "starter" code that extends your module with some reformulations in terms of state. I think you will need to study a textbook, for example, the chapter LYAH, to mess with them. I omit signatures that are becoming more complex, but the type question in ghci will be instructive. You need to add

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

Then everything should work using the definition of 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 ab 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 ab 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" 

To use things like step , steps , stepsIO , etc., we use runState ; this gives us a function from state to new state

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

This, of course, is just an accessor for defining newtype

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

The wrapper allows us to write fantastic things s -> m (a, s) using the simpler bits s -> m (a, s) , but under the newtype contour its always just the function s -> m (a, s) , which we write in the notation do.

Of course, once we deploy using runStateT and have our function s -> m (a, s) , we must provide it with the initial state. The easiest way to see how this works is by testing in 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] 

In the above code, I use the mtl classes, and then use runStateT and runWriterT to interpret or specialize a class that includes signatures. They are specific types of StateT and WriterT defined in Control.Monad.Trans.{State/Writer} . You can omit classes and simply write directly with these specific types by importing these modules. The only difference would be that you need to do lift $ tell [b] in one case, when I combine two effects, state and recording, or whatever you want to name.

There are many words about the analysis of the state with which you are working, but it will appear how you can process it if you think that this happened.

Answer 2

Note that you do not need to use the State monad here, since end and route can be written using foldl' and scanl' after you consider Mov as something that works for the state, and not be part of the state. The syntax for Sstate also helps.

 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 xy) = Dir (-y) x changeDir 'r' (Dir xy) = Dir y (-x) changeDir m (Dir xy) = Dir yx 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 

Then your examples will become:

 λ: 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] 

I will leave this as an exercise (or to someone more knowledgeable and less lazy than me) to adapt

 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]