Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

list - More determinism for `memberd/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.

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.

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 solves this problem using if_/3 and (=)/3.

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

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

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.

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

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

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)).

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

First, a ground query:

?- 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.

Edit

The implementation of memberd_new/2 presented here is deprecated.

I recommend using the newer implementation shown in this answer.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...