Продолжение прохождения стиль против монад

Каковы различия между продолжением прохождения стиля (cps) и монады.

Источник

4 ответа

Решение

Как уже упоминалось в сущности функционального программирования:

Программирование с использованием монад сильно напоминает стиль продолжения - прохождения (CPS), и в этой статье рассматривается взаимосвязь между ними. В некотором смысле они эквивалентны: CPS возникает как особый случай монады, и любая монада может быть встроена в CPS путем изменения типа ответа. Но монадический подход обеспечивает дополнительное понимание и позволяет более точную степень контроля.

Эта статья довольно строгая, и на самом деле она не раскрывает отношения между CPS и монадами. Здесь я попытаюсь привести неофициальный, но наглядный пример:

(Примечание: ниже дано понимание Monad от новичка (меня самого), хотя после написания он выглядит как ответ одного из пользователей с высокими репутациями. Пожалуйста, возьмите его с тонной соли)

Рассмотрим классику Maybe монада

-- I don't use the do notation to make it 
-- look similar to foo below

bar :: Maybe Int
bar =
    Just 5 >>= \x ->
    Just 4 >>= \y ->
    return $ x + y

bar' :: Maybe Int
bar' =
    Just 5 >>= \x ->
    Nothing >>= \_ ->
    return $ x

GHCi> bar
Just 9
GHCi> bar'
Nothing

Таким образом, вычисление останавливается, как только Nothing встречается, ничего нового здесь. Давайте попробуем имитировать такое монадическое поведение, используя CPS:

Вот наша ваниль add функция с использованием CPS. Мы используем все Int здесь вместо алгебраического типа данных сделать это проще:

add :: Int -> Int -> (Int -> Int) -> Int
add x y k = k (x+y)

GHCi> add 3 4 id
7

Обратите внимание, насколько это похоже на монаду

foo :: Int
foo =
    add 1 2 $ \x -> -- 3
    add x 4 $ \y -> -- 7
    add y 5 $ \z -> -- 12
    z

GHCi> foo
12

ХОРОШО. Предположим, что мы хотим, чтобы вычисление было ограничено 10. То есть, любое вычисление должно быть остановлено, когда следующий шаг приведет к значению, большему 10. Это похоже на выражение "вычисление Maybe должно остановиться и вернуться Nothing как только любое значение в цепочке Nothing). Давайте посмотрим, как мы можем сделать это, написав "CPS трансформер"

cap10 :: (Int -> Int) -> (Int -> Int)
cap10 k = \x ->
    if x <= 10 
    then 
        let x' = k x in 
        if x' <= 10 then x' else x
    else x

foo' :: Int
foo' =
    add 1 2 $ cap10 $ \x -> -- 3
    add x 4 $ cap10 $ \y -> -- 7
    add y 5 $ cap10 $ \z -> -- 12
    undefined

GHCi> foo'
7

Обратите внимание, что окончательное возвращаемое значение может быть undefined, но это нормально, потому что оценка останавливается на 3-м шаге (z).

Мы это видим cap10 "оборачивает" нормальное продолжение некоторой дополнительной логикой. И это очень близко к тому, что монада - склеить вычисления вместе с некоторой дополнительной логикой.

Давайте сделаем еще один шаг вперед:

(>>==) :: ((Int -> Int) -> Int) -> (Int -> Int) -> Int
m >>== k = m $ cap10 k

foo'' :: Int
foo'' =
    add 1 2 >>== \x -> -- 3
    add x 4 >>== \y -> -- 7
    add y 5 >>== \z -> -- 12
    undefined

GCHi> foo''
7

Woa! Может быть, мы только что изобрели Cap10 Монада!

Теперь, если мы посмотрим на исходный код Cont, мы увидим, что Cont является

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

Тип runCont является

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

Что хорошо сочетается с типом нашего >>==

Теперь, чтобы действительно ответить на вопрос

Теперь, набрав все это, я перечитал оригинальный вопрос. ОП попросила "разницу":P

Я думаю, разница в том, что CPS дает звонящему больше контроля, где, как обычно, >>= в монаде полностью контролируется автором монады.

Источник

Возможно, вы захотите взглянуть на этот http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

Источник

Интересная статья, которая исследует проблему, - "Императивное функциональное программирование", Пейтон Джонс и Уодлер.

Это документ, который ввел монадический ввод-вывод, и в нем есть сравнение с альтернативными подходами, включая CPS.

Авторы делают вывод:

Так что монады более мощные, чем продолжения, но только из-за типов! Не ясно, является ли это только артефактом системы типов Хиндли-Милнера, или же типы обнаруживают разницу фундаментальной важности (наша собственная интуиция - последняя, ​​но это только интуиция).

Источник

Здесь нет никакой связи, поэтому вопрос имеет такой же смысл, как вопрос о разнице между синим цветом и Плутоном.

Источник
Другие вопросы по тегам