Есть ли экземпляр Monad, но не MonadFix?

В основном это вопрос. Кажется, что mfix может быть определен для любого монадического вычисления, хотя он может расходиться:

Что не так с этой конструкцией? Кроме того, почему отдельные классы Monad и MonadFix разделяются (например, какой тип имеет экземпляр Monad, но не MonadFix)?

Ответы

Ответ 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 неопределенно.

Ответ 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.