如何实现not_all_equal/1谓词 [英] How to implement a not_all_equal/1 predicate

问题描述

如何实现一个not_all_equal/1谓词，如果给定列表包含至少2个不同的元素，则谓词成功；否则，该谓词失败?

How would one implement a not_all_equal/1 predicate, which succeeds if the given list contains at least 2 different elements and fails otherwise?

这是我的尝试(不是很纯正):

Here is my attempt (a not very pure one):

not_all_equal(L) :-
    (   member(H1, L), member(H2, L), H1 \= H2 -> true
    ;   list_to_set(L, S),
        not_all_equal_(S)
    ).

not_all_equal_([H|T]) :-
    (   member(H1, T), dif(H, H1)
    ;   not_all_equal_(T)
    ).

但这并不总是具有最佳的行为:

This however does not always have the best behaviour:

?- not_all_equal([A,B,C]), A = a, B = b.
A = a,
B = b ;
A = a,
B = b,
dif(a, C) ;
A = a,
B = b,
dif(b, C) ;
false.

在此示例中，只有第一个答案应该出现，其他两个答案是多余的.

In this example, only the first answer should come out, the two other ones are superfluous.

推荐答案

这是一种简单的方法，可以保留

Here's a straightforward way you can do it and preserve logical-purity!

not_all_equal([E|Es]) :-
   some_dif(Es, E).

some_dif([X|Xs], E) :-
   (  dif(X, E)
   ;  X = E, some_dif(Xs, E)
   ).

以下是一些使用SWI-Prolog 7.7.2的示例查询.

Here are some sample queries using SWI-Prolog 7.7.2.

首先，最普遍的查询:

?- not_all_equal(Es).
   dif(_A,_B), Es = [_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_A,_A,_B|_C]
...

接下来，OP在问题中给出的查询:

Next, the query the OP gave in the question:

?- not_all_equal([A,B,C]), A=a, B=b.
   A = a, B = b
;  false.                          % <- the toplevel hints at non-determinism

最后，让我们将子目标A=a, B=b放在前面:

Last, let's put the subgoal A=a, B=b upfront:

?- A=a, B=b, not_all_equal([A,B,C]).
   A = a, B = b
;  false.                          % <- (non-deterministic, like above)

很好，但理想情况下，最后一个查询应该确定地成功！

Good, but ideally the last query should have succeeded deterministically!

第一个参数索引 考虑到第一个谓词参数的主要函子(加上一些简单的内置测试)，以改善足够实例化目标的确定性.

First argument indexing takes the principal functor of the first predicate argument (plus a few simple built-in tests) into account to improve the determinism of sufficiently instantiated goals.

这本身并不能令人满意地覆盖dif/2.

This, by itself, does not cover dif/2 satisfactorily.

我们该怎么办?与...合作 经过修饰的词等式/不等式—有效地索引dif/2 ！

What can we do? Work with reified term equality/inequality—effectively indexing dif/2!

some_dif([X|Xs], E) :-                     % some_dif([X|Xs], E) :-
   if_(dif(X,E), true,                     %    (  dif(X,E), true
       (X = E, some_dif(Xs,E))             %    ;  X = E, some_dif(Xs,E)
      ).                                   %    ).

请注意新旧实现的相似之处！

Notice the similarities of the new and the old implementation!

以上，目标X = E在左侧是多余的.让我们删除它！

Above, the goal X = E is redundant on the left-hand side. Let's remove it!

some_dif([X|Xs], E) :-
   if_(dif(X,E), true, some_dif(Xs,E)).

甜！但是，a，我们还没有完成呢！

Sweet! But, alas, we're not quite done (yet)!

?- not_all_equal(Xs).
DOES NOT TERMINATE

发生了什么事?

事实证明，dif/3的实现使我们无法获得最通用查询的良好答案序列.为此，而无需使用其他用于强制进行公平枚举的目标，我们需要对dif/3进行调整后的实现，我将其称为diffirst/3:

It turns out that the implementation of dif/3 prevents us from getting a nice answer sequence for the most general query. To do so—without using additional goals forcing fair enumeration—we need a tweaked implementation of dif/3, which I call diffirst/3:

diffirst(X, Y, T) :-
   (  X == Y -> T = false
   ;  X \= Y -> T = true
   ;  T = true,  dif(X, Y)
   ;  T = false, X = Y
   ).

在谓词some_dif/2的定义中使用diffirst/3代替dif/3:

Let's use diffirst/3 instead of dif/3 in the definition of predicate some_dif/2:

some_dif([X|Xs], E) :-
   if_(diffirst(X,E), true, some_dif(Xs,E)).

因此，终于有了上述带有新some_dif/2的查询:

So, at long last, here are above queries with the new some_dif/2:

?- not_all_equal(Es).                     % query #1
   dif(_A,_B), Es = [_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_B|_C]
...

?- not_all_equal([A,B,C]), A=a, B=b.      % query #2
   A = a, B = b
;  false.

?- A=a, B=b, not_all_equal([A,B,C]).      % query #3
A = a, B = b.

查询1不会终止，但是具有相同的紧凑型答案序列. 好！

Query #1 does not terminate, but has the same nice compact answer sequence. Good!

查询2仍不确定.好的.对我来说，这是最好的.

Query #2 is still non-determinstic. Okay. To me this is as good as it gets.

查询#3已变得确定性:现在更好！

Query #3 has become deterministic: Better now!

底线:

1. 使用library(reif)驯服多余的不确定性，同时保持逻辑纯正！
2. diffirst/3应该进入library(reif):)

1. Use library(reif) to tame excess non-determinism while preserving logical purity!
2. diffirst/3 should find its way into library(reif) :)

---

---

---

编辑:使用元谓词(由评论建议；谢谢！)

---

---

---

more general using a meta-predicate (suggested by a comment; thx!)

让我们像这样概括化some_dif/2:

:- meta_predicate some(2,?).
some(P_2, [X|Xs]) :-
   if_(call(P_2,X), true, some(P_2,Xs)).

some/2可以与diffirst/3以外的其他谓词一起使用.

some/2 can be used with reified predicates other than diffirst/3.

这里是对not_all_equal/1的更新，该更新现在使用some/2而不是some_dif/2:

Here an update to not_all_equal/1 which now uses some/2 instead of some_dif/2:

not_all_equal([X|Xs]) :-
   some(diffirst(X), Xs).

上面的示例查询仍然给出相同的答案，因此在此不再显示.

Above sample queries still give the same answers, so I won't show these here.

这篇关于如何实现not_all_equal/1谓词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！