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

memberb/2 is a typical example from constructive negation. You can turn the requirement upside down, and for example require:

?- ~ member(X, [a,b,c]).
dif(X, a),
dif(X, b),
dif(X, c)

Where ~ would be constructive negation. For a discussion on how constructive negation relates to if_ see for example here.

The disadvantage of fully declarative inductive definitions, for memberd/2 or somesuch is that the Prolog disjunction (;)/2 is not able to simplify constraints, and that Prolog doesn't have a forall that would also simplify constraints such as diff/2.

So that in the end when you do it correctly with the limited (;)/2 and missig forall you get in the best case complete solutions that contain a lot of redundant constraints when you look at the full solution sets that the interpreter would produce.

Here is an example in Jekejeke Prolog, it requires the Minlog extension for the predicate diff/2 to be available:

:- use_module(library(term/diff)).
:- use_module(library(basic/lists)).
test(Y) :- diff(X, a), member(Y, [a,X]).

?- test(X).
X = a ;
diff([X], [a])

The above two answers basically say X = a or ~(X = a) which is in most logics the same as a single answer true.

You would need a Prolog interpreter, that at some points works set oriented. And maybe some operators that would force a set oriented processing. But it might break traditional Prolog code. You can probably not just sneak in fully declarative definitions into code that was based on not so declarative definitions.

Bye

Answer 2

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 3

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.