32 
different(Xs, Ys) :-
   member(X, Xs),
   non_member(X, Ys).
different(Xs, Ys) :-
   member(Y, Ys),
   non_member(Y, Xs).

member/2andを使用したこの定義は、宣言的な観点からnon_member/2はほぼ完全ですが、特定のクエリに対して冗長なソリューションが生成され、選択ポイントがあちこちに残されます。

これを改善する定義は何ですか (おそらく and を使用する純粋な方法if_/3で(=)/3) によってまったく同じソリューションのセットが記述されdifferent/2ますが、少なくとも地上のクエリに対して決定的であり (したがって、無駄な選択ポイントを開いたままにしません)、省略します (可能であれば）冗長な答えはありますか？

1 実際、different([a|nonlist],[]), different([],[b|nonlist])成功します。同じように失敗する可能性があります。したがって、両方で失敗する解決策は問題ありません (おそらくさらに細かいことです)。

4

8 に答える 8

14

初挑戦！

次のコードは、メタ述語tfilter/3and tpartition/4、単調な if-then-else 制御構文if_/3、具体化された単項論理接続詞not_t/3、および具体化された項等価述語に基づいてい(=)/3ます。

different([],[_|_]).
different([X|Xs0],Ys0) :-
   tpartition(=(X),Ys0,Es,Ys1),
   if_(Es=[], true, (tfilter(not_t(=(X)),Xs0,Xs1),different(Xs1,Ys1))).

サンプルクエリ:

?- different([A,B],[X,Y]).
                A=Y ,           dif(B,Y),     X=Y
;     A=X           ,     B=X           , dif(X,Y)
;     A=X           , dif(B,X), dif(B,Y), dif(X,Y)
;               A=Y ,               B=Y , dif(X,Y)
;               A=Y , dif(B,X), dif(B,Y), dif(X,Y)
; dif(A,X), dif(A,Y).

地上データを扱うときの決定論を観察しましょう。

?- different([5,4],[1,2]).
true.

上記のアプローチは、正しい方向への一歩のように感じます...しかし、現状のままでは、完璧とは言えません。

于 2015-06-16T14:22:24.840 に答える
11

（@repeatの最後の回答に大いに触発されましたが、名前はまだ不器用です）

different(Xs, Ys) :-
   if_(tnotexists_inlist_t(list_memberd_t(Ys), Xs),
      true,
      tnotexists_inlist_t(list_memberd_t(Xs), Ys)).

tnotexists_inlist_t(_P_2, [], false).
tnotexists_inlist_t(P_2, [E|Es], T) :-
   if_(call(P_2, E),
      tnotexists_inlist_t(P_2, Es, T),
      T = true).
于 2015-07-08T16:34:42.150 に答える
10

基礎に戻る！このバリアントは、問題の OP によって指定されたコードに非常に近いものです。

if_/3以下は、およびに基づいていmemberd_t/3ます。

different(Xs,Ys) :-
   if_(some_absent_t(Xs,Ys),
       true,
       some_absent_t(Ys,Xs,true)).

some_absent_t([]    ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   if_(memberd_t(X,Ys), some_absent_t(Xs,Ys,Truth), Truth=true).

以下はグラウンド クエリです。

?- 異なる([ 4 ,2,3],[2,3,1]), 異なる([1,2,3],[ 4 ,3,1]),
   異なる([1, 4 ,3],[2,3,1]), 異なる([1,2,3],[2, 4 ,1]),
   異なる ([1,2, 4 ]、[2,3,1])、異なる ([1,2,3]、[2,3, 4 ])。
真実。%すべてのサブゴールが決定論的に成功する

そして、これが以前の回答で使用した（より一般的な）クエリです。

?- different([A,B],[X,Y]).
      A=X ,               B=X ,           dif(Y,X)
;     A=X ,           dif(B,X), dif(B,Y)
;               A=Y ,               B=Y , dif(Y,X), dif(Y,X)
;               A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y).
于 2015-07-07T17:26:00.577 に答える
7

コード美人コンテストの次の出場者!-)

この回答は、前の回答で示されたコードのリファクタリングされたバリエーションを示して います。具体化された結合と分離を使用します。

and_(P_1,Q_1) :-
   and_t(P_1,Q_1,true).

or_(P_1,Q_1) :-
   or_t(P_1,Q_1,true).

and_t(P_1,Q_1,Truth) :-
   if_(P_1, call(Q_1,Truth), Truth=false).

or_t(P_1,Q_1,Truth) :-
   if_(P_1, Truth=true, call(Q_1,Truth)).

「and」と「or」の 2 つのバージョンに注意してください。接尾辞のあるもの_tは真偽値の追加の引数を持ち、接尾辞のないものはそうではなく、それTruth=trueが成り立つと仮定します。

and_t/3具体化された不等式述語に基づいてdif/3、次のように定義しますnonmember_t/3。

nonmember_t(X,Ys,Truth) :-
   list_nonmember_t(Ys,X,Truth).

list_nonmember_t([]    ,_, true).
list_nonmember_t([Y|Ys],X,Truth) :-
   and_t(dif(X,Y), list_nonmember_t(Ys,X), Truth).

some_absent_t/3では、different_t/3とdifferent/2を次のように定義しましょう。

some_absent_t([] ,_ ,false).
some_absent_t([X|Xs],Ys,Truth) :-
   or_t(nonmember_t(X,Ys), some_absent_t(Xs,Ys), Truth).

different_t (Xs、Ys、真実) :-
   or_t(some_absent_t(Xs,Ys),
        some_absent_t(Ys,Xs),
        真実）。

異なる(Xs,Ys) :-
   different_t(Xs,Ys, true ).

それはまだ実行されますか？

?- 異なる([A,B],[X,Y])。
      A=X , B=X , dif(Y,X)
; A=X , dif(B,X), dif(B,Y)
; A=Y 、 B=Y 、 dif(Y,X)、 dif(Y,X)
; A=Y , dif(B,X), dif(B,Y), dif(Y,X)
; dif(A,X), dif(A,Y)。% 前と同じ結果

?- 異なる([ 4 ,2,3],[2,3,1]), 異なる([1,2,3],[ 4 ,3,1]),
   異なる([1, 4 ,3],[2,3,1]), 異なる([1,2,3],[2, 4 ,1]),
   異なる ([1,2, 4 ]、[2,3,1])、異なる ([1,2,3]、[2,3, 4 ])。
真実。% 前と同じ結果

よさそうですね！

全体として、既存の回答に比べて大幅な改善はありませんが、IMO はやや読みやすいコードでありdifferent/2、追加のボーナスとして の具体化されたバージョンです!

于 2015-07-09T00:51:24.853 に答える