haskell - Monad のインスタンスはありますが、MonadFix のインスタンスはありませんか?

Question

質問は主にタイトルにあります。mfix発散する可能性がありますが、どのモナド計算でも定義できるようです。

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

この構造の何が問題なのですか？また、 と の型クラスが分かれているのはなぜMonadですかMonadFix(つまり、どの型が のインスタンスを持ち、 のインスタンスを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

つまり、内部のモナド アクションmfixは 1 回だけ評価する必要があります。MonadFixこれは、バージョンが満たさない主な特性の 1 つです。

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しない呼び出しのバリアントを使用します。mrepeatnewIORef

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.