(SWI)Prolog:次级目标的顺序

Question

我在Prolog中有两个稍微不同的谓词unique_element/2实现.当给定元素X和列表L时,谓词成功,元素X在列表中仅出现一次.以下是实现和结果:

实施1:

%%% unique_element/2
unique_element(Elem, [Elem|T]) :-
    not(member(Elem, T)). 
unique_element(Elem, [H|T]) :-
    member(Elem, T), 
    H\==Elem, 
    unique_element(Elem, T), 
    !. 

结果:

?- unique_element(X, [a, a, b, c, c, b]). 
false.

?- unique_element(X, [a, b, c, c, b, d]).
X = a ;
X = d.

实施2:

%%% unique_element/2
unique_element(Elem, [Elem|T]) :- 
    not(member(Elem, T)). 
unique_element(Elem, [H|T]) :-
    H\==Elem, 
    member(Elem, T), 
    unique_element(Elem, T), 
    !. 

如果你没有第一眼就注意到:"H\== Elem"和"成员(Elem,T)"在第二个impl,规则2上被翻转.

结果:

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

?- unique_element(X, [a, b, c, c, b, d]).
X = a ;
X = d.

问题:在这种情况下,订单如何影响结果？我意识到规则/事实/等的顺序很重要.然而,翻转的两个特定规则似乎不是"连接"或以某种方式相互影响(例如,在错误的位置/顺序中的"切割"谓词).

注意:我们在这里谈论SWI-Prolog.

注2:我知道,可能是不同的和更好的实现.我的问题是关于改变子目标的顺序.

Answer 1

H\==Elem正在测试目标执行时的句法不平等.但后来的统一可能会使变量相同:

?- H\==Elem, H = Elem.
H = Elem.

?- H\==Elem, H = Elem, H\==Elem.
false.

所以在这里我们测试它们是否(语法上)不同,然后它们是统一的,因此不再是不同的.因此,这只是一个临时测试.

member(Elem, T)另一方面,如果这Elem实际上是一个元素,那么目标就是如此T.考虑:

 ?- member(Elem, [X]).
 Elem = X.

哪个可以读作

(何时)它是否持有Elem该列表的元素[X]？

答案是

它在某些情况下,即何时Elem = X.

如果您现在在程序中混合使用这些不同类型的目标,您会得到奇怪的结果,只能通过详细检查您的程序来解释.

作为初学者,最好只坚持Prolog的纯粹部分.在你的情况下:

• 用来dif/2代替\==

• 不要使用削减 - 在你的情况下,它限制了两个答案的数量.如在 unique_element(X, [a,b,c])

• 不要使用not/1也不(\+)/1.它产生更多的不正确性.unique_element(a,[a,X]),X=b.在X=b,unique_element(a,[a,X])正确成功时考虑哪些错误失败.

这是您程序的直接纯化版本.还有改进的余地!

non_member(_X, []).
non_member(X, [E|Es]) :-
   dif(X, E),
   non_member(X, Es).

unique_element(Elem, [Elem|T]) :- 
    non_member(Elem, T). 
unique_element(Elem, [H|T]) :-
    dif(H,Elem), 
     % member(Elem, T),          % makes unique_element(a,[b,a,a|Xs]) loop
    unique_element(Elem, T).

?- unique_element(a,[a,X]).
   dif(X, a)
;  false.              % superfluous

?- unique_element(X,[E1,E2,E3]).
   X = E1,
   dif(E1, E3),
   dif(E1, E2)
;  X = E2,
   dif(E2, E3),
   dif(E1, E2)
;  X = E3,
   dif(E2, E3),
   dif(E1, E3)
;  false.

注意最后一个查询如何读取？

何时是X(任何)列表的唯一元素[E1,E2,E3]？

答案是三重的.考虑一个元素接一个:

X是E1,但只有当它是不同的,以E2和E3

等等

Answer 2

TL; DR:阅读文档并找出原因:

?- X = a, X \== a.
false.

?- X \== a, X = a.
X = a.

我想知道你为什么这么靠近自己搞定了;-)

在Prolog中有太多方法来比较事物.至少,你有统一,有时可以比较,有时甚至更多; 比你有平等,它的否定,你正在使用的那个.那么它做了什么:

?- a \== b. % two different ground terms
true.

?- a \== a. % the same ground term
false.

现在它变得有趣:

?- X \== a. % a free variable and a ground term
true.

?- X \== X. % the same free variable
false.

?- X \== Y. % two different free variables
true.

我建议您执行以下操作:弄清楚member/2它是如何做的(它是否使用统一？等价？还有其他什么？)然后替换member/2上面所有示例中使用的任何内容,看看结果是否有所不同.

既然你正在努力确保事情有所不同,那就尝试一下dif/2.如:

?- dif(a, b).

要么

?- dif(X, X).

要么

?- dif(X, a).

等等.

另见这个问题和答案:我认为答案与您的问题相关.

希望有所帮助.

Answer 3

你能不能像tcount Prolog那样定义unique_element - 在列表中计算重复次数

unique_element(X, List):- tcount(=(X),List,1).

Answer 4

这是使用if_/3和maplist/2 定义 unique_element/2 的另一种可能性：

:- use_module(library(apply)).

unique_element(Y,[X|Xs]) :-
   if_(Y=X,maplist(dif(Y),Xs),unique_element(Y,Xs)).

与@user27815 非常优雅的解决方案 (+s(0)) 相比，此版本不是基于 clpfd（由tcount/3 使用）。OP 给出的示例查询按预期工作：

   ?- unique_element(a,[a, a, b, c, c, b]).
no
   ?- unique_element(X,[a, b, c, c, b, d]).
X = a ? ;
X = d ? ;
no

@false 提供的示例现在成功了，而不会留下多余的选择点：

   ?- unique_element(a,[a,X]).
dif(a,X)

另一个更一般的查询产生相同的结果：

   ?- unique_element(X,[E1,E2,E3]).
E1 = X,
dif(X,E3),
dif(X,E2) ? ;
E2 = X,
dif(X,E3),
dif(X,E1) ? ;
E3 = X,
dif(X,E2),
dif(X,E1) ? ;
no