是否有Monad的实例，但没有MonadFix的实例？

Question

问题主要在标题中。似乎可以为任何一元计算定义mfix，尽管它可能会发散：

mfix :: (a -> m a) -> m a
mfix f = fix (join . liftM f)

这个建筑有什么问题？另外，为什么Monad和MonadFix类型是分开的(即哪种类型有Monad的实例，而没有MonadFix的实例)？

Answer 1

left shrinking (or tightening) law says

mfix (\x -> a >>= \y -> f x y)  =  a >>= \y -> mfix (\x -> f x y)

特别是这意味着

mfix (\x -> a' >> f x)  =  a' >> mfix f

这意味着mfix中的一元操作必须精确地计算一次。这是您的版本无法满足的MonadFix的主要属性之一。

考虑下面这个创建循环可变列表的示例(让我们忽略这样一个事实:由于易变性，您可以在不使用mfix的情况下做到这一点)：

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

对于mfix的变体，对mrepeat的调用永远不会结束，因为您要无限期地使用newIORef调用内部部分。

Answer 2

您对mfix的定义不能保证与标准定义相同。事实上，至少在单子清单中，它更严格：

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