Сдвиг монады

Question

Пытаясь построить интуицию для монадного трансформатора ContT, я (возможно, неудивительно) смутился. Проблема заключается в операции shiftT, которая, кажется, не делает ничего полезного.

Сначала упрощенный пример того, как его можно использовать

shiftT $ \famr -> lift $ do
  a <- calculateAFromEnvironment
  famr a

famr a может быть более сложным выражением, если оно возвращает m r, Теперь попытка объяснить мою интуицию о том, что shiftT ничего не добавляет:

-- inline shiftT
ContT (\f2 -> evalContT ((\f1 -> lift (do
  a <- calculateAFromEnvironment
  f1 a)) f2))

-- beta reduction
ContT (\f2 -> evalContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)))

-- inline evalConT
ContT (\f2 -> runContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)) return)

-- inline lift
ContT (\f2 -> runContT (ContT (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3)) return)

-- apply runConT
ContT (\f2 -> (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3) return)

-- beta reduce
ContT (\f2 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= return)

-- (>>= return) is identity
ContT $ \f2 -> do
  a <- calculateAFromEnvironment
  f2 a

Оказывается, мы могли бы просто создать ContT напрямую.

Время вопроса: Есть ли ситуация, когда shift/shiftT добавляет что-либо поверх cont/ContT? Или они просто используются, чтобы сделать код более читабельным?

Answer 1

После поиска github по Gurkenglas я обнаружил это очень хорошее объяснение shiftT а также resetT с примерами употребления, мотивации и семантики!

Эти функции очень просты. Их определение в transformers Библиотека проста:

resetT :: (Monad m) => ContT r m r -> ContT r' m r
resetT = lift . evalContT

shiftT :: (Monad m) => ((a -> m r) -> ContT r m r) -> ContT r m a
shiftT f = ContT (evalContT . f)

Но философия и смысл далеко позади некоторого интуитивного понимания. Поэтому я рекомендую вам прочитать объяснение по ссылке выше. Иногда бывает так, что вещи, которые легко определить, могут сделать что-то сложное.

Адаптированная документация из объяснений в мопсах, связанных выше:

shiftT

shiftT как callCC за исключением того, что при активации продолжения предусмотрено shiftT, он побежит до конца ближайшего вложения resetT, затем вернитесь к точке, после которой вы активировали продолжение. Обратите внимание, что, поскольку управление в конечном итоге возвращается к точке после активации продолжения, его можно активировать несколько раз в одном и том же блоке. Это непохоже callCC Продолжения, которые отбрасывают текущий путь выполнения при активации.

Увидеть resetT для примера того, как на самом деле работают эти разделенные продолжения.

resetT

Создайте область, которая shiftT Субконтинуации гарантированно завершатся в конце. Рассмотрим этот пример:

resetT $ do
    alfa
    bravo
    x <- shiftT $ \esc -> do   -- note: esc :: m Int, not a ContT
       charlie
       lift $ esc 1
       delta
       lift $ esc 2
       return 0
    zulu x

Это будет:

1. выполнять alfa

2. выполнять bravo

3. выполнять charlie

4. привязывать x до 1, и, таким образом, выполнить zulu 1

5. Упасть с конца resetT и вернуться к сразу после esc 1

6. выполнять delta

7. привязывать x до 2, и, таким образом, выполнить zulu 2

8. Упасть с конца resetT и вернуться к сразу после esc 2

9. Убежать от resetT, в результате чего это приводит к 0

Таким образом, в отличие от callCC Продолжение, эти субконтинунии в конечном итоге вернутся к точке после того, как они активируются, после падения с конца ближайшего resetT,

Answer 2

Вы правы в том, что продолжения с разделителями можно выразить с помощью неограниченных продолжений. Так что определения shiftT а также resetT всегда можно описать, используя только ContT, Но:

• Продолжения с разделителями являются менее мощными. Это облегчает их реализацию, а также рассуждает о людях. (Смотрите также много других интересных постов о продолжениях от Олега Киселева).
• Использование знакомых обозначений сдвига / сброса облегчает понимание, особенно для тех, кто знаком с концепцией.

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

Давайте сделаем несколько примеров:

import Data.List
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Cont

test0 :: Integer
test0 = evalCont . reset $ do
    return 0

Если у нас есть reset без shiftЭто просто чистое вычисление, ничего особенного. Вышеуказанная функция просто возвращает 0,

Теперь давайте использовать их обоих:

test1 :: Integer
test1 = evalCont . reset $ do
    r <- shift $ \esc -> do
        let x = esc 2
            y = esc 3
        return $ x * y
    return $ 1 + r

Это становится более интересным. Код между shift а также reset на самом деле втиснут в вызовы escв этом простом примере это просто return $ 1 + r, Когда мы призываем esc, все вычисления выполняются, и его результат становится результатом esc вызов. Мы делаем это дважды, поэтому, по сути, мы вызываем все между shift а также reset дважды. И результат всего вычисления result $ x * y, результат shift вызов.

Таким образом, в некотором смысле, shift блок становится внешней частью вычисления и блок между reset а также shift становится внутренней частью вычисления.

Все идет нормально. Но это становится еще более пугающим, если мы призываем shift дважды, как в этом примере кода:

list2 :: [(Int, String)]
list2 = evalCont . reset $ do
    x <- shift $ \yieldx ->
        return $ concatMap yieldx [1, 2, 3]
    y <- shift $ \yieldy ->
        return $ concatMap yieldy ["a", "b", "c"]
    return [(x, y)]

И вот что он производит (скрыто для тех, кто хочет попытаться понять это как упражнение):

[(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c")]

Теперь происходит то, что программа выворачивается наизнанку дважды:

1. Сначала все за пределами x <- shift ... блок связан с yieldx звонок, в том числе следующий shift, И результат вычисления является результатом x <- shift ... блок.
2. Во-вторых, при вызове второго y <- shift ... внутри yieldxопять же остальная часть вычисления связана с yieldy вызов. И результат этого внутреннего вычисления является результатом y <- shift ... блок.

Так в x <- shift мы выполняем оставшуюся часть вычисления для каждого из трех аргументов, и во время каждого из них мы делаем аналогичную вещь для каждого из трех других аргументов. В результате получается декартово произведение двух списков, поскольку мы, по сути, выполнили два вложенных цикла.

То же самое относится и к shiftT а также resetTПросто с добавленными побочными эффектами. Например, если мы хотим отладить то, что на самом деле происходит, мы можем запустить приведенный выше код в IO Монады и распечатки отладочных операторов:

list2' :: IO [(Int, String)]
list2' = evalContT . resetT $ do
    x <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ [1, 2, 3]
    y <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ ["a", "b", "c"]
    return [(x, y)]