19

memberchk/2member/2は、次のように定義される一般的に定義された述語です。

memberchk(X, Xs) :-
   once(member(X, Xs)).

したがって、 の最初の回答に対してのみ成功しmember/2ます。その完全な手続き上の意味は、純粋な関係には当てはまりません。その非リレーショナル動作の例として、

?- memberchk(b, [X,b]), X = a.
false.

?- X = a, memberchk(b, [X,b]).
X = a.

一方、多くの場合、十分にインスタンス化さmemberchk/2れた引数で呼び出され、純粋な関係の効率的な近似と見なすことができます。

背後にあるそのような純粋な関係の 1 つがmemberd/2(を使用してif_/3) です。

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

memberchk/2十分にインスタンス化されたケースで近似できる他の純粋な関係はありますか?

言い換えればmemberd/2、 の完全な宣言的置換はありますか、または に置換できないmemberchk/2正当なケースがまだありますか?memberchk/2memberd/2

4

3 に答える 3

5

member/2で表すことができないのよく知られた使用例を次に示しますmemberd/2: bridge.plPascal Van Hentenryck によって与えられたブリッジ スケジューリング問題。

セットアップ フェーズでは、次のmember/2ものが使用されます。

setup(K,Ende,Disj):-
    jobs(L),
    make_vars(L,K),
    member([stop,_,Ende],K),
    ....

したがって、ここでは、事実上、3 要素リストの最初の要素を使用して特定のタスクを選択し、memberd/2要素全体を比較に使用します。結果として、これsetup/3は多くの選択ポイント (実際には 219) を残します。一部 (SICStus など)memberchk/2はそのような状況で使用するため、非単調性を危険にさらします。

次の純粋な置換を使用すると、すべての選択ポイントが回避されます。

member3l([N,D,A], Plan) :-
   tmember(l3_t(N,D,A),  Plan).

l3_t(N,D,A, X, T) :-
   X = [Ni|_],
   if_(N = Ni, ( X=[N,D,A], T = true ), T = false ).

tmember(P_2, [X|Xs]) :-
   if_( call(P_2, X), true, tmember(P_2, Xs) ).

または、次を使用しlibrary(lambda)ます。

member3li([N,Nd,Na], Plan) :-
   tmember([N,Nd,Na]+\X^T^
       (  X=[Nk|_],
          if_( Nk = N, ( X=[N,Nd,Na], T = true ), T = false ) ),
      Plan).

の他の用途tmember/2:

old_member(X, Xs) :-
   tmember( X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberd(X, Xs) :-
   tmember(=(X), Xs).

よりコンパクトな表現を次に示します。

member3l([N,D,A], Plan) :-
   tmember({N,D,A}+\[Ni,Di,Ai]^cond_t(N = Ni, [D,A] = [Di,Ai] ), Plan).

library(lambda)と の使用cond_t/3:

cond_t(If_1, Then_0, T) :-
   if_(If_1, ( Then_0, T = true ), T = false ).
于 2015-10-31T20:58:07.630 に答える
3

memberchk/2次の回答は、 ;に関する元の質問とは直接関係ありません。を定義したこの以前の回答へのフォローアップです。 tmember/2

イディオムtmember/2を次のように一般化することを提案します。

t_non_empty_suffix(P_3, [X|Xs]) :-
   if_(call(P_3,Xs,X), true, t_non_empty_suffix(P_3,Xs)).

Prolog lambdasに基づいて構築するt_non_empty_suffix/2と、次のように定義できます。tmemberX/2

:- use_module(ライブラリ(ラムダ) ).

tmemberX(P_2, Xs) :-
   t_non_empty_suffix(P_2+\_^call(P_2), Xs)。

の代わりに以下old_memberX/2をold_memberdX/2使用します。tmemberX/2tmember/2

old_memberX(X, Xs) :-
   tmemberX(X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberdX(X, Xs) :-
   tmemberX(=(X), Xs).

old_member/2比較してみましょうold_memberX/2...

?- old_member(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

...old_memberd/2そしてold_memberdX/2！

?- old_memberd(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

わかった！old_member/old_memberdに基づいて直接定義するのはどうt_non_empty_suffix/2ですか？

old_memberSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^T^( X = E, T = true ; T = false ), Xs).

old_memberdSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^( X = E ), Xs).

これらの述語を使用して上記のクエリを実行すると、次のようになります。

?- old_memberSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

大丈夫！前と同じ結果。

もう少し掘り下げてみましょう！t_non_empty_suffix/2検討のためのショーケースとしてduplicate_in/2。 、Prolog ラムダ 、、を使用
して、以下を定義します。t_non_empty_suffix/2(=)/3memberd_t/3

','(P_1, Q_1, T) :-
   if_(P_1, call(Q_1,T), T = false).

duplicate_in(X, Xs) :-
   t_non_empty_suffix(X+\Es^E^( X = E, memberd_t(E, Es) ), Xs).

サンプルクエリ:

?- duplicate_in(X, [1,2,3,2,3,4,3,4,5])。
  X = 2 % [1, 2 ,3, 2 ,3,4,3,4,5] (2 が 2 回発生)
; X = 3 % [1,2, 3 ,2, 3 ,4, 3 ,4,5] (3 が 3 回発生)
; X = 4 % [1,2,3,2,3, 4 ,3, 4 ,5] (4 が 2 回発生)
; 間違い。
于 2015-11-02T11:34:38.720 に答える