Implement the member predicate as a one-liner
Solution 1
-
Solution:
member(X, [Y|T]) :- X = Y; member(X, T).
-
Demonstration:
?- member(a, []). fail. ?- member(a, [a]). true ; fail. ?- member(a, [b]). fail. ?- member(a, [1, 2, 3, a, 5, 6, a]). true ; true ; fail.
-
How it works:
- We are looking for an occurrence of the first argument,
X
, in the the second argument,[Y|T]
. - The second argument is assumed to be a list.
Y
matches its head,T
matches the tail. - As a result the predicate fails for the empty list (as it should).
- If
X = Y
(i.e.X
can be unified withY
) then we foundX
in the list. Otherwise (;
) we test whetherX
is in the tail.
- We are looking for an occurrence of the first argument,
-
Remarks:
- Thanks to humble coffee for pointing out that using
=
(unification) yields more flexible code than using==
(testing for equality). -
This code can also be used to enumerate the elements of a given list:
?- member(X, [a, b]). X = a ; X = b ; fail.
-
And it can be used to "enumerate" all lists which contain a given element:
?- member(a, X). X = [a|_G246] ; X = [_G245, a|_G249] ; X = [_G245, _G248, a|_G252] ; ...
Replacing
=
by==
in the above code makes it a lot less flexible: it would immediately fail onmember(X, [a])
and cause a stack overflow onmember(a, X)
(tested with SWI-Prolog version 5.6.57).
- Thanks to humble coffee for pointing out that using
Solution 2
Since you didn't specify what other predicates we're allowed to use, I'm going to try and cheat a bit. :P
member(X, L) :- append(_, [X|_], L).
Solution 3
newmember(X, Xs) :-
phrase(( ..., [X] ),Xs, _).
With
... --> [] | [_], ... .
Actually, the following definition also ensures that Xs
is a list:
member_oflist(X, Xs) :-
phrase(( ..., [X], ... ), Xs).
Acknowledgements
The first appearance of above definition of ...
is on p. 205, Note 1 of
David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars. NACLP 1989, Volume 1.
Claudiu
Graduated from Brown University. E-mail: [email protected]
Updated on July 09, 2022Comments
-
Claudiu almost 2 years
Interview question!
This is how you normally define the
member
relation in Prolog:member(X, [X|_]). % member(X, [Head|Tail]) is true if X = Head % that is, if X is the head of the list member(X, [_|Tail]) :- % or if X is a member of Tail, member(X, Tail). % ie. if member(X, Tail) is true.
Define it using only one rule.