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.