4

要素のリストをセットに変換する小さなスクリプトを用意しました。たとえば、リスト [1,1,2,3] -> [1,2,3] を設定します。手順の中で何が起こっているのか、順を追って説明してもらえますか? [1,1,2,3] -> [1,2,3] の例を使用していただけますか?

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).
4

4 に答える 4

4

具体的な例を見ると、すぐに関係のない詳細に埋もれてしまいます。プログラムの重要な特性を見失うほどです。代わりに、障害スライスと呼ばれる次のプログラム フラグメントを見てみましょう。プログラムに目標を追加すると、失敗スライスが得falseられます。失敗スライスは、多くの興味深い特性を元のプログラムと共有しています。たとえばGoal, false、障害スライスで実行された目標は、元のプログラムよりも多くの推論を使用することはありません。または逆に、元のプログラムはより多くの (またはせいぜい同じ数の) 推論を使用します。そこで、そのようなスライスの 1 つを指摘させてください。

list_to_set([],[]) :- false .
list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y), false ,
     \+member(A,Y) .
list_to_set([A|X],Y):-
   list_to_set(X,Y), false ,
    member(A,Y) .

そして、このフラグメントはもはや具体的な要素には関心がないので (Aも も使用されなくなりました)、最も一般的なリストにmember/2使用できます。length/2このようにして、すべての長さに必要な推論の最小数を次のように観察できます。

?- length(L, N), call_inferences((list_to_set(L,_),false;true),Inf)。
N = 0、Inf = 3;
N = 1、Inf = 6;
N = 2、Inf = 12;
N = 3、Inf = 24;
N = 4、Inf = 48;
N = 5、Inf = 96;
N = 6、Inf = 192;
N = 7、Inf = 384;
N = 8、Inf = 768;
N = 9、Inf = 1536;
N = 10、Inf = 3072 ...

使用する

:- meta_predicate user:call_inferences(0,-).
call_inferences( Goal, Inferences) :-
   statistics(inferences, Inferences0),
   Goal,
   statistics(inferences, Inferences1),
   Inferences is Inferences1 - Inferences0.

推論の数は、要素が増えるごとに 2 倍になります。つまり、指数関数的に成長します。したがって、実装には少なくとも指数関数的に多くの推論が必要です...具体的な例を見る必要はありません。

あなたのプログラムにはさらに問題があります:

?- L=[A,B],list_to_set(L,S), L = [a,b].

失敗しますが、

?-  L=[A,B], L = [a,b], list_to_set(L,S).

成功します。つまり、プログラムはもはや純粋な関係ではありません。maplist(dif(A),Y)の代わりに使用し\+ member(A,Y)ます。

于 2013-01-23T13:35:01.597 に答える
3

GNU Prologなどの Prolog の特定の実装では、コードの実行をトレースできます。この機能を使用すると、以下に示すように評価プロセスを進めることができます。

$ gprolog
GNU Prolog 1.4.2
By Daniel Diaz
Copyright (C) 1999-2012 Daniel Diaz
| ?- consult('list_to_set.pro').
yes
| ?- trace.
yes
{trace}
| ?- list_to_set([1,1,2,3], X).
      1    1  Call: list_to_set([1,1,2,3],_25) ?
      2    2  Call: list_to_set([1,2,3],_57) ?
      3    3  Call: list_to_set([2,3],_83) ?
      4    4  Call: list_to_set([3],_109) ?
      5    5  Call: list_to_set([],_135) ?
      5    5  Exit: list_to_set([],[]) ?
      6    5  Call: \+member(3,[]) ?
      7    6  Call: member(3,[]) ?
      7    6  Fail: member(3,[]) ?
      6    5  Exit: \+member(3,[]) ?
      4    4  Exit: list_to_set([3],[3]) ?
      7    4  Call: \+member(2,[3]) ?
      8    5  Call: member(2,[3]) ?
      ...

Prolog のトレースを解釈する方法の説明は、http://remus.rutgers.edu/cs314/f2007/ryder/projects/prolog/prologTrace.htmlのセクションREADING A TRACEにあります。

于 2013-01-22T16:09:26.467 に答える
3

プロローグ プログラムの手続き上の対応物は、SLDNF と呼ばれます。クエリ:

 list_to_set([1,1,2,3], Result)

ここで、SLDNF は、統一と呼ばれる手順を通じて [1,1,2,3] と [A|X] を一致させようとします。簡単に言えば、変数をインスタンス化できるかどうかをチェックします。[A|X] はショートカットで、(大まかに)「A は最初の要素で、X は残りの要素です」という意味です。これは、A= 1、X = [1,2,3]、Result = [1 |Y] の場合に実行できます。統合が成功した場合は、ルールの本体で同じ置換を使用します (:- の後に表示されるもの)。なぜ第 2 節を使用し、第 3 節または第 1 節を使用しないのか不思議に思うかもしれません。Prolog は実際にそれらすべてを試し、非決定論的な選択をエミュレートしようとします。順番に試してみますが、手続き的に。最初の節は統一できません (A = ?、リストに何もありません)。最初の試行が失敗した場合、3 番目の句が後でチェックされます。それを「選択ポイント1」としましょう。

SLDNF により、最初のクエリが次のように削減されました。

list_to_set([1,2,3], Y2), \+ member(1, Y2)       {Result = [1 | Y2]}

(変数は名前を変更できますが、プログラムとの混乱を避けるためにそうしています) ここで魔法が起こります。SLDNF は以前と同じことを行うようになりましたが、入力が少し異なります [1,2,3]。最高の再帰。そのため、最初の句で統一しようとしますが、再び失敗します。2 番目で成功し、同様に、クエリの最初の要素 (リテラルと呼ばれる) の代わりに、変数置換 X = [2, 3]、A = 1、Y2 = [ 1 | Y]。

今、私たちは持っています

list_to_set([2,3], Y), \+ member (1,Y), \+ member(1, [1 | Y])  {Result = [1 | [1 | Y]]}

最後まで続きません。最終的には、+ member(1, [1 | Y]) をチェックすることになります。これは、「1 は、先頭が 1 で末尾が Y のリストのメンバーではない」ことを意味します。これは組み込みの述語であり、1 がそのリストにある (ヘッド) ため、失敗します。プロローグは選択ポイントに戻り、最終的に「選択ポイント1」に到達します。ここで、句の最後の条件は「A is member of Y」です。このパスが最終的に成功することを自分で確認できます。

せっかちな回答で申し訳ありませんが、参考になれば幸いです。

于 2013-01-22T16:20:37.750 に答える
1

それを英語で見て、直感的に理解できるかどうか見てみましょう。述語の名前を少し手続きが少ないように変更すると役立つ場合があるので、これをと呼びますlist_set。

list_set([],[]).

これは、空のセットが空のリストに対応していることを示しています。

list_set([A|X], [A|Y]):-
  list_set(X,Y),
  \+ member(A,Y).

これは、AがYになく、YがXに対応するセットである場合、Aで始まりXで続くリストは、Aで始まりYで続くセットに対応することを意味します。 A（余りはX）で始まるリストで、YがXに対応するセットであり、AがYにない場合、A（余りはY）で始まるセットがあります。否定演算子は常に私には奇妙に見えました。ここで起こっていることは、次の句でAが保持されAていることであり、存在しないということは、Aが効果的に削除されていることを意味するためです。

list_set([A|X], Y):-
  list_set(X, Y),
  member(A, Y).

これは、前の句の「その他」の場合です。YもリストXに対応し、AがすでにYにある場合、Aで始まりXで続くリストはセットYに対応することを示します。これは、Aが最初に表示されるため、結果から要素が削除される方法です。引数のパターンですが、2番目の引数のパターンにはありません。

于 2013-01-22T17:08:58.037 に答える