是否有可能有一个 state-either 混合 monad？

Question

目标

我正在尝试编写解释器的内部结构，并且出于人体工程学的目的，我想我想要一个 monad 既可以像 state 一样工作，也可以像任何 monad 一样工作。

例如，我想用这两种风格做一些事情：

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

我想用状态风格做其他事情：

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

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

问题

是否有可能像这样创建一个 state-either 混合 monad？

如果不可能，为什么不可能？是否有一种替代方案具有良好的人体工程学，并且我假设Left m >>= _ = Left m这种方法的提前终止（例如通过 停止进一步处理）的效率？

如果可能，我如何为该类型编写 monad 实例？我试过了，但我在编写时卡住了，(>>=)因为在不知道运行Machine时值的情况下，我看不到知道要生成什么构造函数的方法。

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

组合的 monad 应该如下所示：

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

它接受一个状态 the Machine，返回一个修改后的状态，并返回成功或失败。

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

通常，要将 monad 放在一起，您需要将一个“放入”另一个：

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

你可以用另一种方式来做s -> Either String (s, a)，但是这样你就不会因为错误而恢复状态。（请注意，Either String (State Machine a)这不起作用：不允许您失败与否取决于状态。它只是一个Applicative.）

您不必Monad Interpreter自己编写实例。该transformers包（与 GHC 一起提供）提供了“monad 转换器”，用于组合构建 monad。monad 转换器是T :: (Type -> Type) -> (Type -> Type)将一个 monad 作为参数并返回一个新的 monad。

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

ExceptT String是一个 monad 转换器，并且State Machine是一个 monad，所以Interpreter = ExceptT String (State Machine)也是一个 monad。我之前提到的另一种方式是StateT Machine (Either String).

下一步是使用mtl. 这个库在transformer类型之上提供了类，这样 monad 特定的动作像throwError和get被重载以根据需要自动提升自己通过尽可能多的 monad 转换器。使用mtl，您可以在 monad 堆栈中保留自己的多态函数：

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())))

你可以稍后确定它们，通常是在最后：

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