Using Negation in Case Selection

We can use \+/1 to define relations more carefully than previously. To illustrate, consider

 
parity(X,odd):-

		       odd(X).

parity(X,even).

The goal parity(7,X) is intended to succeed using the first clause. Suppose that some later goal fails forcing backtracking to take place in such a way that we try to redo parity(7,X). This goal unifies with the rest of the second clause! This is not desirable behaviour. We can fix this using \+/1.

 
parity(X,odd):-

		       odd(X).

parity(X,even):-

		       \+(odd(X)).

If we go back to a previous example found in section 6.3.1 then we can now resolve the problem about how to deal with unwanted backtracking in programs like:

 
nested_list([HeadTail]):-

		       sublist(Head).

nested_list([HeadTail]):-

		       nested_list(Tail).

sublist([]).

sublist([HeadTail]).

The problem is caused by the fact that a goal like nested_list([a,[b],c,[d]]) will succeed once and then, on redoing, will succeed once more. This happens because the goal unifies with the heads of both clauses --- i.e. with nested_list([HeadTail]) (the heads are the same). We can now stop this with the aid of \+/1:

 
nested_list([HeadTail]):-

		       sublist(Head).

nested_list([HeadTail]):-

			 \+(sublist(Head)),

		       nested_list(Tail).

sublist([]).

sublist([HeadTail]).

Note that this is at the price of often solving the identical subgoal twice ---the repeated goal is sublist(Head). Note also that there is never more than one solution for sublist(X).

Finally, we can define \+/1 using call/1 and the cut ( !/0:

 
\+(X):-

			call(X),

			!,

			fail.

\+(X).

This is a definition which essentially states that ``if X, interpreted as a goal, succeeds then \+(X) fails. If the goal X fails, then \+(X) succeeds. To see this is the case, you have to know the effect of the cut --- fail combination ( (!,fail). See later on in this chapter for more details of this.