2 回答
其实，并不是不能有MonadFix实例，只是库的类型有点太受限制了。如果您定义ContT了所有可能r的 s，那么不仅MonadFix可能，而且所有实例Monad都不需要底层仿函数：
newtype ContT m a = ContT { runContT :: forall r. (a -> m r) -> m r }
instance Functor (ContT m) where
fmap f (ContT k) = ContT (\kb -> k (kb . f))
instance Monad (ContT m) where
return a = ContT ($a)
join (ContT kk) = ContT (\ka -> kk (\(ContT k) -> k ka))
instance MonadFix m => MonadFix (ContT m) where
mfix f = ContT (\ka -> mfixing (\a -> runContT (f a) ka<&>(,a)))
where mfixing f = fst <$> mfix (\ ~(_,a) -> f a )
考虑mfix延续单子的类型签名。
(a -> ContT r m a) -> ContT r m a
-- expand the newtype
(a -> (a -> m r) -> m r) -> (a -> m r) -> m r
这是没有这种类型的纯粹居民的证据。
---------------------------------------------
(a -> (a -> m r) -> m r) -> (a -> m r) -> m r
introduce f, k
f :: a -> (a -> m r) -> m r
k :: a -> m r
---------------------------
m r
apply k
f :: a -> (a -> m r) -> m r
k :: a -> m r
---------------------------
a
dead end, backtrack
f :: a -> (a -> m r) -> m r
k :: a -> m r
---------------------------
m r
apply f
f :: a -> (a -> m r) -> m r f :: a -> (a -> m r) -> m r
k :: a -> m r k :: a -> m r
--------------------------- ---------------------------
a a -> m r
dead end reflexivity k
如您所见，问题在于两者都f期望k类型的值a作为输入。但是，没有办法变出 type 的值a。mfix因此，对于延续单子没有纯粹的居民。
请注意，您也不能mfix递归定义，因为mfix f k = mfix ? ?没有基本情况会导致无限回归。而且，我们无法定义mfix f k = f ? ?，或者mfix f k = k ?因为即使使用递归也无法产生 type 的值a。
mfix但是，我们可以对 continuation monad进行不纯的实现吗？考虑以下。
import Control.Concurrent.MVar
import Control.Monad.Cont
import Control.Monad.Fix
import System.IO.Unsafe
instance MonadFix (ContT r m) where
mfix f = ContT $ \k -> unsafePerformIO $ do
m <- newEmptyMVar
x <- unsafeInterleaveIO (readMVar m)
return . runContT (f x) $ \x' -> unsafePerformIO $ do
putMVar m x'
return (k x')
出现的问题是如何f申请x'。通常，我们会使用递归的 let 表达式，即let x' = f x'. 但是，x'不是 的返回值f。相反，给定的延续f适用于x'。为了解决这个难题，我们创建了一个空的可变变量m，懒惰地读取它的值x，然后应用f到x. 这样做是安全的，因为f它的论点不能严格。当f最终调用给它的延续时，我们将结果存储x'在m并将延续应用k到x'. 因此，当我们最终评估时，x我们得到了结果x'。
上述mfixfor the continuation monad 的实现看起来很像mfixfor IOmonad 的实现。
import Control.Concurrent.MVar
import Control.Monad.Fix
instance MonadFix IO where
mfix f = do
m <- newEmptyMVar
x <- unsafeInterleaveIO (takeMVar m)
x' <- f x
putMVar m x'
return x'
请注意，在mfixfor the continuation monad 的实现中我们使用readMVar了，而在mfixfor IOmonad 的实现中我们使用了takeMVar. 这是因为，给定的延续f可以被多次调用。但是，我们只想存储给第一个回调的结果。使用readMVar而不是takeMVar确保可变变量保持完整。因此，如果连续调用不止一次，那么第二个回调将无限期地阻塞putMVar操作。
但是，只存储第一个回调的结果似乎有点随意。所以，这里有一个实现mfixcontinuation monad，它允许多次调用提供的 continuation。我用 JavaScript 编写它是因为我无法让它很好地适应 Haskell 中的懒惰。
// mfix :: (Thunk a -> ContT r m a) -> ContT r m a
const mfix = f => k => {
const ys = [];
return (function iteration(n) {
let i = 0, x;
return f(() => {
if (i > n) return x;
throw new ReferenceError("x is not defined");
})(y => {
const j = i++;
if (j === n) {
ys[j] = k(x = y);
iteration(i);
}
return ys[j];
});
}(0));
};
const example = triple => k => [
{ a: () => 1, b: () => 2, c: () => triple().a() + triple().b() },
{ a: () => 2, b: () => triple().c() - triple().a(), c: () => 5 },
{ a: () => triple().c() - triple().b(), b: () => 5, c: () => 8 },
].flatMap(k);
const result = mfix(example)(({ a, b, c }) => [{ a: a(), b: b(), c: c() }]);
console.log(result);这是等效的 Haskell 代码，没有mfix.
import Control.Monad.Cont
import Control.Monad.Fix
data Triple = { a :: Int, b :: Int, c :: Int } deriving Show
example :: Triple -> ContT r [] Triple
example triple = ContT $ \k ->
[ Triple 1 2 (a triple + b triple)
, Triple 2 (c triple - a triple) 5
, Triple (c triple - b triple) 5 8
] >>= k
result :: [Triple]
result = runContT (mfix example) pure
main :: IO ()
main = print result
请注意，这看起来很像 list monad。
import Control.Monad.Fix
data Triple = { a :: Int, b :: Int, c :: Int } deriving Show
example :: Triple -> [Triple]
example triple =
[ Triple 1 2 (a triple + b triple)
, Triple 2 (c triple - a triple) 5
, Triple (c triple - b triple) 5 8
]
result :: [Triple]
result = mfix example
main :: IO ()
main = print result
这是有道理的，因为毕竟 continuation monad 是所有 monad之母。我将验证MonadFix我的 JavaScript 实现的规律mfix作为练习留给读者。