Есть ли экземпляр 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 должен оцениваться ровно один раз. Это одно из основных свойств 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.