Невозможно получить экземпляр 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 нет объявления экземпляра для этого? Пожалуйста, помогите мне понять это!

С уважением Marian

PS: Я обнаружил, что Запись в блоге на blog.sigfpe.com , где-то на В конце обсуждения Эдвард Кметт говорит:

"(...) Как я помню,« pass »и« local »вызывают проблемы с текущим MTL, когда вы начинаете микширование в ContT, и, вероятно, должны быть разделены на отдельные классы. 1023 * Может быть, то же самое удержание также для прослушивания из 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 теперь является значением, записанным вычислением whole , а не только частью перед вызовом нашего продолжения \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, который может создать парадокс.