Вот как определяется монада 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. Теперь извлеките только заключенную в скобки часть _2 _ - это часть всего выражения, но это не просто функция, которую мы можем применить. Вместо этого нам нужно применить функцию к. Итак, мы можем говорить об «остальной части вычислений» в этом случае как о \a -> foo a z, которые мы можем применить к bar x y, чтобы восстановить полную форму.
Бывает, что эта концепция «остальной части вычислений» полезна, но с ней неудобно работать, поскольку это что-то за пределами рассматриваемого подвыражения. Чтобы все работало лучше, мы можем вывернуть все наизнанку: извлечь интересующее нас подвыражение, а затем обернуть его в функцию, которая принимает аргумент, представляющий остальную часть вычисления: \k -> k (bar x y).
Эта модифицированная версия дает нам большую гибкость - она не только извлекает подвыражение из своего контекста, но и позволяет нам управлять этим внешним контекстом внутри самого подвыражения. Мы можем рассматривать это как своего рода приостановленное вычисление, дающее нам явный контроль над тем, что произойдет дальше. Итак, как мы можем это обобщить? Что ж, подвыражение практически не изменилось, поэтому давайте просто заменим его параметром вывернутой наизнанку функции, что даст нам _6 _-- другими словами, не что иное, как приложение функции, перевернутое. Мы могли бы так же легко написать flip ($) или добавить немного экзотического иностранного языка и определить его как оператор |>.
Теперь было бы просто, хотя и утомительно и ужасно запутать, перевести каждую часть выражения в эту форму. К счастью, есть способ получше. Как программисты Haskell, когда мы думаем о построении вычислений в фоновом контексте, следующее, что мы думаем, это скажем, это монада? И в этом случае ответ будет <сильный > да, да, это так.
Чтобы превратить это в монаду, мы начнем с двух основных строительных блоков:
m значение типа m a представляет наличие доступа к значению типа a в контексте монады.Что значит иметь доступ к чему-то типа a в этом контексте? Это просто означает, что для некоторого значения x :: a мы применили flip ($) к x, дав нам функцию, которая принимает функцию, которая принимает аргумент типа a, и применяет эту функцию к x. Допустим, у нас есть приостановленное вычисление, содержащее значение типа Bool. Какой тип это дает нам?
> :t flip ($) True
flip ($) True :: (Bool -> b) -> b
Итак, для приостановленных вычислений тип m a работает до _21 _..., что, возможно, является препятствием, поскольку мы уже знали сигнатуру для Cont, но пока меня посмешите.
Здесь интересно отметить, что своего рода «разворот» также применяется к типу монады: Cont b a представляет функцию, которая принимает функцию a -> b и оценивает ее как b. Поскольку продолжение представляет «будущее» вычисления, так и тип a в сигнатуре в некотором смысле представляет «прошлое».
Итак, заменив (a -> b) -> b на Cont b a, какой монадический тип у нашего основного строительного блока приложения обратной функции? a -> (a -> b) -> b переводится в _30 _... сигнатура того же типа, что и 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 - это сумасшедший перевернутый мир, в котором у всех есть козлиные бородки, поэтому на самом деле происходит путаница в путанице, чтобы связать два приостановленных вычисления вместе в новое приостановленное вычисление, но, по сути, здесь нет на самом деле происходит что-то необычное! Применение функций к аргументам, хх, еще один день в жизни функционального программиста.
flip ($) a как ($ a).
- person Reuben Steenekamp; 11.04.2020
Вот фибоначчи:
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. Я бы счел это хорошим продолжением учебника по монаде, хотя, вероятно, это не так.
Поскольку продолжения и монады так сильно связаны в обоих направлениях, я думаю, что то, что применимо к монадам, применимо и к продолжениям: только упорный труд научит вас им, а не чтение какой-нибудь метафоры или аналогии с буррито.
where e y = c (x+y)
- person Thomas Eding; 24.12.2019
РЕДАКТИРОВАТЬ: статья перенесена по ссылке ниже.
Я написал учебник, непосредственно посвященный этой теме, и надеюсь, вы найдете его полезным. (Это определенно помогло укрепить мое понимание!) Это слишком долго, чтобы удобно разместиться в теме о переполнении стека, поэтому я перенес ее в 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-блоке у нас может быть что-то вроде этого:
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. Что ж, чтобы установить результат привязки, просто вызовите _51 _...
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 -> ...
Это просто. Мы хотим, чтобы результат привязки был таким, который мы получаем.
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, реализуя ранний выход из подблока).
Для простого и правдоподобного приложения попробуйте сообщение в блоге Эдварда З. Янга, в котором реализован помеченный прервать и продолжить для петель.
Попытка дополнить другие ответы:
Вложенные лямбды ужасны для удобочитаемости. Именно по этой причине let ... in ... and ... where ... exists, чтобы избавиться от вложенных лямбда-выражений с помощью промежуточных переменных. Используя их, реализация привязки может быть преобразована в:
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
instance Monad (Cont r) where
return a = Cont ($ a)
m >>= k = k a
where a = runCont m id
Что, надеюсь, проясняет происходящее. Реализация возврата возвращает значение коробки с ленивым применением. Использование runCont id применяет id к упакованному значению, которое возвращает исходное значение.
Для любой монады, где любое упакованное значение может быть просто распаковано, обычно существует тривиальная реализация связывания, которая заключается в том, чтобы просто распаковать значение и применить к нему монадическую функцию.
Чтобы получить запутанную реализацию в исходном вопросе, сначала замените k a на Cont $ runCont (k a), которое, в свою очередь, можно заменить на Cont $ \ c-> runCont (k a) c
Теперь мы можем переместить where в подвыражение, чтобы у нас осталось
Cont $ \c-> ( runCont (k a) c where a = runCont m id )
Выражение в круглых скобках может быть уменьшено до \ a -> runCont (k a) c $ runCont m id.
В завершение мы используем свойство runCont, f (runCont m g) = runCont m (f.g), и возвращаемся к исходному запутанному выражению.
