Implement a Prolog predicate that say if an element belong to a list. Problems with not numerical lists

Question

I am studying Prolog for an university exam and I have problems with this exercise:

Implement the predicate not_member(X,L) that is TRUE if the element X does not belong to the list L.

If my reasoning is correct, I have found a solution:

% FACT (BASE CASE): It is TRUE that X is not in the list if the list is empty.
not_member(_,[]).

% RULE (GENERAL CASE): If the list is non-empty, I can divide it in its Head
%   element and the sublist Tail. X does not belong to the list if it is different 
%   from the current Head element and if it does not belong to the sublist Tail.
not_member(X,[Head|Tail]) :-
   X =\= Head,
   not_member(X,Tail).

This code works well with lists of numbers, as the following queries show:

2 ?- not_member(4, [1,2,3]).
true.

3 ?- not_member(1, [1,2,3]).
false.

With lists having some non-numerical elements, however, it does not work and reports an error:

4 ?- not_member(a, [a,b,c]).
ERROR: =\=/2: Arithmetic: `a/0' is not a function

Why?

Monophthong

Answer 1

Let's check the documentation!

(=\=)/2 is an arithmetic operator.

+Expr1 =\= +Expr2 True if expression Expr1 evaluates to a number non-equal to Expr2.

You have to use (\=)/2 to compare two generic terms:

not_member(_, []) :- !.

not_member(X, [Head|Tail]) :-
     X \= Head,
    not_member(X, Tail).

and:

?- not_member(d, [a,b,c]).
true.

Handicraftsman

ok, tnx so much. Only a litle clarification: why do you use: not_member(, []) :- !. instead: not_member(, []). what exactly mean !. ? Tnx – Monophthong

(not a detailed explanation) It's a cut. It prevents backtracking, but it's not mandatory. In this case it's ok to use it since once the unification has succeded on not_member(_, []). we don't need to check for other "solutions", so we "cut" the prolog search tree and stop che computation. – Handicraftsman

Answer 2

Use prolog-dif to get logically sound answers—for both ground and non-ground cases!

Just like in this answer, we define non_member(E,Xs) as maplist(dif(E),Xs).

Let's put maplist(dif(E),Xs) and not_member(E,Xs) by @Haile to the test!

?- not_member(E,[1,2,3]).
false.                                   % wrong! What about `E=4`?

?- maplist(dif(E),[1,2,3]).
dif(E,1), dif(E,2), dif(E,3).            % success with pending goals

Is it steadfast? (For more info on this important issue, read this, this, this, and this answer.)

?- E=d, not_member(E,[a,b,c]).
E = d.
?-      not_member(E,[a,b,c]), E=d.
false.                                  % not steadfast

?- E=d, maplist(dif(E),[a,b,c]).
E = d.
?-      maplist(dif(E),[a,b,c]), E=d.   % steadfast
E = d.

Let's not forget about the most general use!

?- not_member(E,Xs).               
Xs = [].                                % a lot of solutions are missing!

?- maplist(dif(E),Xs).
  Xs = []
; Xs = [_A]      , dif(E,_A)
; Xs = [_A,_B]   , dif(E,_A), dif(E,_B)
; Xs = [_A,_B,_C], dif(E,_A), dif(E,_B), dif(E,_C)
...

Championship