是否有Monad的实例，但不是MonadFix的实例？ [英] Is there an instance of Monad but not of MonadFix?

问题描述

问题主要在标题中。看起来像 mfix 可以为任何一元计算定义，即使它可能会发散：

  mfix ::（a  - > ma） - > ma 
 mfix f = fix（join。liftM f）
  

这种结构有什么问题？另外，为什么将 Monad 和 MonadFix 类型类分开（即哪个类型的实例是 Monad 但不是 MonadFix ）？

解决方案

< 左侧缩小（或紧缩）法律说

  mfix（\ x  - > a>> = \y  - > fxy） = a>> = \ y  - > mfix（\ x  - > fxy）
  

特别是这意味着

  mfix（\ x  - > a'>> fx）= a'>> mfix f 
  

这意味着 mfix 必须精确评估一次。这是 MonadFix 你的版本无法满足的主要属性之一。

考虑这个例子，循环可变列表（让我们忽略这样一个事实，即你可以在不存在 mfix 的情况下感谢可变性）：

  import Control.Monad 
 import Control.Monad.Fix 
 import Data.IORef 
 
 data MList a = Nil |缺点（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 。

The question is mostly in the title. It seems like mfix can be defined for any monadic computation, even though it might diverge:

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

What is wrong with this construction? Also, why are the Monad and MonadFix typeclasses separate (i.e. what type has an instance of Monad but not of MonadFix)?

解决方案

The left shrinking (or tightening) law says that

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

In particular this means that

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

which means that the monadic action inside mfix must be evaluated exactly once. This is one of the main properties of MonadFix which your version fails to satisfy.

Consider this example that creates a cyclic mutable list (let's disregard the fact that you could do that without mfix thanks to mutability):

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

With your variant of mfix the call to mrepeat never finishes, as you're calling the inner part with newIORef indefinitely.

这篇关于是否有Monad的实例，但不是MonadFix的实例？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！