是否有可能为`Free'实现MonadFix？ [英] Is it possible to implement MonadFix for `Free`?

问题描述

中的 http://hackage.haskell.org/package/free Control.Monad .Free.Free 可以让任何给定的 Functor 访问free monad。但是，它不包含 MonadFix 实例。这是因为这样一个实例不能被写入，或者它被遗漏了吗？

如果这样的实例不能被写入，为什么不能？

解决方案

考虑描述 mfix 的作用：

单点计算的固定点。 mfix f 只执行一次动作 f ，并将最终输出作为输入反馈。

$ $ b

在 Free 的上下文中，执行一词意味着创建函子。因此，只有一次意味着在评估 mfix f 的结果中， Pure 构造函数中保存的值必须完全确定有多少个函数层被创建。

现在，假设我们有一个特定的函数一次，我们知道将始终只创建一个 Free 构造函数，但是需要很多 Pure 构造函数来保存叶值。那么，'once'的输出将只是类型 Free fa 的值，它们同构于类型 fa 。有了这些知识，我们可以安全地取消< - code> Free 一次的输出，以获得<$ c


$ b

现在请注意，只执行一次动作， mfix一次的结果对于符合的实例应该不包含比一次的其他一元结构一次在单个应用程序中创建。因此，我们可以推断，从 mfix获得的值必须同构于<给定任何类型为 a - >的函数。对于一些 Functor f ，我们可以用一个 Free 并获得一个类型为 a - >的函数。免费fa 满足上面一次的描述，并且我们已经确定可以解开 mfix的结果一次来获取类型 fa 返回值。

因此，一个符合实例（Functor f）=> MonadFix（Free f）意味着能够通过上述的打包和解包来写入函数 ffix ::（Functor f）=> （a - > f a） - > fa ，它可以用于 Functor 的所有实例。

这显然不是证明你不能写这样一个实例......但是如果可能的话， MonadFix 将是完全多余的，因为你可以轻松地直接写 ffix 。 （我想用> liftM 将它重新实现为 mfix 并带有 Monad 约束。 c $ c>。呃。）


http://hackage.haskell.org/package/free in Control.Monad.Free.Free allows one to get access to the "free monad" for any given Functor. It does not, however, have a MonadFix instance. Is this because such an instance cannot be written, or was it just left out?

If such an instance cannot be written, why not?

解决方案

Consider the description of what mfix does:

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

The word "executes", in the context of Free, means creating layers of the Functor. Thus, "only once" means that in the result of evaluating mfix f, the values held in Pure constructors must fully determine how many layers of the functor are created.

Now, say we have a specific function once that we know will always only create a single Free constructor, plus however many Pure constructors are needed to hold the leaf values. The output of 'once', then, will be only values of type Free f a that are isomorphic to some value of type f a. With this knowledge, we can un-Free the output of once safely, to get a value of type f a.

Now, note that because mfix is required to "execute the action only once", the result of mfix once should, for a conforming instance, contain no additional monadic structure than once creates in a single application. Thus we can deduce that the value obtained from mfix once must also be isomorphic to a value of type f a.

Given any function with type a -> f a for some Functor f, we can wrap the result with a single Free and get a function of type a -> Free f a which satisfies the description of once above, and we've already established that we can unwrap the result of mfix once to get a value of type f a back.

Therefore, a conforming instance (Functor f) => MonadFix (Free f) would imply being able to write, via the wrapping and unwrapping described above, a function ffix :: (Functor f) => (a -> f a) -> f a that would work for all instances of Functor.

That's obviously not a proof that you can't write such an instance... but if it were possible, MonadFix would be completely superfluous, because you could just as easily write ffix directly. (And I suppose reimplement it as mfix with a Monad constraint, using liftM. Ugh.)

这篇关于是否有可能为`Free'实现MonadFix？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！