Test for Existence

We want to determine that some collection of objects has at least one object with a desired property. For example, that a list of terms has at least one term which is also a list. Here is the general schema:

 
 list_existence_test( Info,[HeadTail]):-

		        element_has_property( Info,Head).

 list_existence_test( Info,[HeadTail]):-

		        list_existence_test( Info,Tail).

We outline two examples. The first has 0 parameters. We test whether a list contains lists using nested_list/1--- e.g. we want the goal nested_list([a,[b],c]) to succeed.

 
nested_list([HeadTail]):-

		       sublist(Head).

nested_list([HeadTail]):-

		       nested_list(Tail).

sublist([]).

sublist([HeadTail]).

Note that, for any non-empty list, a goal involving nested_list/1 can be matched using either the first or the second clause. This produces the possibility that, if the goal is redone then it may once again succeed (if there is more than one occurrence of a sublist). This may not be what is wanted. You can test this with the query:

 
?-  nested_list([a,[b],c,[],[d],e]),write(y),fail.

which produces the output yyyno because the first subgoal succeeds, the second writes y and the third fails ( fail/0 always fails!). Then backtracking occurs to write/1 which fails.

We then backtrack into nested_list/1 which can be resatisfied. Basically, the first success had terminated with the subgoal sublist([b]) succeeding for the goal nested_list([[b],c,[],[d],e]). We can resatisfy this goal using the second clause which then sets up the goal nested_list([c,[],[d],e]) which will eventually succeed. This will result in another y being written and, after a while, another attempt to resatisfy nested_list/1 etc.

The point is that you are safe when no goal can be satisfied via different clauses. We could repair the above using an extralogical feature which is described in chapter 9 (the cut).

The program for member/2 fits into this pattern when used with mode member(+,+).

 
member(Element,[ElementTail]).

member(Element,[HeadTail]):-

		       member(Element,Tail).

In case you are wondering where the element_has_property item has gone then we can rewrite member/2 to the logically equivalent:

 
member(Element,[HeadTail]):-

			Element = Head.

member(Element,[HeadTail]):-

		       member(Element,Tail).

Now we can see how this definition fits the above schema.