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? Promise: will use my rep above 10k.
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.
(As there is currently not a single answer into that direction, I refrain from putting out a bounty. However, I will award one, should there be a fitting answer.)
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).
2
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
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
1
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.
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)
).
4
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
1
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
2