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

Well, inspired by the MonadFix instance for Maybe, I tried this one (using the following definitions of 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 are:

• Purity: mfix (return . h) = return (fix h)
• Left shrinking: mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
• Sliding: mfix (liftM h . f) = liftM h (mfix (f . h)), for strict h
• Nesting: mfix (\x -> mfix (f x)) = mfix (\x -> f x x)

Purity is easy to prove -- but I came across a problem when trying to prove left shrinking:

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

but

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

So, at the very least, if the Pure and Impure constructors are distinguishable, then my implementation of mfix does not satisfy the laws. I can't think of any other implementation, but that does not mean it does not exist. Sorry I couldn't illuminate further.

Answer 2

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

Answer 3

No, it cannot be written in general, because not every Monad is an instance of MonadFix. Every Monad can be implemented using the FreeMonad underneath. If you could implement the MonadFix for Free, then you would be able to derive MonadFix from any Monad, which is not possible. But of course, you can define a FreeFix for the MonadFix class.

I think it might look somehow like this, but this is just a 3rd guess (still not tested):

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)

The idea is that m is a Monad that lacks an implementation for mfix; so mfix needs to be a parameter when FreeFix will be reduced.