listprologdcg

Implement the member predicate as a one-liner


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.


Solution

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