list - `memberd/2` 更具确定性？

Question

许多系统提供了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 的定义可以避免像上面这样的选择点？

Answer 1

首先，为了清楚起见，我们将 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 .