Is the State monad applicable to a simple recursive "loop"?

Question

I'm learning Haskell from "LYAH" and got to the State monad. As an exercise I'm working on implementing a simple "virtual cpu". The state monad seems like a good fit for this but I can't figure out how to use it. Here's a very stripped down example of what I have at the moment (without the state monad):

data Instruction = Incr | Decr | Halt

data Computer = Computer { program :: [Instruction],
                           acc :: Int,
                           pc :: Int,
                           halted :: Bool
                         }

main = do
  let comp = Computer { program = [Incr, Decr, Incr, Incr, Halt]
                      , acc = 0
                      , pc = 0
                      , halted = False
                      }
  execute comp

execute :: Computer -> IO ()
execute comp = do
  let (output, comp') = step comp
  putStrLn output
  case halted comp' of
    False -> execute comp'
    True -> return ()

step :: Computer -> (String, Computer)
step comp = let inst = program comp !! pc comp
            in case inst of
                 Decr -> let comp' = comp{ acc = acc comp - 1,
                                           pc = pc comp + 1 }
                             output = "Increment:" ++
                                      "   A = " ++ (show $ acc comp') ++
                                      "  PC = " ++  (show $ pc comp')
                         in (output, comp')
                 Incr -> let comp' = comp{ acc = acc comp + 1,
                                           pc = pc comp + 1 }
                             output = "Decrement:" ++
                                      "   A = " ++ (show $ acc comp') ++
                                      "  PC = " ++  (show $ pc comp')
                         in (output, comp')
                 Halt -> let comp' = comp{halted = True}
                             output = "HALT"
                         in (output, comp')

My step function looks like the state monad but I can't see how to use it here. Would it be applicable? Would it simplify this code, or is this example better as it is?

Answer 1

Absolutely. step can be translated quite mechanically:

import Control.Monad.Trans.State

step :: State Computer String
step = do
   comp <- get
   case program comp !! pc comp of
    Decr -> do 
      let comp' = comp { acc = acc comp - 1
                       , pc = pc comp + 1 }
      put comp'
      return $ "Increment:"
                  ++ "   A = " ++ (show $ acc comp')
                  ++ "  PC = " ++  (show $ pc comp')
    Incr -> do
      let comp' = comp { acc = acc comp + 1
                       , pc = pc comp + 1 }
      put comp'
      return $ "Decrement:"
              ++ "   A = " ++ (show $ acc comp')
              ++ "  PC = " ++  (show $ pc comp')
    Halt -> do
      put $ comp{halted = True}
      return "HALT"

(These let comp' = ... are still a bit awkward. It could be made more imperative-like by using state field-modifiers from the lens library.)

You may notice that State is actually just a specialization of the StateT transformer, and none of the functions I used is specific to this. I.e. you can straight away generalize the signature to

step :: Monad m => StateT Computer m String

That turns out to come in handy for execute, because there you intersperse the state modifications with IO side effects – exactly the kind of thing a transformer is for.

import Control.Monad.IO.Class

execute :: StateT Computer IO ()
execute = do
  output <- step
  liftIO $ putStrLn output
  comp <- get
  case halted comp of
    False -> execute
    True -> return ()

Finally, in main you just need

main = do
  let comp = ...
  evalStatT execute comp