许多系统提供了member/2
的纯粹且高效的实现。特别是,没有任何选择点可供选择:
?- member(b,[a,b]).
true.
然而,member/2
的简单实现会产生:
?- member(b,[a,b]).
true
; false.
从声明的角度来看这当然是正确的,但效率较低。
另一方面,member/2
存在一些技术问题。它允许冗余解决方案,例如:
?- member(a,[a,a]).
true
; true.
memberd/2
使用 if_/3
解决了这个问题和(=)/3
。
memberd(E, [X|Xs]) :-
if_(E = X, true, memberd(E, Xs)).
?- memberd(a,[a,a]).
true.
不幸的是,这个定义再次留下了选择点 - 产生 ; false
(“剩余选择点”)在成员不这样做的情况下:
?- memberd(X,[a,b]).
X = a
; X = b
; false. % BAD - to be avoided!
?- member(X,[a,b]).
X = a
; X = b.
所以我的问题:是否有一个 memberd/2
的定义可以避免像上面这样的选择点?
最佳答案
首先,为了清楚起见,我们将 memberd
重命名为 memberd_old
。
然后,我们实现 memberd_new/2
,它使用滞后和第一个参数索引来防止在列表末尾创建无用的选择点。
memberd_new(E,[X|Xs]) :-
memberd_new_aux(Xs,X,E).
% auxiliary predicate to enable first argument indexing
memberd_new_aux([],E,E).
memberd_new_aux([X1|Xs],X0,E) :-
if_(E=X0, true, memberd_new_aux(Xs,X1,E)).
让我们比较一下 member/2
(SWI-Prolog 内置谓词)、memberd_old/2
和 memberd_new/2
!
首先,地面查询:
?- member(a,[a,a]).
true ;
true. % BAD!
?- memberd_old(a,[a,a]).
true.
?- memberd_new(a,[a,a]).
true.
接下来,另一个地面查询:
?- member(a,[a,b]).
true ; % BAD!
false.
?- memberd_old(a,[a,b]).
true.
?- memberd_new(a,[a,b]).
true.
现在,一个查询具有多个不同的解决方案:
?- member(X,[a,b]).
X = a ;
X = b.
?- memberd_old(X,[a,b]).
X = a ;
X = b ; % BAD!
false.
?- memberd_new(X,[a,b]).
X = a ;
X = b.
编辑
此处介绍的 memberd_new/2
实现已弃用。
我建议使用显示的较新的实现 in this answer .
关于list - `memberd/2` 更具确定性?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30924607/