Implement the member predicate as a one-liner

Question

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.

Soares

Interview for a job? what job? where? do people get jobs thanks to Prolog? – Radbourne

Answer 1

1. Solution:

   member(X, [Y|T]) :- X = Y; member(X, T).
   

2. 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.
   

3. 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 with Y) then we found X in the list. Otherwise (;) we test whether X is in the tail.

4. 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 on member(X, [a]) and cause a stack overflow on member(a, X) (tested with SWI-Prolog version 5.6.57).

Excitor

hmm very cute. The key was the ; operator - I didn't know you could do 'or's inside of a rule. – Soares

If you replace "X == Y" with "X = Y", then you can do member(X, [a]). and even get a sensible result for member(a, X). – Cartography

@humble coffee: thanks! I barely touched Prolog the last few years, so my knowledge is a bit rusty :) – Excitor

It being used to enumerate elements / lists etc. is an awesome side-effect of the way prolog works =). not special to this example - if you define Addition, you automatically get Subtraction. If you define a TypeChecker, you also define an enumerator for all well-typed programs. – Soares

the point of X == Y vs X = Y is that with the second one you're forcing unification (bad as far i can tell), with the second one you do a deep equality check – Underlying

Answer 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).

Nirvana

Answer 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 ... //0 is on p. 205, Note 1 of

David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars. NACLP 1989, Volume 1.

Synn

Answer 4

You can also try this:

member(X,L) :- append(_,[X|_],L).

Estrellaestrellita

Oops, I haven't noticed that this solution already had been given. – Estrellaestrellita