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 listmember(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.
Best Answer
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.
Ymatches its head,Tmatches the tail. - As a result the predicate fails for the empty list (as it should).
- If
X = Y(i.e.Xcan be unified withY) then we foundXin the list. Otherwise (;) we test whetherXis 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
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).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 ... //0 is on p. 205, Note 1 of
David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars. NACLP 1989, Volume 1.
You can also try this:
member(X,L) :- append(_,[X|_],L).