Next: Some General Program Up: The Problem of Previous: Negation as Failure

## 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).

```
together with the set of facts defining odd/1.

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)).

```
Thus `\+`/1 provides extra expressivity as we do not need a set of facts to define even/1.
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(Tail).

sublist([]).

```
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:
```

`\+`(sublist(Head)),

nested_list(Tail).

sublist([]).

```
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.

Next: Some General Program Up: The Problem of Previous: Negation as Failure

Paul Brna
Mon May 24 20:14:48 BST 1999