More determinism for `memberd/2`?

Question

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?

Answer 1

In this answer we compare three different list-membership predicates:

• member/2, a builtin predicate, as implemented in SWI-Prolog.

• memberd/2, as defined by the OP:

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

• memberd_new/2, a proposed alternative which is defined like this:

  memberd_new(E,[X|Xs]) :-
     (  Xs \= [_|_]
     -> E=X
     ;  if_(E=X, true, memberd_new(E,Xs))
     ).
  

---

Let's go!

First, some ground queries:

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

Next, some queries having multiple distinct solutions:

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

Next, a test-case suggested in a comment to a previous answer which broke the version of memberd_new/2 presented earlier.

?- member(a,[a|nonlist]).
true.
?- memberd(a,[a|nonlist]).
true.
?- memberd_new(a,[a|nonlist]).
true.                               % IMPROVED

A variation of above test-case:

?- member(X,[a|nonlist]).
X = a.
?- memberd(X,[a|nonlist]).
X = a ; false.                      % BAD
?- memberd_new(X,[a|nonlist]).
X = a.                              % IMPROVED

Last, some non-terminating queries:

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

Answer 2

There's more... Suppose, we implement memberD/2 based on memberd_t/3:

memberD(X,Xs) :- memberd_t(X,Xs,true).

How does that compare to memberd/2, as defined by the OP in the question?

Let's re-run some queries!

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

In above queries, memberd/2 and memberD/2 give the same answers and leave behind superfluous choice-points in the same instances.

Let's dig a little deeper! Consider the following queries using memberd_t/3 with corner-cases:

?- 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)`

This is not quite what I expected / wanted to get. What can we do? Basically, I see two options:

1. Accept this discrepancy and proclaim: "These queries are corner-cases of no importance."

2. Build an implementation of memberd_t/3 that can handle these cases.

Both options have strengths and weaknesses. In the following we implement memberd_new_t/3 which both handles the corner cases and reduces the creation of superfluous choice-points.

Warning: ugly code ahead!

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

Let's check if we produce fewer useless choicepoints with 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

Alright! So what about above corner cases?

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

It works! At last, consider the most general queries:

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

For these corner cases, memberd_new_t/3 is more like memberd/3 than 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)
...

Answer 3

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.