无法获得MonadWriter实例用于连续Monad变压器？

Question

我尝试为Continuation Monad Transformer的MonadWriter创建一个派生实例.这是我尝试的方式:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}

import Control.Monad.Cont
import Control.Monad.Writer


instance (MonadWriter w m) => MonadWriter w (ContT r m) where
   tell= lift . tell
   listen m= ContT $ \ c -> do
         (a,w) <- listen $ runContT m (c)
         return (a,w)

   pass m = undefined

这给了我以下错误:

Occurs check: cannot construct the infinite type: r = (r, w1)
When generalising the type(s) for `listen'
In the instance declaration for `MonadWriter w (ContT r m)'

接下来尝试是这样的:

instance (MonadWriter w m) => MonadWriter w (ContT r m) where
   tell= lift . tell
   listen m= ContT $ \ c -> do
         (a,w) <- runContT m (listen . c)
         return (a,w)

   pass m = undefined

其次是:

Occurs check: cannot construct the infinite type: a = (a, w)
When generalising the type(s) for `listen'
In the instance declaration for `MonadWriter w (ContT r m)'

有谁知道如何实现听和传递这里？是否有理由在mtl中没有这样的实例声明？请帮我理解这个!

关心玛丽安

PS:我在blog.sigfpe.com上发现Blog Entry,在讨论结束时的某个地方,Edward Kmett说:

"(...)我记得,当你开始在ContT中混音时,'pass'和'local'会导致当前MTL出现问题,并且可能应该被分解为不同的类."

对于MonadWriter来说,听听也许同样如此.因此,最简单的解决方案是,如果您不需要监听并传递特殊情况,请将它们保留为未定义:

instance (MonadWriter w m) => MonadWriter w (ContT r m) where
   tell= lift . tell
   listen = undefined
   pass = undefined

PS:(2011-03-11)在这个主题中进一步潜水我得出了这个解决方案:(当在ContT上指定类型r为()时,我们可以尝试这个:)

  instance (MonadWriter w m) => MonadWriter w (ContT () m) where    
    listen m = do
        a <- m
        (_,w) <- lift $ listen $ runContT m (return . (const ()))
        return (a,w)

这编译!跑了!但是,唉,monadic动作必须计算两次.可能有人拿这个暗示将这两个电话以某种方式合并成一个吗？然后我们将获得所需的实现.

Answer 1

我不认为这是可能的.供参考,以下是ContT:

ContT r m a = (a -> m r) -> m r

这是我的出发点listen:

listen m = ContT $ \c -> 
    runCont m (\x -> c (x,w))

问题是,我们从哪里获得w？ w将来自在使用其返回值调用函数之前runCont m执行的计算.也就是说,我们需要传递的信息来自,所以我们需要做这样的事情:\x -> c (x,w)xcrunCont

listen m = ContT $ \c -> do
    rec (r,w) <- listen . runContT m $ \x -> c (x,w)
    return r

(需要LANGUAGE DoRec和MonadFix m在上下文中)

虽然那种类型不合理,但这是不正确的. w现在是整个计算所写的值,而不仅仅是调用我们的继续之前的部分\x -> c (x,w).

你知道你需要做什么吗？我知道我的回答基本上是"我认为这是不可能的,因为我无法想办法"(Conal Elliott称之为"缺乏想象力的证据"),但我认为这次缺乏想象力是正确的.我们需要的信息在我们有机会窥视之前就被摧毁了.

我相信使用Codensity monad变换器可以实现这个实例:

newtype CodensityT m a = CodensityT { runCodensityT :: forall r. (a -> m r) -> m r }

它可以提供与其相同的性能改进Cont,但不支持callCC.这是因为你可以随心所欲地runCodensityT进行计算r.

listen m = CodensityT $ \c -> listen (runCodensityT m return) >>= c

也许callCC是问题所在.如果你能想出一个结合的例子,我会不会感到惊讶listen,callCC这会产生一个悖论.