更多关于"membered/2"的确定性吗? [英] More determinism for `memberd/2`?

问题描述

许多系统提供member/2的纯净有效实现.特别是，没有选择点可以打开:

Many systems provide a pure and efficient implementation of member/2. In particular, no choice point is left open for:

?- member(b,[a,b]).
true.

而member/2的简单实现会产生以下结果:

whereas, a naive implementation of member/2 produces rather:

?- member(b,[a,b]).
true ;
false.

从声明的角度来看，这当然是正确的，但是效率较低.

which is certainly correct from a declarative viewpoint, but less efficient.

另一方面，member/2存在一些技术问题.它允许冗余解决方案，例如:

On the other hand, there are some technical problems with member/2. It permits redundant solutions, like in:

?- member(a,[a,a]).
true ;
true.

memberd/2使用 if_/3 和(=)/3解决了此问题.

memberd/2 solves this problem using if_/3 and (=)/3.

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs)).

?- memberd(a,[a,a]).
true.

不幸的是，此定义使选择点再次打开-在成员不存在的情况下产生; false(剩余的选择点").

Unfortunately, this definition leaves choice points open again - producing ; false ("leftover choicepoints") in situations where member does not:

?- memberd(X,[a,b]).
X = a ;
X = b ;
false.    % BAD - to be avoided!

?- member(X,[a,b]).
X = a ;
X = b.

所以我的问题是:是否有memberd/2的定义避免了上述选择点?

So my question: Is there a definition of memberd/2 that avoids the choice point as this one above?

推荐答案

首先，为了清楚起见，我们将memberd重命名为memberd_old.

First, we rename memberd to memberd_old for the sake of clarity.

然后，我们实现memberd_new/2，该方法使用滞后和第一参数索引来防止在列表末尾创建无用的选择点.

Then, we implement memberd_new/2, which uses lagging and 1st argument indexing to prevent the creation of the useless choicepoint at the end of the list.

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！

Let's compare member/2 (SWI-Prolog builtin predicate), memberd_old/2, and memberd_new/2!

首先，进行地面查询:

?- member(a,[a,a]).
true ;
true.                       % BAD!

?- memberd_old(a,[a,a]).
true.

?- memberd_new(a,[a,a]).
true.

接下来，另一个地面查询:

Next, another ground query:

?- member(a,[a,b]).
true ;                      % BAD!
false.

?- memberd_old(a,[a,b]).
true.

?- memberd_new(a,[a,b]).
true.

现在，具有多个不同解决方案的查询:

Now, a query having multiple distinct solutions:

?- 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的实现.

我建议在此答案中使用所示的更新的实现.

I recommend using the newer implementation shown in this answer.

这篇关于更多关于"membered/2"的确定性吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！