Is it possible to implement MonadFix for `Free`?

Question

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?

Answer 1

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.)