不同/ 2 - 是否存在纯粹的,确定的定义？

Question

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

虽然这个定义使用member/2和non_member/2几乎是¹从声明的观点完美的,它产生于特定查询的冗余解决方案,并选择留点周围.

什么是改进的定义(以纯粹的方式可能使用if_/3和(=)/3),使得完全相同的解决方案集被描述different/2但至少对于地面查询是确定的(因此不会留下任何无用的选择点)并且省略(如有可能)任何多余的答案？

---

¹ _{实际上,different([a|nonlist],[]), different([],[b|nonlist])成功了.它同样可能失败.所以两者都失败的解决方案很好(甚至可能更精细).}

Answer 1

第一次尝试!

以下代码基于元谓词tfilter/3和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.

上面的方法感觉就像朝着正确方向迈出了一步......但是,按原样,我不会称之为完美.

Answer 2

这是另一次尝试!我们利用单调if-then-else控制结构if_/3,结合具体列表成员谓词memberd_t/3,以及第一个参数索引来避免创建无用的选择点.

different(Xs,Ys) :-
   different_aux(Xs,Ys,Xs,Ys).

different_aux([],[_|_],Xs0,Ys0) :-
   different_aux(Ys0,[],Ys0,Xs0).     % swap Xs/Ys pair
different_aux([X|Xs],Ys,Xs0,Ys0) :-
   if_(memberd_t(X,Ys0),
       different_aux(Ys,Xs,Ys0,Xs0),  % variant: different_aux(Xs,Ys,Xs0,Ys0)
       true).

首先,我们运行一个我们希望失败的查询:

?- different([1,2,3],[2,3,1]).
false.

以下查询类似于上面给出的失败查询; 每个人x在第一个[1,2,3]或第二个列表中的不同索引处放置一个"不同"项目[2,3,1]:

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

好! 让我们运行我之前回答中使用的另一个(相当普遍的)查询 :

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

紧凑!比我之前介绍的有了很大改进 !

Answer 3

回到根源!此变体非常接近 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).

这是一个地面查询:

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                 % all subgoals succeed deterministically

这是我在之前的答案中使用的(更一般的)查询:

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

Answer 4

(很多灵感来自@rev的最后一个答案,名字仍然太笨拙)

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

Answer 5

代码选美大赛的下一个参赛者! - )

这个答案说明中显示的代码重构变化 前面的回答.它使用具体的连接和分离:

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

注意"和"和"或"的两个版本; 带后缀的那些_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,Truth) :-
   or_t(some_absent_t(Xs,Ys),
        some_absent_t(Ys,Xs),
        Truth).

different(Xs,Ys) :-
   different_t(Xs,Ys,true).

它还在运行吗？

?- 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).                     % same result as before

?- different([4,2,3],[2,3,1]), different([1,2,3],[4,3,1]),
   different([1,4,3],[2,3,1]), different([1,2,3],[2,4,1]),
   different([1,2,4],[2,3,1]), different([1,2,3],[2,3,4]).
true.                                    % same result as before

看起来还不错!

总而言之,不是对现有答案的巨大改进,而是IMO稍微更具可读性的代码,以及different/2作为额外奖励的具体版本!

Answer 6

让我们把它发挥到极致---通过的帮助下list_nonmember_t/3,exists_in_t/3和 or_/2!

some_absent_t(Xs,Ys,Truth) :-
   exists_in_t(list_nonmember_t(Ys),Xs,Truth).

different(Xs,Ys) :-
   or_(some_absent_t(Xs,Ys),
       some_absent_t(Ys,Xs)).

Answer 7

不久前提供了以下大胆的赏金(+500):

^{这里仍然缺少一个惯用的答案.例如,or_t/3应该是(;)/ 3.还有更多.}

接受挑战!这个答案是对前一个答案的后续跟进.

1. 我们使用reified逻辑​​连接词,可以这样定义:(;)/3

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

2. 接下来,我们定义元谓词 call_/1.它对于本答案中使用的具体谓词很有用.它的名字和语义,call_/1如下if_/3,and_/2和or_/2!

   call_(P_1) :- call(P_1,true).
   

3. 使用(;)/3,call_/1和some_absent_t/3我们实施different/2:

   different(As,Bs) :- call_((some_absent_t(As,Bs) ; some_absent_t(Bs,As))).
   

完成!而已.

让我们重新运行我们在之前的答案中使用的查询!

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

?- different([1,2,3],[2,3,1]).
false.

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

同样的疑问,同样的答案...看起来好了给我!