Esiste un'istanza di Monad ma non di MonadFix?

Question

La domanda è principalmente nel titolo. Sembra che mfix può essere definito per qualsiasi calcolo monade, anche se potrebbe divergono:

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

Cosa c'è di sbagliato con questa costruzione? Inoltre, perché sono separati i typeclasses Monad e MonadFix (ad esempio, che tipo ha un'istanza di Monad ma non di MonadFix)?

Answer 1

Il left shrinking (or tightening) law says che

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

In particolare, ciò significa che

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

che significa che l'azione monadic all'interno mfix deve essere valutato esattamente una volta. Questa è una delle proprietà principali di MonadFix che la tua versione non riesce a soddisfare.

Considerate questo esempio che crea un elenco mutabile ciclico (cerchiamo di non tener conto del fatto che si poteva farlo senza mfix grazie alla mutevolezza):

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 

Con la vostra variante mfix la chiamata a mrepeat non finisce mai, come stai chiamando la parte interna con newIORef indefinitamente.

Answer 2

La tua definizione di mfix non è garantita per essere equivalente a quella standard. Infatti, almeno nella lista Monade è rigoroso:

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