Declarative uses of memberchk/2

Question

memberchk/2 is a commonly defined predicate that is defined in terms of member/2 like so:

memberchk(X, Xs) :-
   once(member(X, Xs)).

It therefore succeeds only for the first answer of member/2. Its full procedural meaning does not fit into a pure relation. As an example for its non-relational behavior consider

?- memberchk(b, [X,b]), X = a.
false.

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

On the other hand, in many cases memberchk/2 will be called with sufficiently instantiated arguments, where it can be seen as an efficient approximation of a pure relation.

One such pure relation behind is memberd/2 (using if_/3):

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

Are there any other pure relations that can be approximated by memberchk/2 for sufficiently instantiated cases?

In other words: Is memberd/2 a full, declarative replacement for memberchk/2 or are there still legitimate cases where memberchk/2 cannot be replaced by memberd/2?

Answer 1

Here is a well-known example use of member/2 that cannot be represented by memberd/2: bridge.pl the bridge scheduling problem given by Pascal Van Hentenryck.

In the setup phase member/2 is used:

setup(K,Ende,Disj):-
    jobs(L),
    make_vars(L,K),
    member([stop,_,Ende],K),
    ....

So here, effectively the first element in the three-element list is used to select a particular task whereas memberd/2 uses the entire element for comparison. As a consequence this setup/3 leaves open a lot of choicepoints (actually, 219). Some (like SICStus) use memberchk/2 in that situation, thereby risking non-monotonicity.

Using the following pure replacement, all choicepoints are avoided.

member3l([N,D,A], Plan) :-
   tmember(l3_t(N,D,A),  Plan).

l3_t(N,D,A, X, T) :-
   X = [Ni|_],
   if_(N = Ni, ( X=[N,D,A], T = true ), T = false ).

tmember(P_2, [X|Xs]) :-
   if_( call(P_2, X), true, tmember(P_2, Xs) ).

Alternatively using library(lambda):

member3li([N,Nd,Na], Plan) :-
   tmember([N,Nd,Na]+\X^T^
       (  X=[Nk|_],
          if_( Nk = N, ( X=[N,Nd,Na], T = true ), T = false ) ),
      Plan).

Other uses of tmember/2:

old_member(X, Xs) :-
   tmember( X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberd(X, Xs) :-
   tmember(=(X), Xs).

Here is a more compact representation:

member3l([N,D,A], Plan) :-
   tmember({N,D,A}+\[Ni,Di,Ai]^cond_t(N = Ni, [D,A] = [Di,Ai] ), Plan).

Using library(lambda)and cond_t/3:

cond_t(If_1, Then_0, T) :-
   if_(If_1, ( Then_0, T = true ), T = false ).

Answer 2

The following answer does not directly relate to the original question regarding memberchk/2; instead, it is a follow-up to this previous answer which defined meta-predicate tmember/2.

We propose generalizing the idiom tmember/2 like so:

t_non_empty_suffix(P_3, [X|Xs]) :-
   if_(call(P_3,Xs,X), true, t_non_empty_suffix(P_3,Xs)).

Building on t_non_empty_suffix/2 and Prolog lambdas, we can define tmemberX/2 like so:

:- use_module(library(lambda)).

tmemberX(P_2, Xs) :-
   t_non_empty_suffix(P_2+\_^call(P_2), Xs).

The following old_memberX/2 and old_memberdX/2 use tmemberX/2 instead of tmember/2:

old_memberX(X, Xs) :-
   tmemberX(X+\E^T^( X = E, T = true ; T = false ), Xs).

old_memberdX(X, Xs) :-
   tmemberX(=(X), Xs).

Let's compare old_member/2 to old_memberX/2 ...

?- old_member(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

... and old_memberd/2 to old_memberdX/2!

?- old_memberd(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

OK! How about defining old_member / old_memberd directly based on t_non_empty_suffix/2?

old_memberSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^T^( X = E, T = true ; T = false ), Xs).

old_memberdSFX(X, Xs) :-
   t_non_empty_suffix(X+\_^E^( X = E ), Xs).

Running above queries with these predicates we get:

?- old_memberSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 2 ; X = 3 ; X = 4 ; X = 3 ; X = 4 ; X = 5 ; false.

?- old_memberdSFX(X, [1,2,3,2,3,4,3,4,5]).
X = 1 ; X = 2 ; X = 3 ; X = 4 ; X = 5 ; false.

Alright! Same results as before.

---

Let's dig a bit deeper! As a show-case for t_non_empty_suffix/2 consider duplicate_in/2.
Using t_non_empty_suffix/2, Prolog lambdas, (=)/3, and memberd_t/3 we define:

','(P_1, Q_1, T) :-
   if_(P_1, call(Q_1,T), T = false).

duplicate_in(X, Xs) :-
   t_non_empty_suffix(X+\Es^E^( X = E, memberd_t(E, Es) ), Xs).

Sample query:

?- duplicate_in(X, [1,2,3,2,3,4,3,4,5]).
  X = 2         % [1,2,3,2,3,4,3,4,5]    (2 occurs  twice)
; X = 3         % [1,2,3,2,3,4,3,4,5]    (3 occurs thrice)
; X = 4         % [1,2,3,2,3,4,3,4,5]    (4 occurs  twice)
; false.