Как и почему работает монада Haskell Cont?

Question

Вот как определяется монада Cont:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

Не могли бы вы объяснить, как и почему это работает? Что он делает?

Answer 1

Первое, что нужно понять о монаде продолжения, это то, что, по сути, на самом деле ничего не делает вообще.Это правда!

Основная идея продолжения в целом состоит в том, что оно представляет остальную часть вычисления .Скажем, у нас есть такое выражение: foo (bar x y) z.Теперь извлеките только часть в скобках, bar x y - это часть всего выражения, но это не просто функция, которую мы можем применить.Вместо этого нам нужно применить функцию к .Таким образом, мы можем говорить об «остальной части вычисления» в этом случае как о \a -> foo a z, который мы можем применить к bar x y для восстановления полной формы.

Теперь, случается, что это понятие«Остальная часть вычислений» полезна, но работать с ней неудобно, поскольку это нечто за пределами подвыражения, которое мы рассматриваем.Чтобы заставить вещи работать лучше, мы можем вывернуть вещи наизнанку: извлечь интересующее нас подвыражение, а затем обернуть его в функцию, которая принимает аргумент, представляющий остальную часть вычисления: \k -> k (bar x y).

Эта измененная версия дает нам большую гибкость - она ​​не только извлекает подвыражение из своего контекста, но и позволяет манипулировать этим внешним контекстом внутри самого подвыражения .Мы можем думать об этом как о как о приостановленном вычислении , что дает нам явный контроль над тем, что происходит дальше.Теперь, как мы можем обобщить это?Что ж, подвыражение практически не изменилось, поэтому давайте просто заменим его параметром для функции наизнанку, что даст нам \x k -> k x - другими словами, не более чем приложение функции, в обратном порядке .Мы могли бы так же легко написать flip ($) или добавить немного экзотического иноязычного аромата и определить его как оператор |>.

Теперь это было бы просто, хотя и утомительно и ужасно запутанно,переведите каждый фрагмент выражения в эту форму.К счастью, есть лучший способ.Как программисты на Haskell, когда мы думаем построение вычислений в фоновом контексте , следующее, что мы думаем, это Скажите, это монада? И в этом случае ответ да, да, это так.

Чтобы превратить это в монаду, мы начнем с двух основных строительных блоков:

• Для монады m, значение типа m a означает наличие доступа к значению типа a в контексте монады.
• Ядром наших «приостановленных вычислений» является перевернутое приложение-функция.

Что делаетэто значит иметь доступ к чему-то типа a в этом контексте?Это просто означает, что для некоторого значения x :: a мы применили flip ($) к x, что дает нам функцию, которая принимает функцию, которая принимает аргумент типа a, и применяет эту функцию к x,Допустим, у нас есть приостановленное вычисление, содержащее значение типа Bool.Какой тип это нам дает?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

Так что для приостановленных вычислений тип m a работает до (a -> b) -> b ... что, возможно, является антиклимаксом, так как мы уже знали сигнатуру для Cont, но покажите мне.

Интересно отметить, что своего рода «обращение» также применимо к типу монады: Cont b a представляет функцию, которая принимает функцию a -> b и оцениваетдо b.Как продолжение представляет «будущее» вычислений, так и тип a в сигнатуре представляет в некотором смысле «прошлое».

Итак, заменяя (a -> b) -> b на Cont b a, что является монадическимтип для нашего основного строительного блока приложения обратной функции?a -> (a -> b) -> b переводит в a -> Cont b a ... ту же сигнатуру типа, что и return, и, фактически, это именно то, что она есть.

С этого момента все в значительной степени выпадает непосредственно из типов: По сути, нет никакого разумного способа реализации >>=, кроме фактической реализации.Но что на самом деле делает ?

В этот момент мы возвращаемся к тому, что я сказал изначально: монада продолжения на самом деле не делает ничего. Нечто типа Cont r a тривиально эквивалентно чему-то типа a, просто предоставляя id в качестве аргумента для приостановленного вычисления. Это может привести к тому, что, если Cont r a является монадой, но преобразование настолько тривиально, не должно ли a в одиночку также быть монадой? Конечно, это не работает как есть, поскольку нет конструктора типа, который можно определить как экземпляр Monad, но, скажем, мы добавляем тривиальную оболочку, например data Id a = Id a. Это действительно монада, а именно монада идентичности.

Что >>= делает для монады идентификации? Сигнатура типа Id a -> (a -> Id b) -> Id b, что эквивалентно a -> (a -> b) -> b, что снова является простым приложением функции. Установив, что Cont r a тривиально эквивалентно Id a, мы можем сделать вывод, что и в этом случае (>>=) является просто приложением функции .

Конечно, Cont r a - это сумасшедший перевернутый мир, в котором у всех есть бородки, поэтому то, что происходит на самом деле, включает в себя путаницу вещей в замешательстве, чтобы соединить два приостановленных вычисления в новое приостановленное вычисление, но, по сути, там 1109 * на самом деле ничего необычного не происходит! Применение функций к аргументам, хо хам, еще один день из жизни функционального программиста.

Answer 2

Вот Фибоначчи:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Представьте, что у вас есть машина без стека вызовов - она ​​допускает только хвостовую рекурсию. Как выполнить fib на этой машине? Вы можете легко переписать функцию для работы в линейном, а не экспоненциальном времени, но это требует крошечного понимания и не является механическим.

Препятствием для того, чтобы сделать его хвостовым рекурсивным, является третья строка, где есть два рекурсивных вызова. Мы можем сделать только один звонок, который также должен дать результат. Вот куда входят продолжения.

Мы заставим fib (n-1) принять дополнительный параметр, который будет функцией, определяющей, что должно быть сделано после вычисления его результата, назовем его x. Конечно, это будет добавление fib (n-2). Итак: для вычисления fib n вы вычисляете fib (n-1) после этого, если вы вызываете результат x, вы вычисляете fib (n-2), после этого, если вы вызываете результат y, вы возвращаете x+y.

Другими словами, вы должны сказать:

Как выполнить следующие вычисления: «fib' n c = вычислить fib n и применить c к результату»?

Ответ заключается в следующем: «вычислить fib (n-1) и применить d к результату», где d x означает «вычислить fib (n-2) и применить e к результату», где e y означает c (x+y). В коде:

fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
           where d x = fib' (n-2) e
                 where e y = c (x+y)

Эквивалентно, мы можем использовать лямбды:

fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
               fib' (n-2) $ \y ->
               c (x+y)

Чтобы получить фактическое число Фибоначчи, используйте идентификатор: fib' n id. Вы можете думать, что строка fib (n-1) $ ... передает свой результат x следующему.

Последние три строки пахнут как do блок, а на самом деле

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

то же самое, с точностью до новых типов, по определению монады Cont. Обратите внимание на различия. В начале \c -> вместо x <- ... есть ... $ \x -> и c вместо return.

Попробуйте написать factorial n = n * factorial (n-1) в хвостовой рекурсивной манере, используя CPS.

Как работает >>=? m >>= k эквивалентно

do a <- m
   t <- k a
   return t

Сделав перевод обратно, в том же стиле, что и в fib', вы получите

\c -> m $ \a ->
      k a $ \t ->
      c t

упрощение \t -> c t до c

m >>= k = \c -> m $ \a -> k a c

Добавление новых типов, которые вы получаете

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

который находится вверху этой страницы. Это сложно, но если вы знаете, как переводить нотацию do и прямое использование, вам не нужно знать точное определение >>=! Монада продолжения гораздо понятнее, если вы посмотрите на блоки do.

Монады и продолжения

Если вы посмотрите на это использование монады списка ...

do x <- [10, 20]
   y <- [3,5]
   return (x+y)

[10,20] >>= \x ->
  [3,5] >>= \y ->
    return (x+y)

([10,20] >>=) $ \x ->
  ([3,5] >>=) $ \y ->
    return (x+y)

это выглядит как продолжение! Фактически, (>>=), когда вы применяете один аргумент, имеет тип (a -> m b) -> m b, который равен Cont (m b) a. См. Sigfpe Мать всех монад для объяснения. Я бы посчитал это хорошим уроком по продолжению монады, хотя, вероятно, он и не был таким.

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

Answer 3

РЕДАКТИРОВАТЬ: Статья перенесена по ссылке ниже.

Я написал учебник, непосредственно посвященный этой теме, который, я надеюсь, вы найдете полезным. (Это, безусловно, помогло укрепить мое понимание!) Это слишком долго, чтобы удобно вписываться в тему переполнения стека, поэтому я перенес его в Haskell Wiki.

Пожалуйста, смотрите: MonadCont под капотом

Answer 4

Я думаю, что самый простой способ получить монаду Cont - это понять, как использовать ее конструктор.Я собираюсь предположить следующее определение, хотя реалии пакета transformers немного отличаются:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Это дает:

Cont :: ((a -> r) -> r) -> Cont r a

, чтобы построитьзначение типа Cont r a, нам нужно дать функцию для Cont:

value = Cont $ \k -> ...

Теперь сам k имеет тип a -> r, а тело лямбды должно иметь тип r.Очевидное, что нужно сделать, это применить k к значению типа a и получить значение типа r.Да, мы можем сделать это, но это только одна из многих вещей, которые мы можем сделать.Помните, что value не обязательно должен быть полиморфным в r, это может быть тип Cont String Integer или что-то конкретное.Итак:

• Мы можем применить k к нескольким значениям типа a и каким-то образом объединить результаты.
• Мы можем применить k к значению типа a, понаблюдайте за результатом, а затем решите применить k к чему-то другому, основываясь на этом.
• Мы могли бы вообще игнорировать k и просто получить значение типа r сами.

Но что все это значит?Что в итоге получается k?Ну, в do-блоке у нас может быть что-то похожее на это:

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

Вот забавная часть: мы можем, в некотором смысле и неформально, разделить do-блок на две части в случае появленияконструктора Cont, и подумайте об остальной части всего вычисления после как о самом значении.Но подождите, это зависит от x, так что это действительно функция от значения x типа a до некоторого значения результата:

restOfTheComputation x = do
  thing3 x
  thing4

На самом деле, это restOfTheComputation является грубо говоря тем, чем в конечном итоге становится k.Другими словами, вы вызываете k со значением, которое становится результатом x вашего вычисления Cont, остальные вычисления выполняются, а затем полученный r возвращается в вашу лямбду в результатезвонка на k.Итак:

• , если вы вызывали k несколько раз, остальная часть вычислений будет выполняться несколько раз, и результаты могут быть объединены, как вы хотите.
• , если вы не сделаливообще не вызывайте k, остальная часть всего вычисления будет пропущена, а включающий вызов runCont просто вернет вам любое значение типа r, которое вам удалось синтезировать.То есть, если какая-то другая часть вычислений не вызывает you из их k и не возится с результатом ...

ЕслиВы все еще со мной на этом этапе, должно быть легко увидеть, что это может быть довольно мощным.Чтобы пояснить это немного, давайте реализуем некоторые стандартные классы типов.

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

Нам дано значение Cont с результатом связывания x типа a и функцией f :: a -> bи мы хотим получить значение Cont с результатом связывания f x типа b.Ну, чтобы установить результат привязки, просто позвоните k ...

  fmap f (Cont c) = Cont $ \k -> k (f ...

Подождите, откуда мы получим x?Ну, это будет включать c, который мы еще не использовали.Вспомните, как работает c: ему присваивается функция, а затем вызывается эта функция с результатом привязки.Мы хотим вызвать нашу функцию с f, примененную к этому результату связывания.Итак:

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

Тада!Далее, Applicative:

instance Applicative (Cont r) where
  pure x = Cont $ \k -> ...

Это просто.Мы хотим, чтобы результат связывания был x, который мы получили.

  pure x = Cont $ \k -> k x

Теперь, <*>:

  Cont cf <*> Cont cx = Cont $ \k -> ...

Это немного сложнее, но использует по существу те же идеив fmap: сначала получите функцию из первого Cont, сделав лямбду для ее вызова:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

Затем получите значение x из второго и сделайте fn x привязкурезультат:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad почти такой же, хотя требует runCont или кейса или разрешает распаковать новый тип.

Этот ответ уже довольно длинный, поэтому я не буду вдаваться в ContT (короче: он точно такой же, как Cont! Единственное отличие заключается в типе конструктора типов, реализациях всегоидентичны) или callCC (полезный комбинатор, предоставляющий удобный способ игнорировать k, реализующий ранний выход из подблока).

Для простого и правдоподобного приложения попробуйте Edward Z. Yang'sсообщение в блоге, в котором реализовано с надписью break и продолжение циклов .