継続パッシングスタイルとモナド

StackOverflow https://stackoverflow.com/questions/4525919

質問

継続パッシングスタイル（CPS）とモナドの違いは何ですか。

役に立ちましたか？

解決

で述べたように 機能プログラミングの本質:

継続を強く連想させるモナドとのプログラミング - パススタイル（CPS）。このペーパーでは、2つの関係を調査します。ある意味では、それらは同等です。CPSはモナドの特別なケースとして発生し、回答タイプを変更することによりMONADがCPSに埋め込まれる場合があります。しかし、モナディックアプローチは追加の洞察を提供し、より細かい程度の制御を可能にします。

その論文は非常に厳格であり、実際にはCPSとMonadsの関係を完全に拡大していません。ここで私は非公式の、しかし実例を与えようとします：

（注：以下は初心者（私自身）からのMonadの理解ですが、それを書いた後は、それらの高いユーザーの答えの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 ここでは、代数的なデータ型の代わりに、それを容易にする：

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 いくつかの追加のロジックで通常の継続を「ラップ」します。そして、それはMonadに非常に近いです - いくつかの追加のロジックと一緒に計算を接着します。

さらに一歩行きましょう：

(>>==) :: ((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

私たちのタイプとうまく並んでいます >>==

今、実際に質問に答えるために

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

違いは、CPSが発信者により多くのコントロールを与えることだと思います。 >>= モナドでは、モナドの著者によって完全に制御されています。

他のヒント

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

問題を探る興味深い論文 「命令的な機能プログラミング」, 、ペイトン・ジョーンズとワドラー。

Monadic IOを導入したのは論文であり、CPSを含む代替アプローチと比較しています。

著者は結論付けています：

したがって、モナドは継続よりも強力ですが、それはタイプのためだけです！これがHindley-Milnerタイプシステムのアーティファクトにすぎないのか、それともタイプが根本的な重要性の違いを明らかにしているのかは明らかではありません（私たち自身の直感は後者ですが、直感です。）

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top