Prolog中的alldifferent/1谓词

Question

allsame([]).
allsame([X]).
allsame([X,X|Z]) :-
   allsame([X|Z]).

如何更改以获得下面的结果？

alldifferent(L): The elements in L are all different.

?- alldifferent([a, b, b, c, d]).
false
?- alldifferent([a, b, c, d, e]).
true

Answer 1

首先,让我们先看看你的定义allsame/1.对于给定的列表,您正在建立这样的平等:

[ A,      B,      C,      D ... ]
    A = B,  B = C,  C = D,   ...      chain pattern

所以你正在建立一系列平等.通过引用一个公共变量,还有另一种表达方式:

[ A,      B,      C,      D ... ]
  A = V,  B = V,  C = V,  D = V,  ... star pattern

这最常见的表达方式是:

allsame_bis(L) :-
   maplist(=(_), L).

或者,更多的增长,不使用经常定义的maplist/2:

allsame_ter(L) :-
   allsame_with(L, _).

allsame_with([], _).
allsame_with([X|Xs], V) :-
   X = V,                      % could be moved into the head
   allsame_with(Xs, V).

现在,你说,你"想要联系"这一点alldifferent/1,这使情况变得更加复杂.请注意,这alldifferent/1不是对您的财产的直接否定.那将是:

notallsame(L) :-
   phrase((..., [A,B], {dif(A,B)}, ...), L),

有两个直接连续的元素是不同的.

为了完整起见,这里有一个版本可以避免查询的冗余答案,例如notallsame([1,2,3]):

notallsame_bis(L) :-
   phrase((all(=(A)),[A,B], {dif(A,B)}, ...), L).

首先是一系列相同的元素,然后是一个不同的元素.

all//1并... //1在别处定义.

但回到不同的/ 2.平等关系是可传递的,它允许我们做一些快捷方式,无论是做链还是做星.但是不同是不可传递的.所以我们现在要建立dif/2所有可能的对之间的差异关系.总的来说,我们需要n 2 n/2 dif/2个目标.嘿,我们很高兴我们仍然可以利用交换性,否则我们将不得不支付两倍以上.

 alldifferent([]).
 alldifferent([X|Xs]) :-
    maplist(dif(X), Xs),
    alldifferent(Xs).

这种关系建立dif/2如下:

 [ A,      B,        C,        D,        E ... ]
       dif(B,A), dif(C,A), dif(D,A), dif(E,A), ... maplist(dif(A),[B,C,D,E ...])
                 dif(C,B), dif(D,B), dif(E,B), ... maplist(dif(B),  [C,D,E ...])
                           dif(D,C), dif(E,C), ... maplist(dif(C),    [D,E ...])
                                     dif(E,D), ... maplist(dif(D),      [E ...])

这是另一个版本,可能看起来更诱人.事实上,它与您的原始程序有一定的相似之处.不是吗？

alldifferent_bis([]).
alldifferent_bis([_]).
alldifferent_bis([A,B|Xs]) :-
   dif(A,B),
   alldifferent_bis([A|Xs]),
   alldifferent_bis([B|Xs]).

最后,我们可以使用更高阶定义来使用以下定义:

alldifferent_ter(L) :-
   pairwise(dif,L).

allsame_quater(L) :-
   pairwise(=,L).

无论出于何种原因,如果您无法使用dif/2,请使用安全的ISO Prolog近似值iso_dif/2.它会尽可能频繁地(安全地)成功,但是当可能发生安全故障时可能会产生错误.想一想alldifferent_bis([_,a,a]).