prolog - 定义一个包含数字及其否定的谓词并枚举它们

Question

我需要定义一个谓词 plusminus(X)。 包含 2 个数字，s(0) 是 0 的后继，表示 s(s(s(0))) = 3和它们的负数 p(0) 代表 -1 意味着 p(p(p(0))) = -3 并且可以被枚举为:

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

我有以下解决方案，但我没有按照我想要的顺序得到它，

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

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

如何更改以下内容以获得我想要的输出？

Answer 1

这个答案有点大，但它展示了关于公平枚举答案的一个更普遍的观点:如果您为对象定义“大小”度量，则可以通过增加大小来强制枚举。

首先是数字的定义，要么是0，要么是正数，要么是负数:

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

例子:

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

我们可以看出这是不公平的:它不会生成负数。但是，它确实接受它们:

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

在这种特殊情况下，我们可以(仅)强制枚举负数:

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

与其他答案不同，这不接受带有混合构造函数符号的数字:

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

现在进行“尺寸”测量。这基本上只是一个数字的绝对值。我们像以前一样分别为正数和负数定义它:

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

(请注意，这与 numeral/1 的定义相同，只是到处都有一个额外的大小参数。)

现在plusminus/1可以先枚举0、1、2、3等(非负数)数字，作为每个预期答案的大小。然后它枚举具有这些大小的数字；这将强制所需的整体枚举顺序为 0、1、-1、2、-2 ...

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

例子:

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

这是一个非常通用的模式:例如，如果您有一个描述列表的谓词，并且您希望通过增加大小来公平地枚举它们，请在前面放置一个目标 length(List, _N)它的。这是“大小”谓词，它将强制按大小 0、1、2 等枚举列表。