Is it possible to have a state-either hybrid monad?

Question

Goal

I'm trying to write the internals of an interpreter, and, for ergonomics purposes, I think I want to have a monad that works like both the state and either monads.

For example, I'd like to do some things with either style:

checkedAddress :: Integer -> Interpreter Int
checkedAddress n = if (n < toInteger (minBound :: Int))
                      then fail $ "Address " ++ show n ++ " is too low"
                   else if (n > toInteger (maxBound :: Int))
                      then fail $ "Address " ++ show n ++ " is too high"
                   else return $ fromInteger n

I'd like to do other things with state style:

setInstructionPointer :: Int -> Interpreter ()
setInstructionPointer ip (Machine _ mem) = ((), Machine ip mem)

getInstructionPointer :: Interpreter Int
getInstructionPointer m@(Machine ip mem) = (ip, m)

Questions

Is it possible to create a state-either hybrid monad like this?

If it's impossible, why is it impossible? Is there an alternative that has the nice ergonomics and, I assume, efficiency of early termination of (like either stops further processing through Left m >>= _ = Left m) this approach?

If it's possible, how do I write the monad instance for the type? I tried, but I got stuck when writing (>>=) because I can't see a way to know what constructor to produce without knowing the runtime Machine value.

data Interpreter a = Running      (Machine -> (a, Machine))
                   | Halted       (Machine -> Machine)
                   | Error String (Machine -> Machine)

instance Monad Interpreter where
  return = Running . (,)
  Running f     >>= g = DontKnowWhich $ \ m -> let (a, m') = f m
                                               in  case g a of
                                                        Running h ->
                                                        Halted  h ->
                                                        Error s h ->
  h@(Halted  _) >>= _ = h
  e@(Error _ _) >>= _ = e

Answer 1

The combined monad should look like this:

newtype Interpreter a
  = Interpreter { runInterpreter :: Machine -> (Machine, Either String a) }

It takes a state, the Machine, returns a modified state, and returns either success or failure.

deriving instance Functor Interpreter
instance Monad Interpreter where
    return x = _exercise
    Interpreter x >>= f = _exercise
instance Applicative Interpreter where pure = return; (<*>) = ap
liftEither :: Either String a -> Interpreter a
liftState :: State Machine a -> Interpreter a

In general, to put monads together, you put one "inside" the other:

Interpreter a <~> State Machine (Either String a)

You could do it another way, s -> Either String (s, a), but then you don't get the state back on error. (Note that Either String (State Machine a) does not work: whether or not you fail would not be allowed to depend on the state. It's only an Applicative.)

You do not have to write the Monad Interpreter instance yourself. The transformers package (shipped with GHC) provides "monad transformers" for constructing monads compositionally. A monad transformer is a T :: (Type -> Type) -> (Type -> Type) that takes a monad as argument and returns a new monad.

type Interpreter = ExceptT String (State Machine)
liftEither = except
liftState = lift

ExceptT String is a monad transformer, and State Machine is a monad, so Interpreter = ExceptT String (State Machine) is also a monad. The other way I mentioned before would be StateT Machine (Either String).

The next step is to use the mtl. This library provides classes on top of the transformer types such that monad-specific actions like throwError and get are overloaded to automatically lift themselves through as many monad transformers as needed. With the mtl, you can leave your own functions polymorphic in the monad stack:

checkedAddress :: MonadExcept String m => Integer -> m Int
checkedAddress n = do
  -- you don't need to branch, failure short-circuits!
  when (n < toInteger (minBound :: Int)) $ throwError _
  when (n > toInteger (maxBound :: Int)) $ throwError _
  pure (fromInteger n)

setInstructionPointer :: MonadState Machine m => Int -> m ()
setInstructionPointer ip = modify \(Machine _ mem) -> (Machine ip mem)

getInstructionPointer :: MonadState Machine m => m Int
getInstructionPointer = gets \(Machine i _) -> i

-- combined:
checkedOffsetJump :: (MonadState Machine m, MonadExcept String m) => Integer -> m ()
checkedOffsetJump off = setInstructionPointer =<< checkedAddress =<< (off +) <$> toInteger <$> getInstructionPointer
-- read: setInstructionPointer(checkedAddress(off + toInteger(getInstructionPointer())))

And you can nail them down later, usually at the very end:

runState $ runExceptT $ checkedOffsetJump 0x8000 :: Machine -> (Either String (), Machine)