Better definition of the reifying memberd_t/3

Question

Section 7 of "Indexing dif/2" discusses general reification and the following definition is given for a reified list-membership:

memberd_t(X, Es, T) :-
   l_memberd_t(Es, X, T).

l_memberd_t([], _, false).
l_memberd_t([E|Es], X, T) :-
   if_( X = E
   , T = true
   , l_memberd_t(Es, X, T) ).

It looks really a bit too complex for me to grasp. After all, the original memberd/2 did not use if_/3. Only subsequent optimizations did. The original version is found in section 4:

memberd(X, [E|Es]) :-
   (  X = E
   ;  dif(X, E),
      memberd(X, Es)
   ).

which then gets optimized step-by-step towards a version using if_/3.

So much for what I have tried. Is there a better way to define memberd_t/3 that does not rely on if_/3 directly and better exposes the fact that we have here two alternatives?

One clarification to what I meant to have the alternatives in an explicit manner. It should be next-to-trivial to write memberdr_t/3 based on it.

?- memberd_t(E,"abc",true).
   E = a
;  E = b
;  E = c
;  false.
?- memberdr_t(E,"abc",true). % how to write that with a trivial change
   E = c
;  E = b
;  E = a
;  false.

This question is not about producing a lower-level implementation as many of the answers have done (by using (\=)/2, !/0, and the like).

Quite the contrary, it focuses on providing a cleaner, high-level implementation.

Answer 1

Using (;)/3:

% Version described in the paper.
memberd_t(_, [], false).
memberd_t(X, [E|Es], T) :-
    call((X=E ; memberd_t(X, Es)), T).

memberdr_t(_, [], false).
memberdr_t(X, [E|Es], T) :-
    call((memberdr_t(X, Es) ; X=E), T).

The alternative for memberd/2 can be obtained by using the commutativity of (;)/2, In the same way, the alternative for memberd_t/2 can be obtained by using the commutativity of (;)/3.

Answer 2

Concise (but inefficient if there is no match in a long list):

memberd_t_alt3(X, Es, true) :-
    member(E, Es),
    ( X == E -> ! ; X = E ).
memberd_t_alt3(X, Es, false) :-
    maplist(dif(X), Es).

Results in swi-prolog:

?- memberd_t_alt3(E, [a, b], T).
E = a,
T = true ;
E = b,
T = true ;
T = false,
dif(E, a),
dif(E, b).

?- memberd_t_alt3(b, [b, b], true).
true. % No unwanted choicepoint

?- memberd_t_alt3(b, [b|_], true), false.
false. % Correct

Answer 3

This improves on memberd_t by avoiding unwanted choicepoints when there is a clearly-matching element:

memberd_t_alt2(X, Es, T) :-
    % Filter the potential matches
    include_eq(Es, X, Ps, M),
    memberd_t_alt2_(M, X, Ps, T).

memberd_t_alt2_(match(X), X, _, true).
memberd_t_alt2_(maybe, X, Es, true) :-
    member(X, Es).
memberd_t_alt2_(maybe, X, Es, false) :-
    maplist(dif(X), Es).

include_eq([], _, [], maybe).
include_eq([E|Es], X, Ps, M) :-
    (   E \= X
        % Definite exclusion
    ->  include_eq(Es, X, Ps, M)
    ;   E == X
        % Definite match, finish here
    ->  M = match(E)
        % Maybe
    ;   Ps = [E|Ps0],
        include_eq(Es, X, Ps0, M)
    ).

Results in swi-prolog:

?- memberd_t_alt2(b, [E, b], T).
T = true. % No unwanted choicepoint

?- memberd_t_alt2(X, [a, b], T).
X = a,
T = true ;
X = b,
T = true ;
T = false,
dif(X, a),
dif(X, b).

?- memberd_t_alt2(b, [b|_], true), false.
false. % Correct

Answer 4

Another solution like memberd_t/3:

=(X, Y, T) :-
    X == Y, !,
    T = true.
=(X, Y, T) :-
    X \= Y, !,
    T = false.
=(Y, Y, true).
=(X, Y, false) :-
    dif(X, Y).

dif(X, Y, T) :-
    X \= Y, !,
    T = true.
dif(X, Y, T) :-
    X == Y, !,
    T = false.
dif(X, Y, true) :-
    dif(X, Y).
dif(Y, Y, false).

memberdb_t(X, [], false).
memberdb_t(X, [E|Es], T) :-
    % if_(dif(X, E), memberdb_t(X, Es, T), T = true).
    (   X \= E
    ->  memberdb_t(X, Es, T)
    ;   X == E
    ->  T = true
    ;   dif(X, E),
        memberdb_t(X, Es, T)
    ;   X = E,
        T = true
    ).

memberdf_t(X, [], false).
memberdf_t(X, [E|Es], T) :-
    % if_(X = E, T = true, memberdf_t(X, Es, T)).
    (   X == E
    ->  T = true
    ;   X \= E
    ->  memberdf_t(X, Es, T)
    ;   X = E,
        T = true
    ;   dif(X, E),
        memberdf_t(X, Es, T)
    ).

Answer 5

Another solution with foldl/4:

memberdf_t(X, Es0, T) :-
    Es = Es0,
    foldl(m_t(X), Es, false, T).

memberdb_t(X, Es0, T) :-
    reverse(Es0, Es),
    foldl(m_t(X), Es, false, T).

m_t(X, E, true, true).
m_t(X, E, false, T) :-
    if_(X = E, T = true, T = false).

Answer 6

This version inlines (=)/3:

memberd_t(_, _, [], false).
memberd_t(D, X, Es0, T) :-
    D == f, !,
    [E|Es] = Es0,
    (   X == E
    ->  T = true
    ;   X \= E
    ->  memberd_t(f, X, Es, T)
    ;   X = E,
        T = true
    ;   dif(X, E),
        memberd_t(f, X, Es, T)
    ).
memberd_t(D, X, Es0, T) :-
    D == b, !,
    [E|Es] = Es0,
    (   X \= E
    ->  memberd_t(b, X, Es, T)
    ;   X == E
    ->  T = true
    ;   dif(X, E),
        memberd_t(b, X, Es, T)
    ;   X = E,
        T = true
    ).

But it's very explicit.

Answer 7

Can use helper:

:- use_module(library(reif)).

memberd_t_alt(X, Es, T) :-
    tmember_t(=(X), Es, T).

Results in swi-prolog:

?- memberd_t_alt(E, [a, b], T).
E = a,
T = true ;
E = b,
T = true ;
false.

?- memberd_t_alt(b, [b, b], true).
true. % No unwanted choicepoint

?- memberd_t_alt(b, [b|_], true), false.
false. % Correct

Answer 8

Comparing from the perspective of the list rather than an element, to hopefully be more intuitive:

memberd5_t(X, Es, T) :-
    memberd5_t_(Es, X, T).

% Nothing matches
memberd5_t_([], _, false).
memberd5_t_([E|Es], X, T) :-
    compare_list_elem(C, E, X),
    memberd5_t_choice_(C, Es, E, X, T).

memberd5_t_choice_(true, _, X, X, true).
memberd5_t_choice_(cont, Es, E, X, T) :-
    dif(E, X),
    % Continue searching
    memberd5_t_(Es, X, T).

compare_list_elem(C, E, X) :-
    (   E == X
        % There is a definite match within the list
    ->  C = true
    ;   true
    ).

Results in swi-prolog:

?- memberd5_t(E, [a, b], T).
E = a,
T = true ;
E = b,
T = true ;
T = false,
dif(E, a),
dif(E, b).

?- memberd5_t(b, [b, b], true).
true. % No unwanted choicepoint

?- memberd5_t(b, [b|_], true), false.
false. % Correct