Используйте MonadRef для реализации MonadCont

Question

Существует хорошо известная проблема, которую мы не можем использовать forall вводит в Cont тип возврата.

Однако должно быть хорошо иметь следующее определение:

class Monad m => MonadCont' m where
    callCC' :: ((a -> forall b. m b) -> m a) -> m a
    shift :: (forall r.(a -> m r) -> m r) -> m a
    reset :: m a -> m a

а затем найти экземпляр, который имеет смысл. В этой статье автор утверждал, что мы можем реализовать MonadFix на вершине ContT r m при условии что m реализованы MonadFix а также MonadRef, Но я думаю, что если у нас есть MonadRef мы можем реально реализовать callCC' выше, как следующее:

--satisfy law: mzero >>= f === mzero
class Monad m => MonadZero m where
    mzero :: m a

instance (MonadZero m, MonadRef r m) => MonadCont' m where
    callCC' k = do
        ref <- newRef Nothing
        v <- k (\a -> writeRef ref (Just a) >> mzero)
        r <- readRef ref
        return $ maybe v id r
    shift = ...
    reset = ...

(К сожалению, я не знаком с семантикой shift а также reset поэтому я не предоставил реализации для них)

Эта реализация, кажется, хорошо для меня. Интуитивно, когда callCC' будучи призванным, мы кормим k что функция, что ее собственный эффект всегда терпит неудачу (хотя мы не можем предоставить значение произвольного типа b, но мы всегда можем предоставить mzero типа m b и в соответствии с законом он должен эффективно прекратить вычисление всех дальнейших эффектов), и он получает полученное значение как конечный результат callCC',

Итак, мой вопрос:

Является ли эта реализация работает, как ожидается, для идеального callCC? Можем ли мы реализовать shift а также reset с правильной семантикой, а?

В дополнение к вышесказанному, я хочу знать:

Чтобы обеспечить правильное поведение, мы должны принять некоторые свойства MonadRef, Так что бы законы MonadRef иметь для того, чтобы заставить вышеупомянутую реализацию вести себя как ожидалось?

ОБНОВИТЬ

Оказывается, вышеприведенная наивная реализация недостаточно хороша. Чтобы оно удовлетворяло "Ток продолжения"

callCC $\k -> k m === callCC $ const m === m

Мы должны приспособить реализацию к

instance (MonadPlus m, MonadRef r m) => MonadCont' m where
    callCC' k = do 
       ref <- newRef mzero
       mplus (k $ \a -> writeRef ref (return a) >> mzero) (join (readRef ref))

Другими словами, оригинал MonadZero недостаточно, мы должны быть в состоянии объединить mzero значение с нормальным вычислением без отмены всего вычисления.

Вышеизложенное не отвечает на вопрос, оно просто скорректировано, поскольку первоначальная попытка была сфальсифицирована, чтобы быть кандидатом. Но для обновленной версии оригинальные вопросы все еще остаются вопросами. Особенно, reset а также shift еще предстоит реализовать.

Answer 1

(Это еще не ответ, но только некоторые подсказки возникли у меня в голове. Надеюсь, что это приведет к реальному ответу, я или кто-то еще.)

Call-by-Value - это двойственный вызов по имени - Philip Wadler

В вышеприведенной статье автор представил "Двойное исчисление", типизированное исчисление, соответствующее классической логике. В последнем разделе есть сегмент говорит

Стратегия, двойная по требованию, могла бы избежать этой неэффективности, перезаписывая coterm его covalue при первой оценке.

Как указано в статье Вадлера, вызов по имени оценивает продолжения с нетерпением (он возвращается до оценки всех значений), в то время как вызов по значению оценивает продолжения лениво (возвращается только после оценки всех значений).

Теперь взгляните на callCC' выше, я полагаю, что это пример двойного вызова по требованию на стороне продолжения. Стратегия оценки заключается в том, чтобы обеспечить поддельное "продолжение" данной функции, но кешировать состояние в этой точке, чтобы позже вызвать "истинное" продолжение. Это похоже на создание кэша продолжения, и поэтому, как только вычисления завершатся, мы восстановим это продолжение. Но кэшируйте оцененное значение, как оно подразумевается по требованию.

В общем, я подозреваю, что состояние (вычисление до текущего момента времени) двойственно продолжению (будущее вычисление). Это объяснит несколько явлений. Если это правда, то неудивительно, что MonadRef (соответствуют глобальному и полиморфному состоянию) двойственны MoncadCont (соответствуют глобальным и полиморфным продолжениям), и поэтому их можно использовать для реализации друг друга.