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

Question

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

Answer 1

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

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

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

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

Рассмотрим классику 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 Nothing Как только какое -либо значение в цепочке Nothing) Давайте посмотрим, как мы можем сделать это, написав «CPS Transformer»

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

Уа! Может быть, мы только что изобрели Cap10 МОНАД!

Теперь, если мы посмотрим на исходный код продолжения, Мы видим, что 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 дает вызывающему абоненту больше контроля, где обычно >>= В монаде полностью контролируется автором Монады.

Answer 2

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

Answer 3

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

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

Авторы заключают:

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

Answer 4

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