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

我有一个由以下命令生成的标准解释器 monad 转换器的简化版本FreeT:

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

type Interactive p r = FreeT (InteractiveF p r)

p是“提示”，并且r是“环境”...可以使用以下命令来运行它：

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)) = -- ...?

我还尝试使用一个版本，利用MonadFix的实例m，但也没有运气——

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 情况有可能，我也会很高兴:)

假设您已经有一名口译员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 .)

我们可以直接捕捉“了解解释器”的想法，而无需提前委托解释器。

{-# 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读取解释器。

If t是一个 Monad 转换器，UnFreeT t也是一个 monad 转换器。我们可以轻松构建一个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

If t是一个 Monad 转换器，m is a Monad, and t m也是一个Monad, then UnFree t m is a 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

Usage

为您Interactive，你会包裹FreeT in 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

The UnFreeT不再“尽可能地释放口译员”。口译员不能再随心所欲地决定要做什么。中的计算UnFreeT可以请求翻译。当计算请求并使用解释器时，将使用与开始解释程序相同的解释器来解释程序的该部分。