haskell - 是否可以为 `Free` 实现 MonadFix ？

Question

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

如果无法编写这样的实例，为什么不呢？

Answer 1

考虑 mfix 的描述是:

The fixed point of a monadic computation. mfix f executes the action f only once, with the eventual output fed back as the input.

“执行”一词，在 Free 的上下文中，意味着创建 Functor 的图层。因此，“仅一次”意味着在评估mfix f的结果中， Pure 中保存的值构造函数必须完全确定创建仿函数的层数。

现在，假设我们有一个特定的函数 once我们知道永远只会创建一个 Free构造函数，加上任意数量 Pure需要构造函数来保存叶值。那么，“once”的输出将仅为 Free f a 类型的值。与 f a 类型的某个值同构。有了这些知识，我们就可以- Free once的输出安全地获取 f a 类型的值.

现在，请注意，因为 mfix需要“仅执行一次操作”，结果为 mfix once对于符合要求的实例，不应包含除 once 之外的其他一元结构。在单个应用程序中创建。由此我们可以推断出mfix once获得的值还必须与 f a 类型的值同构.

给定任何类型为 a -> f a 的函数对于一些Functor f ，我们可以用单个 Free 包装结果并得到 a -> Free f a 类型的函数满足 once 的描述如上所述，我们已经确定可以解开 mfix once 的结果。获取 f a 类型的值返回。

因此，符合条件的实例 (Functor f) => MonadFix (Free f)意味着能够通过上述包装和展开来编写函数 ffix :: (Functor f) => (a -> f a) -> f a这适用于 Functor 的所有实例.

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