14

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

Mokosha
  • 2,737
  • 16
  • 33
  • 3
    The continuation monad does not have the desired fixpoint operator. – augustss Sep 12 '14 at 22:45
  • 1
    See also [Why can't there be an instance of MonadFix for the continuation monad?](http://stackoverflow.com/q/25827227/1333025). – Petr Sep 14 '14 at 15:48

2 Answers2

17

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.

Petr
  • 62,528
  • 13
  • 153
  • 317
6

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.
chi
  • 111,837
  • 3
  • 133
  • 218