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

Question

我有一个简化版本的标准解释器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只是一个单子而不仅仅是一个单子变换器,并且有

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是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

如果t是monad transormer,m是a Monad,而且t m也是a Monad,那么UnFree t m就是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

用法

对于你的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可以求解释.当计算需要并使用解释器时,将使用相同的解释器来解释程序的那部分,就像用于开始解释程序一样.