Невозможно получить экземпляр MonadWriter для продолжения Monad Transformer?

Question

Я пытаюсь сделать производный экземпляр для MonadWriter из Continuation Monad Transformer. Вот как я это попробовал:

{-# 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, где где-то в конце обсуждения Эдвард Кметт говорит:

"(...) Как я помню," pass "и" local "вызывают проблемы с текущим MTL, когда вы начинаете микширование в ContT, и, вероятно, должны быть разделены на отдельные классы".

Может быть, тот же трюм также для прослушивания из MonadWriter. Таким образом, самое простое решение, если вам не нужно слушать и передавать в особом случае, оставить их неопределенными:

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

PS: (2011-03-11) Погружаясь дальше в этой теме, я придумал это решение: (При указании типа r на ContT как () мы могли бы попробовать это:)

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

Это компилируется! И бежит! Но, увы, монадическое действие нужно вычислять дважды. Кто-нибудь может принять это как намек, чтобы свести два вызова как-то в один? Тогда мы получим желаемую реализацию.

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) с его возвращаемым значением x, То есть информация, которую мы должны передать c происходит от runCont так что нам нужно сделать что-то вроде этого:

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),

Вы видите, что вам нужно сделать? Я знаю, что мой ответ по сути "я думаю, что это невозможно, потому что я не могу придумать, как это сделать" (то, что Конал Эллиотт называет "доказательством недостатка воображения"), но я думаю, что мое отсутствие воображения на этот раз правильно. Информация, в которой мы нуждаемся, уничтожается, прежде чем у нас появляется возможность взглянуть на нее.

Я полагаю, что этот случай возможен с монадным трансформатором Codensity:

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 это создало бы парадокс.