Lists in Prolog - Thinking as Computation - page 142

Figure 7.1. A trace of a list predicate

?- person_list([john,sue]).
Call: (7) person_list([john, sue])
Call: (8) person(john)
Exit: (8) person(john)
Call: (8) person_list([sue])
Call: (9) person(sue)
Exit: (9) person(sue)
Call: (9) person_list([])

% This is where the first

Exit: (9) person_list([]) % clause is used.

Exit: (8) person_list([sue])
Exit: (7) person_list([john, sue])

% If H is a person and T is a list of people,
% then [H|T] is also a list of people.
person_list([H|T]) :- person(H), person_list(T).
These two clauses complete the definition. A trace of a query appears in figure 7.1.
Here is how unification works with the two clauses during back-chaining:
1. [john,sue] does not unify with [] in the first clause, but it does unify with [H|T]
in the second clause for H=john and T=[sue] .

2. [sue] does not unify with [], but it does unify with [H|T] for H=sue and T=[] .

3. [] unifies with [] , and the predicate succeeds immediately.
Note how the two notations for lists work together.

Example 2: Membership in a list

Define a predicate elem that will determine whether something is an element of a list.
This is the desired behavior:
?- elem(b,[a,b,c,d]).
Yes
?- elem(f,[a,b,c,d]).
No

Prolog systems provide a predefined predicate, member , with exactly this behavior,
but the following defines a version as a recursive predicate:
1. Write clauses for the empty list. There is nothing to write here since the query

elem(X,[]) should always fail.