11

この引用はどういう意味ですか?

the list functor represents a context of nondeterministic choice;

関数型プログラミングのファンクターのコンテキストで。

Functor はある種の「コンテナ」であり、構造を変更せずにコンテナ内の要素に関数を均一に適用できることを理解していると思います。したがって、失敗する可能性のあるコンテキストまたはコンテナーを表す Functor である可能性がありますが、リストが非決定論的な選択を伴うコンテキストまたはコンテナーを表すのはなぜですか?

4

5 に答える 5

11

私が知る限り、複数の可能な答えがある場合、計算は「非決定論的」です。リストには複数の可能な回答を含めることができます。だから。

(なぜそれが非決定的と呼ばれるのかについては、私にはわかりません...非決定的とはrandomを意味すると予想していましたが、これはまったく異なるものです。)

于 2012-04-18T21:13:33.377 に答える
8

従来、計算可能性と複雑さにおいて、非決定論的計算モデルはモデルを参照していました。その場合、「分岐」することができます。ウィキペディアはそれを次のように説明しています：

計算の複雑さの理論では、非決定論的アルゴリズムは、すべての可能なステップで、複数の継続を可能にするアルゴリズムです（森の中の小道を歩いている男性を想像してください。さらに進むたびに、希望する道路の分岐点を選択する必要があります。取る）。これらのアルゴリズムは、考えられるすべての計算パスの解決策に到達するわけではありません。ただし、それらはいくつかのパスの正しい解決策に到達することが保証されています（つまり、森の中を歩いている男性は、「正しい」パスの組み合わせを選択した場合にのみキャビンを見つけることができます）。選択肢は、検索プロセスでの推測として解釈できます。

リストモナドでは、これはまさにあなたがしていることです。たとえば、リストモナドのクリーク問題の決定バージョンに対するこの解決策を考えてみましょう。

cliques :: Int -> Graph -> [[Node]]
cliques 0 _ = [[]]
cliques minCliqueSize graph = do
  v <- nodes graph
  vs <- cliques (minCliqueSize - 1) (deleteNode v graph)
  mapM_ (\ w -> guard (isAdjacent v w graph)) vs
  return (v:vs)

これはまさに、クリーク問題を解決するための非決定性チューリングマシンなどのプログラミング方法です。

于 2012-04-18T22:02:25.383 に答える
5

次の点を考慮してください。

foo = do
  x <- [1 .. 10]
  y <- [2, 3, 5, 7]
  return (x * y)

とはfoo? ただし、1 から 10 までの数値であり、y が 2、3、5、または 7 のいずれかであるx * yという非決定論的な選択を除いては、です。したがって、foo はx[2, 3, 5, 7, 4, 6, 10, 14, etc... ]

于 2012-04-18T21:59:39.680 に答える
5

ファンクターをコンテナーとして表示するだけでなく、特定の種類のコンテキストとして表示することもできます。あなたの値はそのコンテキストにあり、それらを操作したい場合はmap、関数をコンテキストに持ち上げるために使用します。別の言い方をすれば、あなたの価値観はその文脈で増強されるということです。

リスト ファンクターが非決定論的選択のコンテキストである方法を理解するには、別のファンクターがコンテキストである方法を確認することが役立つ場合があります。Maybe ファンクターは、失敗する可能性のある計算のコンテキストです。Maybe ファンクターの値に関数を適用しようとすると、結果の値は、そもそも計算が失敗したかどうかという同じコンテキストを保持します。

同様に、リストは決定論的な結果を持たない計算の結果と見なすことができますが、その結果は代わりにいくつかの値の 1 つから非決定論的に選択される可能性があります。3 つの要素を持つリストに関数をマップしようとすると、それらの要素は変更されますが、3 つの値から選択できるコンテキストは同じままです。

Dan Burtons の回答から少し借りて、リストのモナド表記を見てください。

foo = do
  x <- [1 .. 10]
  y <- [2, 3, 5, 7]
  return (x * y)

各リストから 1 つの値を抽出できることを表記が示しているように見えるため、最初は少し奇妙に思えますが、結果として 40 要素の長さのリストが得られます。ファンクター (この場合はモナド) を単一の値のコンテキストとして見ると、より意味があります。例では、xとyはそのような値ですが、それらのコンテキストは非決定的であるということです。このような 2 つの値を乗算すると、非決定性がさらに高まり、リストが長くなります。したがって、モナド と>>=ではコンテキストを変更できますが、ファンクター とmapでは変更できません。

于 2012-04-18T22:50:47.640 に答える
4

「古典的な」計算は1つの入力を取り、1つの出力を与えます。これらの非決定論的計算で表現したいのは、次のとおりです。入力について確信が持てない場合、出力について何を言うことができますか？

不確実性を表す2つの通常の方法は、次のことを考慮することです。

  1. 入力が特定のセットの要素であること
  2. 入力が既知の確率分布によって与えられること

例として、入力を2倍にする関数（2 *）について考えてみます。入力がダイスロールの結果である場合、その関数の出力について何を言うことができますか？

  1. サイコロには6つの面があるので、結果はセット{2,4,6,8,10,12}になります。
  2. それぞれの顔の確率が1/6であることを知っているので、これらの数字のそれぞれが1/6の確率で現れることを知っています

リストファンクターは、1の意味で非決定論的計算を表します。：リストによってセットを表します。

于 2012-04-18T21:35:53.600 に答える