如何实现 not_all_equal/1 谓词
How to implement a not_all_equal/1 predicate
如何实现一个 not_all_equal/1
谓词,如果给定列表至少包含 2 个不同的元素则该谓词成功,否则失败?
这是我的尝试(不是很纯粹):
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)
).
然而,这并不总是最好的行为:
?- 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.
在这个例子中,只有第一个答案应该出来,其他两个是多余的。
这里是对 SICStus|SWI 使用 library(reif)
的部分实现。它当然是正确的,因为它在无法继续时会产生错误。但它缺乏我们想要的通用性。
not_all_equalp([A,B]) :-
dif(A,B).
not_all_equalp([A,B,C]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(B,C) ), true, false ).
not_all_equalp([A,B,C,D]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(A,D) ; dif(B,C) ; dif(B,D) ), true, false ).
not_all_equalp([_,_,_,_,_|_]) :-
throw(error(representation_error(reified_disjunction),'C\'est trop !')).
?- not_all_equalp(L).
L = [_A,_B], dif(_A,_B)
; L = [_A,_A,_B], dif(_A,_B)
; L = [_A,_B,_C], dif(_A,_B)
; L = [_A,_A,_A,_B], dif(_A,_B)
; L = [_A,_A,_B,_C], dif(_A,_B)
; L = [_A,_B,_C,_D], dif(_A,_B)
;
! error(representation_error(reified_disjunction),'C\'est trop !')
?- not_all_equalp([A,B,C]), A = a, B = b.
A = a,
B = b
; false.
编辑:现在我意识到我根本不需要添加那么多 dif/2
目标! 一个变量与第一个不同就够了!不需要互斥!我仍然觉得删除 dif(B,C)
目标有点不安全...
not_all_equalp([A,B]) :-
dif(A,B).
not_all_equalp([A,B,C]) :-
if_(( dif(A,B) ; dif(A,C) ), true, false ).
not_all_equalp([A,B,C,D]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(A,D) ), true, false ).
not_all_equalp([_,_,_,_,_|_]) :-
throw(error(representation_error(reified_disjunction),'C\'est trop !')).
答案完全一样...我认为这里发生了什么。这个版本是不是更弱,就是不太一致?
这里有一个简单的方法,您可以做到这一点并保留 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 的示例查询。
首先,最一般的查询:
?- 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 在问题中给出的查询:
?- 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
放在首位:
?- A=a, B=b, not_all_equal([A,B,C]).
A = a, B = b
; false. % <- (non-deterministic, like above)
很好,但理想情况下,最后一个查询应该确定性地成功!
输入<a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/" rel="nofollow noreferrer">library</a>(<a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl" rel="nofollow noreferrer">reif</a>)
First argument indexing
将第一个谓词参数的主要仿函数(加上一些简单的内置测试)考虑在内,以提高充分实例化目标的确定性。
这本身不能覆盖dif/2
令人满意。
我们能做什么?一起工作
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)
). % ).
注意新旧实现的相似之处!
以上,目标 X = E
在左侧是多余的。让我们删除它!
some_dif([X|Xs], E) :-
if_(dif(X,E), true, some_dif(Xs,E)).
太棒了!但是,唉,我们还没有完成(还)!
?- not_all_equal(Xs).
DOES NOT TERMINATE
怎么回事?
事实证明,dif/3
的实现阻止了我们为最一般的查询获得一个好的答案序列。为此——在不使用强制公平枚举的额外目标的情况下——我们需要调整 dif/3
的实现,我称之为 diffirst/3
:
diffirst(X, Y, T) :-
( X == Y -> T = false
; X \= Y -> T = true
; T = true, dif(X, Y)
; T = false, X = Y
).
让我们在谓词的定义中使用 diffirst/3
而不是 dif/3
some_dif/2
:
some_dif([X|Xs], E) :-
if_(diffirst(X,E), true, some_dif(Xs,E)).
所以,最后,这里是新的 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 没有终止,但具有同样漂亮的紧凑答案序列。 好!
查询 #2 仍然是不确定的。好的。对我来说,这已经是最好的了。
查询 #3 已成为确定性的:现在更好了!
底线:
- 使用
library(reif)
来驯服过多的不确定性,同时保持逻辑的纯度!
diffirst/3
应该进入 library(reif)
:)
编辑: 使用 meta-predicate 更通用(由评论建议;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
.
以外的具体化谓词一起使用
这里是对 not_all_equal/1
的更新,现在使用 some/2
而不是 some_dif/2
:
not_all_equal([X|Xs]) :-
some(diffirst(X), Xs).
上面的示例查询仍然给出相同的答案,所以我不会在这里显示这些。
如何实现一个 not_all_equal/1
谓词,如果给定列表至少包含 2 个不同的元素则该谓词成功,否则失败?
这是我的尝试(不是很纯粹):
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)
).
然而,这并不总是最好的行为:
?- 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.
在这个例子中,只有第一个答案应该出来,其他两个是多余的。
这里是对 SICStus|SWI 使用 library(reif)
的部分实现。它当然是正确的,因为它在无法继续时会产生错误。但它缺乏我们想要的通用性。
not_all_equalp([A,B]) :-
dif(A,B).
not_all_equalp([A,B,C]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(B,C) ), true, false ).
not_all_equalp([A,B,C,D]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(A,D) ; dif(B,C) ; dif(B,D) ), true, false ).
not_all_equalp([_,_,_,_,_|_]) :-
throw(error(representation_error(reified_disjunction),'C\'est trop !')).
?- not_all_equalp(L).
L = [_A,_B], dif(_A,_B)
; L = [_A,_A,_B], dif(_A,_B)
; L = [_A,_B,_C], dif(_A,_B)
; L = [_A,_A,_A,_B], dif(_A,_B)
; L = [_A,_A,_B,_C], dif(_A,_B)
; L = [_A,_B,_C,_D], dif(_A,_B)
;
! error(representation_error(reified_disjunction),'C\'est trop !')
?- not_all_equalp([A,B,C]), A = a, B = b.
A = a,
B = b
; false.
编辑:现在我意识到我根本不需要添加那么多 dif/2
目标! 一个变量与第一个不同就够了!不需要互斥!我仍然觉得删除 dif(B,C)
目标有点不安全...
not_all_equalp([A,B]) :-
dif(A,B).
not_all_equalp([A,B,C]) :-
if_(( dif(A,B) ; dif(A,C) ), true, false ).
not_all_equalp([A,B,C,D]) :-
if_(( dif(A,B) ; dif(A,C) ; dif(A,D) ), true, false ).
not_all_equalp([_,_,_,_,_|_]) :-
throw(error(representation_error(reified_disjunction),'C\'est trop !')).
答案完全一样...我认为这里发生了什么。这个版本是不是更弱,就是不太一致?
这里有一个简单的方法,您可以做到这一点并保留 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 的示例查询。
首先,最一般的查询:
?- 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 在问题中给出的查询:
?- 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
放在首位:
?- A=a, B=b, not_all_equal([A,B,C]).
A = a, B = b
; false. % <- (non-deterministic, like above)
很好,但理想情况下,最后一个查询应该确定性地成功!
输入<a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/" rel="nofollow noreferrer">library</a>(<a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl" rel="nofollow noreferrer">reif</a>)
First argument indexing 将第一个谓词参数的主要仿函数(加上一些简单的内置测试)考虑在内,以提高充分实例化目标的确定性。
这本身不能覆盖dif/2
令人满意。
我们能做什么?一起工作
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)
). % ).
注意新旧实现的相似之处!
以上,目标 X = E
在左侧是多余的。让我们删除它!
some_dif([X|Xs], E) :-
if_(dif(X,E), true, some_dif(Xs,E)).
太棒了!但是,唉,我们还没有完成(还)!
?- not_all_equal(Xs). DOES NOT TERMINATE
怎么回事?
事实证明,dif/3
的实现阻止了我们为最一般的查询获得一个好的答案序列。为此——在不使用强制公平枚举的额外目标的情况下——我们需要调整 dif/3
的实现,我称之为 diffirst/3
:
diffirst(X, Y, T) :-
( X == Y -> T = false
; X \= Y -> T = true
; T = true, dif(X, Y)
; T = false, X = Y
).
让我们在谓词的定义中使用 diffirst/3
而不是 dif/3
some_dif/2
:
some_dif([X|Xs], E) :-
if_(diffirst(X,E), true, some_dif(Xs,E)).
所以,最后,这里是新的 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 没有终止,但具有同样漂亮的紧凑答案序列。 好!
查询 #2 仍然是不确定的。好的。对我来说,这已经是最好的了。
查询 #3 已成为确定性的:现在更好了!
底线:
- 使用
library(reif)
来驯服过多的不确定性,同时保持逻辑的纯度! diffirst/3
应该进入library(reif)
:)
编辑: 使用 meta-predicate 更通用(由评论建议;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
.
这里是对 not_all_equal/1
的更新,现在使用 some/2
而不是 some_dif/2
:
not_all_equal([X|Xs]) :-
some(diffirst(X), Xs).
上面的示例查询仍然给出相同的答案,所以我不会在这里显示这些。