Monad有没有MonadFix的实例？

Question

问题主要在标题中.似乎mfix可以为任何monadic计算定义,即使它可能有所不同:

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

这个结构有什么问题？另外,为什么Monad和MonadFixtypeclass分开(即什么类型有一个实例Monad但没有MonadFix？)？

Answer 1

该(或紧缩)左收缩定律说的是

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

特别是这意味着

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

这意味着内部的monadic动作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不保证等同于标准定义.事实上,至少在monad列表中它更严格:

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