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

Question

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

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

type Interactive p r = FreeT (InteractiveF p r)

p是“提示符”，而r是“环境”...one使用如下方式运行：

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...if的一个受限版本，Interactive p r IO是IO...I think...but的一个受限版本.嗯，无论如何，我的直觉说应该有一个好的例子。

我试着写了一个，但我似乎真的搞不懂。到目前为止，我最近的尝试是：

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...I就可以只使用Free；也就是说，让Interactive只是一个单台而不仅仅是一个单台转换器，并且有

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

假设您已经有了一个用于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。

如果t是一个单变压器，那么UnFreeT t也是一个单一变压器。我们可以很容易地从不需要知道解释器的计算中构建UnFreeT，只需忽略interpeter即可。

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是单端转换体，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不再“尽可能地释放解释器”。解释器不能再任意地决定它想做什么。UnFreeT中的计算可以请求一个解释器。当计算请求并使用解释器时，将使用相同的解释器来解释程序的该部分，就像用于开始解释程序一样。

Answer 2

编写MonadFix m => MonadFix (Interactive p r)实例是不可能的。

您的InteractiveF是研究良好的摩尔机的基函子。Moore机器提供一个输出，在您的例子中是提示符，然后根据输入确定下一步要做的事情，在您的例子中是环境。摩尔机器总是首先输出。

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

如果我们遵循C. A. McCann的论点关于为Free编写MonadFix实例，但将自己局限于Free (MooreF a b)的特定情况，那么我们最终将确定如果存在Free (MooreF a b)的MonadFix实例，那么就必须存在一个函数

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

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

就像“国家让”一样

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

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'

通过一些等式推理，我们可以在f的右侧替换let

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'

所有不是almostMooreFFix的undefined都不需要let。