Lists in Prolog - Thinking as Computation - page 143

2. Write clauses to handle the list [H|T] , assuming the list T is already taken care of.
The query elem(X,[H|T]) should succeed if X is equal to H ,orif X is an element
of list T . So two clauses are needed:
% X is an element of any list whose head is X.
elem(X,[X|_]).
% If X is an element of a list L,
% then it is an element of any list whose tail is L.
elem(X,[_|L]) :- elem(X,L).
Note the use of the anonymous variable. In the first clause, the query succeeds no
matter what the tail is; in the second clause, the query succeeds no matter what the
head is.
We can follow the behavior in a trace:
?- elem(c,[a,b,c,d]).
Call: (7) elem(c,[a,b,c,d])
Call: (8) elem(c,[b,c,d])
Call: (9) elem(c,[c,d]) % Here the first clause is used and

Exit: (9) elem(c,[c,d]) % succeeds immediately.

Exit: (8) elem(c,[b,c,d])
Exit: (7) elem(c,[a,b,c,d])

Example 3: List of unique people

The member predicate (or the elem predicate just defined) can be used to write the
clauses for a predicate uniq_people (

)

that holds when z is any list of people that are
all distinct, as needed for many constraint satisfaction problems. As before, assume
that a predicate person is already defined. The uniq_people predicate will once again
be recursive:
1. The empty list [] is a (trivial) list of unique people.
2. For the list [P|L] ,if P is a person, L is a list of unique people, and in addition, P
is not an element of L , then [P|L] is also a list of unique people.
This gives a definition of the predicate with the following two clauses:
uniq_people([]).
uniq_people([P|L]) :- uniq_people(L), person(P), \+ member(P,L).
This recursive predicate will work properly for lists of any size. Note how succinct
and elegant this definition is compared to the long sequences of inequalities written
in chapter 5 for each constraint satisfaction problem.

z