Define a predicate that holds of both numeral and their negative and enumerate them

Question

I need to define a predicate plusminus(X). that holds of 2 numerals, s(0) which is the successor of 0 meaning s(s(s(0))) = 3 and their negatives p(0) which represents -1 meaning p(p(p(0))) = -3 and can be enumerated such that:

? plusminus(X).
  X = 0 ? ;
  X = s(0) ? ;
  X = p(0) ? ;
  X = s(s(0)) ? ;
  X = p(p(0)) ? ;
  X = s(s(s(0))) ? ;
  X = p(p(p(0))) ? ;
...

I have the following solution but I don't get it in the same order as I want it to be,

negative(0, 0).
negative(s(X), p(Y)) :- negative(X, Y). 

plusminus(X) :- negative(X, _).

How do I change the following to get me the output I desire?

Answer 1

From my observation, in order for two cases separated by an 'or' (;), there must be some other predicate within the function that is always satisfied, in order for both of the cases separated by the 'or' to be called one after the other. I might be wrong in this, however, from my testing, I have noticed that the following solution doesn't work:

pOm(X) :- numeral(X) ; neg(_, X).

This solution gives the following output, even though the solution makes complete sense.

?- pOm(X).
X = 0 ;
X = s(0) ;
X = s(s(0)) ;
X = s(s(s(0))) .
...

When we look at another solution, however:

pOm(0).
pOm(X) :- numeral(Y), neg(Y, Z), (X = s(Y); X = p(Z)).

This solution gives the following output:

?- pOm(X).
X = 0 ;
X = s(0) ;
X = p(0) ;
X = s(s(0)) ;
X = p(p(0)) ;
X = s(s(s(0))) ;
X = p(p(p(0))) .
...

Although I don't exactly know for sure why this one works and the previous one doesn't, I do, however, have a hypothesis.

It looks like the second solution has two predicates that are always going to be called, numeral(Y) and neg(Y, Z). This property seems to enforce the pOm(X) predicate to satisfy the remaining conditions one by one. So in one case, it would satisfy X = s(Y), and in the other, it would satisfy X = p(Z), contiguously.

Once again, this is only my observation. If there is a solid reason for why the second solution works and the first one doesn't, I would be grateful if anyone could explain it.

Hope I helped :).

Answer 2

This answer is a bit bigger, but it demonstrates a more general point about enumerating answers fairly: If you define a "size" measure for your objects, you can force enumeration by increasing size.

First, a definition of numerals, which are either 0 or positive or negative:

numeral(0).
numeral(X) :-
    positive(X).
numeral(X) :-
    negative(X).

positive(s(0)).
positive(s(X)) :-
    positive(X).

negative(p(0)).
negative(p(X)) :-
    negative(X).

Examples:

?- numeral(N).
N = 0 ;
N = s(0) ;
N = s(s(0)) ;
N = s(s(s(0))) .

We can see that this is unfair: It does not generate negative numbers. It does accept them, however:

?- numeral(p(p(p(0)))).
true ;
false.

In this particular case we can force enumeration of negative numbers (only):

?- Negative = p(_), numeral(Negative).
Negative = p(0) ;
Negative = p(p(0)) ;
Negative = p(p(p(0))) ;
Negative = p(p(p(p(0)))) .

Unlike the other answer, this doesn't accept numerals with mixed constructor symbols:

?- numeral(p(s(p(0)))).
false.

Now for the "size" measure. This is basically just the absolute value of a numeral. We define it separately for positive and negative numerals, as before:

numeral_size(0, 0).
numeral_size(Positive, Size) :-
    positive_size(Positive, Size).
numeral_size(Negative, Size) :-
    negative_size(Negative, Size).

positive_size(s(0), s(0)).
positive_size(s(X), s(Size)) :-
    positive_size(X, Size).

negative_size(p(0), s(0)).
negative_size(p(X), s(Size)) :-
    negative_size(X, Size).

(Note that this is the same as the definition of numeral/1, just with an extra size argument everywhere.)

Now plusminus/1 can first enumerate (non-negative) numerals for 0, 1, 2, 3, etc., as the size of each expected answer. Then it enumerates numerals with these sizes; this will force the wanted overall enumeration order of 0, 1, -1, 2, -2, ...

plusminus(X) :-
    numeral(Size),
    numeral_size(X, Size).

Example:

?- plusminus(X).
X = 0 ;
X = s(0) ;
X = p(0) ;
X = s(s(0)) ;
X = p(p(0)) ;
X = s(s(s(0))) ;
X = p(p(p(0))) ;
X = s(s(s(s(0)))) ;
X = p(p(p(p(0)))) .

This is a very general pattern: For example, if you have a predicate describing lists, and you want to enumerate them fairly by increasing size, stick a goal length(List, _N) in front of it. This is the "size" predicate that will force enumeration of lists by size 0, 1, 2, etc.

Answer 3

Two problems with your current approach: the first is that you only give plusminus(X) :- negative(X, _). and never plusminus(X) :- negative(X, _).

The predicate negative/2 doesn't take in X and Y and evaluate to true if X = Y-1, it takes in X and Y and evaluates to true if X is nonnegative and X is Y-1.

The second problem is that you need to first unify a variable (in my example below, B), with a value, then force that value to be positive or negative and unify with X.

This worked when I tested it:

numeral(0).
numeral(s(X)) :- numeral(X).
numeral(p(X)) :- numeral(X).

negative(0, 0).
negative(s(X), p(Y)) :- negative(X, Y). 

plusminus(X) :- X=0;
                numeral(B), (B=X; negative(B,X)), dif(X,0).

It's a little clunky - if you don't mind having 0 returned twice, you can use plusminus(X) :- numeral(B), (B=X; negative(B,X)). instead.