由 FreeT 生成的解释器 monad 转换器的 MonadFix 实例？

Question

我有一个由 FreeT:

生成的标准解释器 monad 转换器的简化版本

data InteractiveF p r a = Interact p (r -> a)

type Interactive p r = FreeT (InteractiveF p r)

p 是 "prompt"，r 是 "environment"...有人会运行使用类似的东西：

runInteractive :: Monad m => (p -> m r) -> Interactive p r m a -> m a
runInteractive prompt iact = do
  ran <- runFreeT iact
  case ran of
    Pure x -> return x
    Free (Interact p f) -> do
      response <- prompt p
      runInteractive prompt (f resp)

instance MonadFix m => MonadFix (FreeT (InteractiveF p r)) m a)
mfix = -- ???

我觉得这种类型或多或少只是 StateT 的受限版本...如果有的话，我认为 Interactive p r IO 是 IO 的受限版本。 .我觉得...但是...好吧，无论如何，我的直觉告诉我应该有一个很好的例子。

我试过写一个，但我似乎真的想不通。到目前为止，我最接近的尝试是：

mfix f = FreeT (mfix (runFreeT . f . breakdown))
  where
    breakdown :: FreeF (InteractiveF p r) a (FreeT (InteractiveF p r) m a) -> a
    breakdown (Pure x) = x
    breakdown (Free (Interact p r)) = -- ...?

我也试过使用一个利用了 m 的 MonadFix 实例的版本，但也不走运 --

mfix f = FreeT $ do
  rec ran <- runFreeT (f z)
      z   <- case ran of
               Pure x -> return x
               Free iact -> -- ...
  return -- ...

有人知道这是否真的可行，或者为什么不可行？如果是的话，哪里是我继续寻找的好地方？

或者，在我的实际应用中，我什至不需要使用FreeT...我可以使用Free；也就是说，让 Interactive 只是一个 monad 而不仅仅是一个 monad 转换器，并且

runInteractive :: Monad m => (p -> m r) -> Interactive p r a -> m a
runInteractive _ (Pure x) = return x
runInteractive prompt (Free (Interact p f) = do
    response <- prompt p
    runInteractive prompt (f response)

如果对于这种情况有可能而不是一般的 FreeT 情况，我也会很高兴:)

Answer 1

无法写入 MonadFix m => MonadFix (Interactive p r) 实例。

您的 InteractiveF 是经过充分研究的 Moore machines 的基函子。 Moore 机器提供输出，在您的情况下是提示，然后根据输入（在您的情况下是环境）确定下一步要做什么。摩尔机总是先输出。

data MooreF a b next = MooreF b (a -> next)
    deriving (Functor)

如果我们按照 C. A. McCann's argument 为 Free 编写 MonadFix 个实例，但将自己限制在 Free (MooreF a b) 的特定情况下，我们最终将确定是否存在 MonadFix Free (MooreF a b) 的实例那么必须存在一个函数

mooreFfix :: (next -> MooreF a b next) -> MooreF a b next

要写这个函数，必须构造一个MooreF b (f :: a -> next)。我们没有任何 b 可以输出。可以想象，如果我们已经有了下一个 a，我们可以得到一个 b，但是 Moore 机器总是先输出。

喜欢状态中的let

如果你前面只读一个 a，你可以写一些接近 mooreFfix 的东西。

almostMooreFfix :: (next -> MooreF a b next) -> a -> MooreF a b next
almostMooreFfix f a = let (MooreF b g) = f (g a)
                      in (MooreF b g)

然后 f 能够独立于参数 next 确定 g 变得势在必行。所有可能使用的 f 都是 f next = MooreF (f' next) g' 的形式，其中 f' 和 g' 是一些其他函数。

almostMooreFFix :: (next -> b) -> (a -> next) -> a -> MooreF a b next
almostMooreFFix f' g' a = let (MooreF b g) = f (g a)
                          in (MooreF b g)
                          where
                              f next = MooreF (f' next) g'

通过一些等式推理，我们可以替换 let

右侧的 f

almostMooreFFix :: (next -> b) -> (a -> next) -> a -> MooreF a b next
almostMooreFFix f' g' a = let (MooreF b g) = MooreF (f' (g a)) g'
                          in (MooreF b g)

我们将 g 绑定到 g'。

almostMooreFFix :: (next -> b) -> (a -> next) -> a -> MooreF a b next
almostMooreFFix f' g' a = let (MooreF b _) = MooreF (f' (g' a)) g'
                          in (MooreF b g')

当我们将 b 绑定到 f' (g' a) 时，let 变得不必要并且该函数没有递归节点。

almostMooreFFix :: (next -> b) -> (a -> next) -> a -> MooreF a b next
almostMooreFFix f' g' a = MooreF (f' (g' a)) g'

所有不是 undefined 的 almostMooreFFix 甚至不需要 let。

Answer 2

假设您已经有了 Interactive 的翻译。

interpret :: FreeT (InteractiveF p r) m a -> m a
interpret = undefined

编写一个 MonadFix 实例是微不足道的：

instance MonadFix m => MonadFix (FreeT (InteractiveF p r) m) where
    mfix = lift . mfix . (interpret .)

我们可以直接捕捉 "knowing the interpeter" 的这种想法，而无需提前提交解释器。

{-# LANGUAGE RankNTypes #-}

data UnFreeT t m a = UnFree {runUnFreeT :: (forall x. t m x -> m x) -> t m a}
--   given an interpreter from `t m` to `m` ^                          |
--                                  we have a value in `t m` of type a ^

UnFreeT只是一个读取解释器的ReaderT。

如果t是一个单子变换器，那么UnFreeT t也是一个单子变换器。我们可以轻松地从不需要了解解释器的计算中构建一个 UnFreeT，只需忽略解释器即可。

unfree :: t m a -> UnFreeT t m a
--unfree = UnFree . const
unfree x = UnFree $ \_ -> x

instance (MonadTrans t) => MonadTrans (UnFreeT t) where
    lift = unfree . lift

如果t是一个monad transormer，m是一个Monad，t m也是一个Monad，那么UnFree t m是一个Monad。给定一个解释器，我们可以将两个需要解释器的计算绑定在一起。

{-# LANGUAGE FlexibleContexts #-}

refree :: (forall x. t m x -> m x) -> UnFreeT t m a -> t m a
-- refree = flip runUnFreeT
refree interpreter x = runUnFreeT x interpreter

instance (MonadTrans t, Monad m, Monad (t m)) => Monad (UnFreeT t m) where
    return = lift . return
    x >>= k = UnFree $ \interpreter -> runUnFreeT x interpreter >>= refree interpreter . k

最后，给定解释器，只要底层 monad 有一个 MonadFix 实例，我们就可以修复计算。

instance (MonadTrans t, MonadFix m, Monad (t m)) => MonadFix (UnFreeT t m) where
    mfix f = UnFree $ \interpreter -> lift . mfix $ interpreter . refree interpreter . f

一旦有了解释器，我们实际上可以做底层 monad 可以做的任何事情。这是因为，一旦我们有了 interpreter :: forall x. t m x -> m x，我们就可以执行以下所有操作。我们可以从 m x 到 t m x 一直到 UnFreeT t m x 并再次下降。

                      forall x.
lift               ::           m x ->         t m x
unfree             ::         t m x -> UnFreeT t m x
refree interpreter :: UnFreeT t m x ->         t m x
interpreter        ::         t m x ->           m x

用法

对于您的 Interactive，您需要将 FreeT 包装在 UnFreeT 中。

type Interactive p r = UnFreeT (FreeT (InteractiveF p r))

您的解释器仍将被编写为生成 FreeT (InteractiveF p r) m a -> m a。要将新的 Interactive p r m a 一直解释为 m a，您将使用

interpreter . refree interpreter

UnFreeT不再是"frees the interpreter as much as possible"。解释器不能再随心所欲地随意决定要做什么。 UnFreeT 中的计算可以求解释器。当计算请求并使用解释器时，将使用与开始解释程序时使用的相同解释器来解释程序的那部分。

由 FreeT 生成的解释器 monad 转换器的 MonadFix 实例？

MonadFix instance for interpreter monad transformer generated by FreeT?

monads

haskell

monadfix

free-monad

喜欢状态中的let

用法