许多系统提供了纯粹而有效的实现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,避免选择点如上所述？
rep*_*eat 12
首先,我们重命名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此处介绍的实现已弃用.
我建议使用此答案中显示的较新实现.
在这个答案中,我们比较了三个不同的列表成员谓词:
member/2,一个内置的谓词,在SWI-Prolog中实现.memberd/2,如OP所定义:
memberd(E,[X|Xs]) :-
if_(E=X, true, memberd(E,Xs)).
memberd_new/2,建议的替代方案,定义如下:
memberd_new(E,[X|Xs]) :-
( Xs \= [_|_]
-> E=X
; if_(E=X, true, memberd_new(E,Xs))
).
我们走吧!
首先,一些基本的查询:
?- member(b,[a,b]).
true.
?- memberd(b,[a,b]).
true.
?- memberd_new(b,[a,b]).
true.
?- member(a,[a,a]).
true ; true. % BAD
?- memberd(a,[a,a]).
true.
?- memberd_new(a,[a,a]).
true.
?- member(a,[a,b]).
true ; false. % BAD
?- memberd(a,[a,b]).
true.
?- memberd_new(a,[a,b]).
true.
接下来,一些查询有多个不同的解决方案
?- member(X,[a,b]).
X = a ; X = b.
?- memberd(X,[a,b]).
X = a ; X = b ; false. % BAD
?- memberd_new(X,[a,b]).
X = a ; X = b.
接下来,在对先前答案的评论中建议的测试案例
打破了之前memberd_new/2提出的版本.
?- member(a,[a|nonlist]).
true.
?- memberd(a,[a|nonlist]).
true.
?- memberd_new(a,[a|nonlist]).
true. % IMPROVED
以上测试用例的变体:
?- member(X,[a|nonlist]).
X = a.
?- memberd(X,[a|nonlist]).
X = a ; false. % BAD
?- memberd_new(X,[a|nonlist]).
X = a. % IMPROVED
最后,一些非终止查询:
?- member(1,Xs).
Xs = [1|_A]
; Xs = [_A,1|_B]
; Xs = [_A,_B,1|_C]
; Xs = [_A,_B,_C,1|_D]
...
?- memberd(1,Xs).
Xs = [1|_A]
; Xs = [_A,1|_B], dif(_A,1)
; Xs = [_A,_B,1|_C], dif(_A,1), dif(_B,1)
; Xs = [_A,_B,_C,1|_D], dif(_A,1), dif(_B,1), dif(_C,1)
...
?- memberd_new(1,Xs).
Xs = [1|_A]
; Xs = [_A,1|_B], dif(_A,1)
; Xs = [_A,_B,1|_C], dif(_A,1), dif(_B,1)
; Xs = [_A,_B,_C,1|_D], dif(_A,1), dif(_B,1), dif(_C,1)
...
还有更多...假设,我们memberD/2基于以下方式实施memberd_t/3:
memberD(X,Xs) :- memberd_t(X,Xs,true).
如何是比较memberd/2,在这个问题的任择议定书的定义？
让我们重新运行一些查询!
?- memberd(a,[a,a]), memberd(a,[a,b]), memberd(b,[a,b]),
memberD(a,[a,a]), memberD(a,[a,b]), memberD(b,[a,b]).
true. % all of these succeed deterministiaclly
?- memberd(X,[a,b]).
X = a ; X = b ; false. % could be better
?- memberD(X,[a,b]).
X = a ; X = b ; false. % could be better
?- memberd(a,[a|nonlist]), memberD(a,[a|nonlist]).
true. % both succeed deterministically
?- memberd(X,[a|nonlist]).
X = a ; false. % could be better
?- memberD(X,[a|nonlist]).
X = a ; false. % could be better
在上面的查询,memberd/2并memberD/2给出相同的答案,并在相同的情况下,留下多余的选择点.
让我们深入挖掘一下!考虑使用memberd_t/3角落案例的以下查询:
?- memberd_t(a,[a|nonlist],T). T = true. % OK ?- memberd_t(b,[a|nonlist],T). false. % missing: `T = false` ?- memberd_t(X,[a|nonlist],T). T = true, X = a ; false. % missing: `T = false, dif(X,a)`
这不是我期望/想要得到的.我们能做什么？基本上,我看到两个选项:
接受这种差异并宣称:"这些查询是不重要的角落案例."
构建memberd_t/3可以处理这些情况的实现.
两种选择都有优点和缺点.在下文中,我们实现memberd_new_t/3了处理极端情况并减少多余选择点的创建.
警告:未来的丑陋代码!
memberd_new_t(E,Xs0,Truth) :-
( Xs0 \= [_|_]
-> Truth = false
; Truth = false,
freeze(Xs0, Xs0\=[_|_])
; Xs0 = [X|Xs],
( Xs \= [_|_]
-> =(E,X,Truth)
; if_(E=X,Truth=true,memberd_new_t(E,Xs,Truth))
)
).
让我们检查一下我们是否会产生更少的无用选择点memberd_new_t/3!
?- memberd_t(X,[a,b],true). X = a ; X = b ; false. % suboptimal ?- memberd_new_t(X,[a,b],true). X = a ; X = b. % BETTER ?- memberd_t(X,[a|nonlist],true). X = a ; false. % suboptimal ?- memberd_new_t(X,[a|nonlist],true). X = a. % BETTER
好的!那么上面的角落呢？
?- memberd_t(a,[a|nonlist],T).
T = true. % OK
?- memberd_new_t(a,[a|nonlist],T).
T = true. % OK
?- memberd_t(b,[a|nonlist],T).
false. % BAD
?- memberd_new_t(b,[a|nonlist],T).
T = false. % OK
?- memberd_t(X,[a|nonlist],T).
T = true, X = a
; false. % BAD
?- memberd_new_t(X,[a|nonlist],T).
T = true, X=a
; T = false, dif(X,a). % OK
有用!最后,考虑最常见的查询:
?- memberd_t(X,Xs,T).
T=false, Xs = []
; T=true , Xs = [X |_A]
; T=false, Xs = [_A ], dif(X,_A)
; T=true , Xs = [_A, X |_B], dif(X,_A)
; T=false, Xs = [_A,_B ], dif(X,_A), dif(X,_B)
; T=true , Xs = [_A,_B, X|_C], dif(X,_A), dif(X,_B)
; T=false, Xs = [_A,_B,_C ], dif(X,_A), dif(X,_B), dif(X,_C)
...
?- memberd_new_t(X,Xs,T).
T=false, freeze(Xs,Xs\=[_|_])
; T=true , Xs = [ X |_A]
; T=false, freeze(_B,_B\=[_|_]), Xs = [_A |_B], dif(X,_A)
; T=true , Xs = [_A, X |_B], dif(X,_A)
; T=false, freeze(_C,_C\=[_|_]), Xs = [_A,_B |_C], dif(X,_A), dif(X,_B)
; T=true , Xs = [_A,_B, X|_C], dif(X,_A), dif(X,_B)
; T=false, freeze(_D,_D\=[_|_]), Xs = [_A,_B,_C|_D], dif(X,_A), dif(X,_B), dif(X,_C)
...
对于这些极端情况,memberd_new_t/3更像是memberd/3不是 memberd_t/3:
?- memberd(X,Xs).
Xs = [ X |_A]
; Xs = [_A, X |_B], dif(X,_A)
; Xs = [_A,_B, X |_C], dif(X,_A), dif(X,_B)
; Xs = [_A,_B,_C, X |_D], dif(X,_A), dif(X,_B), dif(X,_C)
; Xs = [_A,_B,_C,_D, X|_E], dif(X,_A), dif(X,_B), dif(X,_C), dif(X,_D)
...