27

継続渡しスタイル (cps) とモナドの違いは何ですか。

4

4 に答える 4

31

関数型プログラミングの本質 で述べたように：

モナドを使ったプログラミングは、継続 - 受け渡しスタイル (CPS) を強く連想させます。この論文では、この 2 つの関係を探ります。ある意味ではそれらは同等です: CPS はモナドの特殊なケースとして発生し、回答の型を変更することで任意のモナドを CPS に埋め込むことができます。しかし、モナドのアプローチは追加の洞察を提供し、より細かい制御を可能にします。

その論文は非常に厳密であり、実際には CPS とモナドの間の関係をあまり拡張していません。ここで、非公式ではあるが実例となる例を挙げようとします:

（注：以下は初心者（私自身）からのモナドの理解ですが、それを書いた後、それはそれらの高評価ユーザーの答えの1つのように見えます.たくさんの塩でそれを取ってください）

古典的な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簡単にするために、ここでは代数データ型の代わりにall を使用しています。

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 トランスフォーマー" を作成して、どのようにそれを行うことができるか見てみましょう。

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のソースコードを見るとCont、

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

のタイプrunContは

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

これは私たちのタイプとうまく一致します>>==

実際に質問に答える

これをすべて入力した後、元の質問を読み直しました。OPは「違い」を求めました：P

>>=違いは、通常、モナド内の はモナドの作成者によって完全に制御されるのに対し、CPS は呼び出し元により多くの制御を与えることだと思います。

于 2011-08-07T16:58:06.507 に答える
9

これを見たいと思うかもしれませんhttp://blog.sigfpe.com/2008/12/mother-of-all-monads.html

于 2011-03-12T16:15:27.207 に答える
5

この問題を調査する興味深い論文は、Peyton Jones と Wadler による「命令型関数型プログラミング」です。

これはモナディック IO を紹介した論文であり、CPS を含む代替アプローチとの比較があります。

著者は次のように結論付けています。

したがって、モナドは継続よりも強力ですが、それは型のためだけです! これが Hindley-Milner 型システムの人工物にすぎないのか、それとも型が根本的な重要性の違いを明らかにしているのかは明らかではありません (私たち自身の直感では後者ですが、それは単なる直感です)。

于 2011-08-08T08:44:33.303 に答える
-12

関係はありません。したがって、この質問は青色と冥王星の違いについて尋ねるのと同じくらい理にかなっています。

于 2010-12-24T16:59:48.783 に答える