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?

A kind of unit test would be useful. Something like "Hey, guys, make it succeed". — dlask, Jun 19 '15 at 19:05
@dlask: There is only the toplevel that shows you what we want to succeed. Could use `setup_call_cleanup/3` but that is way more confusing. — false, Jun 19 '15 at 19:07
I mean, there are many different combinations of parameters and responses, it would be comfortable to have all those checks automated. By the way, is it possible to detect the choice points programmatically? — dlask, Jun 19 '15 at 19:12
Two related questions/remarks: 1) `member(a, [a,a])` succeeds twice, but this could be interpreted as "`a` is member of `[a,a]` twice"; can you explicitly provide in your question your preferred reading? and 2) `member(a, [a, b])` still gives `true; false`; is your idea that a succeeding exactly once is always to be preferred? — , Jun 23 '15 at 11:42
@Boris: Declarative reading is always a reading on ground terms only. A redundant solution thus has absolutely no meaning at all. This becomes maybe more evident if you have several occurences of that goal. Say: `member(a, [a,a]), member(a, [a,a])` the three extra answers have no declarative meaning whatsoever - it would not be the worst idea to use a `once/1` in this particular case. Note that `once/1` cannot be used for every ground goal, because of potential inconsistencies - think of `p:-freeze(_,false).` and the query `q`. — false, Jun 23 '15 at 11:47
@Boris: As for `true ; false` this is a performance issue **only**. There are other ways to attack this problem (like [`call_semidet/1`](http://stackoverflow.com/a/12942551/772868)) too. — false, Jun 23 '15 at 11:49

score 12 · Answer 1 · edited May 23 '17 at 12:15

12

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.

edited May 23 '17 at 12:15

Community

1
1

answered Jun 18 '15 at 21:46

repeat

18,496
4
54
166

2

~ It is a restriction compared to `member/2` or `memberd/2`. Not sure this is a good idea. – false Jun 19 '15 at 12:28
1

`memberd(a,[a|nonlist])` succeeds, but not in your version – false Jun 19 '15 at 12:43
1

@false What is the rationale behind `memberd(a, [a|nonlist])` succeeding? The second argument is not even a list? – Jun 26 '15 at 17:49
1

@Boris: It is a generalization that has performance advantages. Think of `memberd(a,[a,b,c,d])` which is immediately determinate without visiting the entire list. Conversely, if you would always impose that no generalization is permitted you would have much weaker termination properties (think of the 2nd argument of `append/3`). – false Jun 26 '15 at 17:58
@Boris: and, similar arguments apply to enumerate answers for partial lists, there repeat's aproach produces twice as many answers. – false Jun 26 '15 at 18:25
@Boris: FYI, there is a [100 bounty](http://stackoverflow.com/q/30863784/772868) waiting... – false Jun 26 '15 at 19:06
@false That's great, but I am not able to figure out the intended semantics of `memberd/2`. Reading the answers where you have used it to solve other questions, I get a clear idea of how it can be used to solve the particular problem, but I am not sure I understand its most general meaning. – Jun 27 '15 at 08:17
@Boris: You know how to ask a question :-) – false Jun 27 '15 at 08:30

score 8 · Answer 2 · edited May 23 '17 at 12:24

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

score 6 · Answer 3 · answered Aug 03 '15 at 09:56

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:

Accept this discrepancy and proclaim: "These queries are corner-cases of no importance."
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)
...

More determinism for `memberd/2`?

3 Answers3

Edit

Linked