Таким образом определяется монада 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
Не могли бы вы объяснить, как и почему это работает? Что он делает?
Первое, что нужно знать о продолжении монады, состоит в том, что, в сущности, это вообще ничего не делает. Это правда!
Основная идея продолжения вообще состоит в том, что она представляет собой остальную часть вычисления. Скажем, у нас есть такое выражение: 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 - сумасшедший перевернутый мир, в котором у всех есть бородки, так что на самом деле происходит перетасовка вещей в путаных целях, чтобы связать два взвешенных вычисления вместе с новым взвешенным вычислением, но по существу, там на самом деле ничего необычного не происходит! Применение функций к аргументам, ho hum, еще один день в жизни функционального программиста.
Вот Фибоначчи:
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' nc= вычислить fib n и применить c к результату"?
Ответ заключается в следующем: "вычислить fib (n-1) и применить d к результату", где dx означает "вычислить fib (n-2) и применить e к результату", где ey означает 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 → ct до c
m >>= k = \c -> m $ \a -> k a c
Добавляя новые типы, вы получаете
m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c
который находится на вершине этой страницы. Это сложно, но если вы знаете, как перевести между 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 → mb) → mb который является Cont (mb) a. Смотрите sigfpe Мать всех монад для объяснения. Я бы посчитал это хорошим уроком по продолжению монады, хотя, вероятно, это не так.
Поскольку продолжения и монады так сильно связаны в обоих направлениях, я думаю, что то, что относится к монадам, применимо и к продолжениям: их научит только тяжелая работа, а не чтение метафоры буррито или аналогии.
EDIT: Статья перенесена на ссылку ниже.
Я написал учебник, непосредственно обращаясь к этой теме, надеюсь, что вы найдете полезным. (Это, безусловно, помогло цементировать мое понимание!) Это слишком долго, чтобы удобно входить в тему, поэтому я перенес его в Haskell Wiki.
Смотрите: MonadCont под капотом
Я думаю, что самый простой способ захватить монаду 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-block у нас может быть что-то похожее:
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, которое вам удалось синтезировать. То есть, если какая-либо другая часть вычисления не вызовет вас из их 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, в котором помечен как разрыв и продолжен для циклов.