`Free`可以实现MonadFix吗？

Question

Control.Monad.Free.Free中的http://hackage.haskell.org/package/free允许用户访问任何给定Functor的“免费monad”。但是，它没有MonadFix实例。这是因为这样的实例无法编写，还是被遗漏了？

如果这样的实例无法写入，原因何在？

Answer 1

考虑一下对mfix功能的描述：

一元运算的不动点。mfix f只执行一次动作f，最终的输出作为输入反馈。

在Free的上下文中，单词"executes“意味着创建Functor的层。因此，“只有一次”意味着在计算mfix f的结果中，Pure构造函数中保存的值必须完全确定创建了多少层函数。

现在，假设我们有一个特定的函数once，我们知道它总是只创建一个Free构造函数，再加上需要多少个Pure构造函数来保存叶的值。然后，“once”的输出将只是与f a类型的某个值同构的Free f a类型的值。有了这些知识，我们就可以安全地对once的输出取消Free，得到一个f a类型的值。

现在，请注意，因为mfix需要“只执行一次操作”，所以对于符合条件的实例，mfix once的结果不应该包含once在单个应用程序中创建的额外的单变量结构。因此，我们可以推断，从mfix once获得的值也必须与f a类型的值同构。

给定某个Functor f的任何类型为a -> f a的函数，我们可以用单个Free包装结果，并获得满足上面对once的描述的a -> Free f a类型的函数，并且我们已经确定可以展开mfix once的结果以获得f a类型的值。

因此，符合标准的实例(Functor f) => MonadFix (Free f)将意味着能够通过上述包装和解包来编写适用于Functor的所有实例的函数ffix :: (Functor f) => (a -> f a) -> f a。

这显然不能证明你不能写这样的实例...但是如果可能的话，MonadFix将完全是多余的，因为您可以很容易地直接编写ffix。(我假设使用liftM将其重新实现为带有Monad约束的mfix。啊。)

Answer 2

受Maybe的MonadFix实例的启发，我尝试了这个实例(使用以下Free定义)：

data Free f a
    = Pure a
    | Impure (f (Free f a))

instance (Functor f) => Monad (Free f) where
    return = Pure
    Pure x >>= f = f x
    Impure x >>= f = Impure (fmap (>>= f) x)

instance (Functor f) => MonadFix (Free f) where
    mfix f = let Pure x = f x in Pure x

The laws包括：

对于严格的h

• Nesting：mfix (\x -> mfix (f x)) = mfix (\x -> f x x)

，

• 纯净：mfix (return . h) = return (fix h)
• Left缩小：mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
• Sliding：mfix (liftM h . f) = liftM h (mfix (f . h))

纯洁性很容易证明--但我在试图证明left收缩时遇到了一个问题：

mfix (\x -> a >>= \y -> f x y)
= let Pure x = (\x -> a >>= \y -> f x y) x in Pure x
= let Pure x = a >>= \y -> f x y in Pure x
-- case a = Pure z
  = let Pure x = Pure z >>= \y -> f x y in Pure x
  = let Pure x = f x z in Pure x
  = let Pure x = (\x -> f x z) x in Pure x
  = mfix (\x -> f x z)
  = Pure z >>= \y -> mfix (\x -> f x y)
-- case a = Impure t
  = let Pure x = Impure t >>= \y -> f x y in Pure x
  = let Pure x = Impure (fmap (>>= \y -> f x y) t) in Pure x
  = Pure _|_

但

  Impure t >>= \y -> mfix (\x -> f x y)
  = Impure (fmap (>>= \y -> mfix (\x -> f x y)) t)
  /= Pure _|_

因此，至少，如果Pure和Impure构造函数是可区分的，那么我的mfix实现就不符合法律。我不能想到任何其他的实现，但这并不意味着它不存在。抱歉，我不能进一步说明。

Answer 3

不，它不能在一般情况下编写，因为不是每个Monad都是MonadFix的实例。每个Monad都可以使用底层的FreeMonad来实现。如果您可以免费实现MonadFix，那么您将能够从任何Monad派生MonadFix，这是不可能的。当然，您也可以为MonadFix类定义一个FreeFix。

我认为它可能看起来像这样，但这只是第三个猜测(仍然没有测试)：

data FreeFix m a = FreeFix { runFreeFix :: (forall r. (r -> m r) -> m r) -> m a }

instance (Monad m) => Monad (FreeFix m) where
    return a = FreeFix $ \_-> do
        return a
    f >>= g = FreeFix $ \mfx -> do
        x <- runFreeFix f mfx
        runFreeFix (g x) mfx

instance (Monad m) => MonadFix (FreeFix m) where
    mfix f = FreeFix $ \mfx -> do
        mfx (\r->runFreeFix (f r) mfx)

其想法是，m是一个缺少mfix实现的Monad；因此，当FreeFix将减少时，mfix需要是一个参数。