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

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?

CodePudding user response：

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