A classical example of recursion in list-processing is identifying whether some item is an element of a list. This predicate is commonly called member/2. It is true if the item is on the list, and false otherwise. The base is that situation where we can be sure that we have found the item in question on the list. The limiting case here would be if the item sought is the first one on the list. We can generalise from this to the following clause:
member(Item, List):- List = [Item|Rest].
This is OK if the item sought is indeed the first item, but what if it isn't?. In that case, we need to ignore the first item and proceed to check the remainder (i.e. the tail) of the list:
member(Item, [Head|Tail]):- member(Item, Tail).
If
the item sought is on the list, this procedure will find it, and Prolog will
respond with 'yes'; if not, it will fail, and Prolog will respond with 'no'.[4]
Note that, as usual with many Prolog
predicates, member/2 can be used to generate solutions; if the second
argument is instantiated to a list and the first is a variable, the predicate
can to used to select items off the list:
| ?- member(X, [a, b, c]). X = a ? ; X = b ? ; X = c ? ; no
[4] This definition of member/2 can be simplified slightly by 'unfolding' the call to =/2 and placing it in the head of the rule, to give:
member(Item, [Item|List]). member(Item, [Head|Tail]):- member(Item, Tail).
If
you consult this program into SICStus, you will get the following error
messages.
{Warning: [List] - singleton variables in member/2 in lines 1-2}
{Warning: [Head] - singleton variables in member/2 in lines 2-5}
This is because, in the first clause, the variable List only occurs
once, as does the variable Head in the second clause. Since the
occurrence of a unique variable in Prolog code often indicates a typing error,
SICStus warns you when this occurs. The code will still run OK, but if you want
to avoid the warnings, you can us the so-called 'anonymous' variable, typed
with just the underscore character for all singleton variables. Different
occurrences of the anonymous variable in the same clause do not unify.
The above definition of member can be rewritten as
member(Item, [Item|_]). member(Item, [_|Tail]):- member(Item, Tail).