82

これは、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

これがどのように、そしてなぜ機能するのか説明していただけますか？何してるの？

4

5 に答える 5

129

継続モナドについて最初に気付くことは、基本的に、それは実際には何もしていないということです。それは本当です！

一般的な継続の基本的な考え方は、それが残りの計算を表すということです。次のような式があるとしますfoo (bar x y) z。ここで、括弧で囲まれた部分だけを抽出します -- これbar x yは式全体の一部ですが、適用できる関数だけではありません。代わりに、関数をに適用する必要があります。したがって、この場合の「残りの計算」は で\a -> foo a zあり、これを適用しbar x yて完全な形式を再構築できます。

さて、この「残りの計算」という概念は便利ですが、検討している部分式の外にあるものであるため、扱いにくい場合があります。物事をよりうまく機能させるために、物事を裏返しにすることができます: 関心のある部分式を抽出し、残りの計算を表す引数を取る関数でラップします: \k -> k (bar x y).

この変更されたバージョンにより、多くの柔軟性が得られます。コンテキストから部分式を抽出するだけでなく、部分式自体の外部コンテキストを操作できます。これは一種の中断された計算と考えることができ、次に何が起こるかを明示的に制御できます。では、これを一般化するにはどうすればよいでしょうか。\x k -> k xさて、部分式はほとんど変更されていないので、それをインサイドアウト関数へのパラメーターに置き換えてみましょう。同様に簡単に書くこともできflip ($)ますし、エキゾチックな外国語風味を少し加えて、それを演算子として定義することもできます|>。

さて、式のすべての部分をこの形式に変換するのは、退屈で恐ろしく難読化されますが、簡単です。幸いなことに、もっと良い方法があります。Haskell プログラマーとして、バックグラウンド コンテキスト内で計算を構築することを考えるとき、次に考えるのは、これはモナドか? ということです。この場合、答えはイエスです。

これをモナドに変換するには、2 つの基本的な構成要素から始めます。

  • モナドmの場合、 typeの値は、モナドのコンテキスト内m aで type の値にアクセスできることを表します。a
  • 私たちの「中断された計算」の核心は、反転された関数の適用です。

aこのコンテキスト内でタイプのあるものにアクセスできるとはどういう意味ですか? これは単に、ある値x :: aに対して を適用flip ($)しx、タイプ の引数を取る関数を受け取る関数を与え、aその関数を に適用することを意味しますx。type の値を保持する中断された計算があるとしますBool。これは私たちにどのようなタイプを与えますか?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

したがって、中断された計算の場合、型は ...のm aように機能します。(a -> b) -> bCont

ここで注目すべき興味深い点は、一種の「反転」がモナドの型にも適用されるというCont b aことa -> bですb。継続が計算の「未来」を表すようaに、署名の型はある意味で「過去」を表します。

では、逆関数アプリケーションの基本的なビルディング ブロックのモナド型(a -> b) -> bはCont b a何でしょうか? a -> (a -> b) -> bに変換されa -> Cont b aます ... と同じ型シグネチャでreturnあり、実際、それはまさにそれです。

>>=ここから先は、ほとんどすべてが型から直接派生します。実際の実装以外に実装する賢明な方法は本質的にありません。しかし、それは実際に何をしているのでしょうか?

この時点で、最初に言ったことに戻ります。継続モナドは実際には何もしていません。type の何かは、一時停止された計算に引数として指定するだけCont r aで、単なる type の何かと自明に同等です。これは、 がモナドであるが、変換が非常に些細なことである場合、単独でもモナドであるべきではないかという疑問につながるかもしれません。もちろん、インスタンスとして定義する型コンストラクターがないため、そのままでは機能しませんが、 のような単純なラッパーを追加するとします。これは確かにモナド、すなわち恒等モナドです。aidCont r aaMonaddata Id a = Id a

恒等モナドに対して何>>=をしますか? 型シグネチャはであり、これは単純な関数適用でId a -> (a -> Id b) -> Id bある と同等です。が と自明に等価であることa -> (a -> b) -> bを確立したので、この場合も同様に、関数適用だけであると推測できます。Cont r aId a(>>=)

もちろん、Cont r a誰もがあごひげを生やしているクレイジーな反転世界なので、実際に起こることは、中断された 2 つの計算を新しい中断された計算に連鎖させるために混乱した方法で物事をシャッフルすることですが、本質的には、実際には異常なことは何も起こっていません。の上！関数を引数に適用する、ふむふむ、関数型プログラマーの人生の別の日。

于 2010-07-23T23:39:05.633 に答える
45

フィボナッチは次のとおりです。

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

コール スタックのないマシンがあると想像してください。末尾再帰のみが許可されます。fibそのマシンで実行する方法は？指数時間ではなく線形で機能するように関数を簡単に書き直すことができますが、それには少しの洞察が必要であり、機械的ではありません。

末尾再帰にする際の障害は、2 つの再帰呼び出しがある 3 行目です。呼び出しは 1 回しかできず、結果も返さなければなりません。ここから継続に入ります。

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)に適用する」、ここで. コード内:ee yc (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)

実際のフィボナッチ使用 ID を取得するには: fib' n id. fib (n-1) $ ...行はその結果を次の行に渡すと考えることができますx。

最後の3行はdo塊の匂いがして、実は

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

は、モナドの定義により、newtypes まで同じContです。違いに注意してください。の代わりにandの代わりに\c ->、先頭にあります。x <- ...... $ \x ->creturn

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

取得した newtype の追加

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)

続きそうです！実際、(>>=)1 つの引数を適用すると、型(a -> m b) -> m bは になりCont (m b) aます。説明については、 sigfpe の全モナドの母を参照してください。私はそれを良い継続モナドのチュートリアルだと考えていますが、おそらくそのように意図されたものではありませんでした.

継続とモナドは両方向で非常に強く関連しているため、モナドに当てはまることは継続にも当てはまると思います。ハードワークだけがそれらを教えてくれます。ブリトーの比喩やアナロジーを読む必要はありません。

于 2010-07-25T22:16:23.153 に答える
18

編集:記事は以下のリンクに移行されました。

このトピックに直接対処するチュートリアルを作成しました。これが役立つことを願っています。(確かに私の理解を深めるのに役立ちました!) スタック オーバーフローのトピックに収まるには少し長すぎるので、Haskell Wiki に移行しました。

参照してください:内部の MonadCont

于 2010-07-24T00:29:23.083 に答える
9

Contモナドを理解する最も簡単な方法は、そのコンストラクターの使い方を理解することだと思います。transformersパッケージの実際は少し異なりますが、ここでは次の定義を想定します。

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

これは与える：

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

したがって、 type の値を構築するCont r aには、関数を に与える必要がありますCont。

value = Cont $ \k -> ...

現在、kそれ自体が typea -> rを持っており、ラムダの本体には type が必要rです。行うべき明白なことは、 type の値に適用kして、 typeaの値を取得することですr。はい、それはできますが、それは私たちができる多くのことの1つにすぎません. ではポリモーフィックであるvalue必要はありません。rタイプCont String Integerまたはその他の具体的なものである可能性があります。そう：

  • ktype のいくつかの値に適用しa、何らかの方法で結果を組み合わせることができます。
  • ktype の値に適用しa、結果を観察してkから、それに基づいて別のものに適用することを決定できます。
  • k完全に無視して、型の値をr自分で生成することもできます。

しかし、これはどういう意味ですか？結局何kになるの？do ブロックでは、次のようなものがあるかもしれません。

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

ここが楽しい部分です: 私たちの頭の中で、やや非公式に、Contコンストラクターの出現時に do ブロックを 2 つに分割し、その後の残りの計算全体をそれ自体の値と考えることができます。しかし、待ってください、それが何であるかは内容に依存するxため、実際には型の値から何らかの結果値への関数です:xa

restOfTheComputation x = do
  thing3 x
  thing4

実際、これrestOfTheComputationは大まかに言えば、最終的にどうなるかkです。言い換えれば、計算の結果となる値で呼び出し、k残りの計算が実行され、生成された が への呼び出しの結果としてラムダに戻ります。そう：xContrk

  • 複数回呼び出した場合k、残りの計算は複数回実行され、結果は任意に組み合わせることができます。
  • まったく呼び出さなかった場合k、計算全体の残りはスキップされ、外側の呼び出しは、合成に成功したrunCont型の値を返すだけです。rつまり、計算の他の部分が彼らのからあなたを呼び出していて、結果をいじっていない限り... k

この時点でまだ私と一緒にいるなら、これが非常に強力であることが簡単にわかるはずです. 少しポイントを作るために、いくつかの標準型クラスを実装しましょう。

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

type のContbind result を持つ value とfunctionが与えられ、typeの bind result を持つ値を作成したいとします。さて、バインド結果を設定するには、呼び出すだけです...xaf :: a -> bContf xbk

  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 -> ...

これは簡単です。バインド結果が得られるものになるようにしxます。

  pure x = Cont $ \k -> k x

今、<*>：

  Cont cf <*> Cont cx = Cont $ \k -> ...

Contこれは少しトリッキーですが、基本的に fmap と同じ考え方を使用します。最初に呼び出すラムダを作成して、最初の から関数を取得します。

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

次にx、秒から値を取得しfn x、バインド結果を作成します。

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

MonadrunContnewtype を展開するには、require または case または letが必要ですが、ほとんど同じです。

この答えはすでにかなり長いので、ここには立ち入りませんContT(要するに: とまったく同じContです! 唯一の違いは型コンストラクターの種類であり、すべての実装は同じです) またはcallCC(便利なコンビネーターを無視する便利な方法を提供しk、サブブロックからの早期終了を実装します)。

シンプルで妥当なアプリケーションについては、Edward Z. Yang のブログ投稿でラベル付きの break と continue を for ループに実装してみてください。

于 2012-09-04T23:35:58.377 に答える