The question is mostly in the title. It seems like mfix
can be defined for any monadic computation, even though it might diverge:
mfix :: (a -> m a) -> m a
mfix f = fix (join . liftM f)
What is wrong with this construction? Also, why are the Monad
and MonadFix
typeclasses separate (i.e. what type has an instance of Monad
but not of MonadFix
)?
The left shrinking (or tightening) law says that
mfix (\x -> a >>= \y -> f x y) = a >>= \y -> mfix (\x -> f x y)
In particular this means that
mfix (\x -> a' >> f x) = a' >> mfix f
which means that the monadic action inside mfix
must be evaluated exactly once. This is one of the main properties of MonadFix
which your version fails to satisfy.
Consider this example that creates a cyclic mutable list (let's disregard the fact that you could do that without mfix
thanks to mutability):
import Control.Monad
import Control.Monad.Fix
import Data.IORef
data MList a = Nil | Cons a (IORef (MList a))
mrepeat :: a -> IO (MList a)
mrepeat x = mfix (liftM (Cons x) . newIORef)
main = do
(Cons x _) <- mrepeat 1
print x
With your variant of mfix
the call to mrepeat
never finishes, as you're calling the inner part with newIORef
indefinitely.
Your definition of mfix
is not guaranteed to be equivalent to the standard one. In fact, at least in the list monad it is stricter:
> take 1 $ mfix (\x -> [1,x])
[1]
> let mfix2 :: Monad m => (a -> m a) -> m a; mfix2 f = fix (join . liftM f)
> take 1 $ mfix2 (\x -> [1,x])
Interrupted.