haskell - 是否有可能有一个状态或混合单子(monad)？

Question

目标

我正在尝试编写解释器的内部结构，并且出于人体工程学的目的，我想我想要一个既像状态又像任一单子(monad)一样工作的单子(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)

问题

是否有可能像这样创建一个状态或混合单子(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) }

它需要一个状态，即机器，返回修改后的状态，并返回成功或失败。

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)放在一起，您可以将一个单子(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 = <a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Except.html#t:ExceptT" rel="noreferrer noopener nofollow">ExceptT</a> String (<a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-State-Lazy.html#t:State" rel="noreferrer noopener nofollow">State</a> Machine)
liftEither = <a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Except.html#v:except" rel="noreferrer noopener nofollow">except</a>
liftState = <a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Class.html#v:lift" rel="noreferrer noopener nofollow">lift</a>

ExceptT String 是一个 monad 转换器，而 State Machine 是一个 monad，因此 Interpreter = exceptT String (State Machine) 也是一个单子(monad)。我之前提到的另一种方式是 StateT Machine(任一字符串)。

下一步是使用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)) $ <a href="https://hackage.haskell.org/package/mtl-2.2.2/docs/Control-Monad-Except.html#v:throwError" rel="noreferrer noopener nofollow">throwError</a> _
  when (n > toInteger (maxBound :: Int)) $ throwError _
  pure (fromInteger n)

setInstructionPointer :: MonadState Machine m => Int -> m ()
setInstructionPointer ip = <a href="https://hackage.haskell.org/package/mtl-2.2.2/docs/Control-Monad-State-Lazy.html#v:modify" rel="noreferrer noopener nofollow">modify</a> \(Machine _ mem) -> (Machine ip mem)

getInstructionPointer :: MonadState Machine m => m Int
getInstructionPointer = <a href="https://hackage.haskell.org/package/mtl-2.2.2/docs/Control-Monad-State-Lazy.html#v:gets" rel="noreferrer noopener nofollow">gets</a> \(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())))

您可以稍后将它们确定下来，通常是在最后:

<a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-State-Lazy.html#v:runState" rel="noreferrer noopener nofollow">runState</a> $ <a href="https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Except.html#v:runExceptT" rel="noreferrer noopener nofollow">runExceptT</a> $ checkedOffsetJump 0x8000 :: Machine -> (Either String (), Machine)