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