如何在Prolog中生成所有自然数？

Question

问题陈述:

我正在尝试在Prolog(SWI-Prolog)中生成所有自然数字对,

即正式具有功能f(X,Y),以便:

调用后f(X,Y)与未结合的变量X,Y对于每对自然数(M,N)的存在一个N0为使得按压分号N0次后,Prolog的将返回(X,Y)=(m,n).

尝试失败:

我希望使用Cantor的配对功能来编写函数.简而言之,它按如下方式枚举对:(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0) ),(2,1),(1,2),(0,3),(4,0)......

我表达如下:

gen(0,0).                                          % 'root'
gen(M,0) :- gen(0, X), M is X+1.                   % 'jump to the previous diagonal'
gen(M,N) :- gen(X, Y), M is X-1, N is Y+1, N > 0.  % 'a step inside a diagonal'

然而,由于Prolog搜索实际上是如何工作的,这最终导致第二个规则反复调用自身,ad infinitem,最终由于堆栈空间耗尽而崩溃(在它之前返回的唯一结果是(0,0)和(1, 0),然后它被卡住,反复失败第二个规则'0是0 + 1').

---

您有任何想法如何使这个或任何其他优雅的方法工作？

谢谢.

---

编辑 - 我的解决方案.

基于接受的答案(谢谢!),我编写了以下代码,按预期工作:

range(Min, _, Min).
range(Min, Max, Val) :- NewMin is Min+1, Max >= NewMin, range(NewMin, Max, Val).

natnum(0).
natnum(N) :-
    natnum(N0),
    N is N0 + 1.

gen(A,B) :-
    natnum(N),
    range(0, N, B),
    A is N - B.

使用时:

?- gen(X,Y).
X = 0,
Y = 0 ;

X = 1,
Y = 0 ;

X = 0,
Y = 1 ;

X = 2,
Y = 0 ;

X = 1,
Y = 1 ;

X = 0,
Y = 2 ;

X = 3,
Y = 0

and so on...

Answer 1

我给你一个开始:

让我们先从创建上回溯,得到所有自然数谓语单与每个解决方案这样的数字:

natnum(0).
natnum(N) :-
        N #= N0 + 1,
        natnum(N0).

示例查询:

?- natnum(N).
N = 0 ;
N = 1 ;
N = 2 ;
N = 3 ;
etc.

然后,我们观察到我们可以通过限制每对的总和来生成这样的对而不会陷入无限循环.例如:

pair(A-B) :-
        natnum(N),
        N #>= A + B,
        A #>= 0,
        B #>= 0,
        label([A,B]).

示例查询:

?- pair(P).
P = 0-0 ;
P = 0-0 ;
P = 0-1 ;
P = 1-0 ;
P = 0-0 ;
P = 0-1 ;
P = 0-2 ;
P = 1-0 ;
P = 1-1 ;
P = 2-0 ;
P = 0-0 ;
P = 0-1 ;
P = 0-2 ;
P = 0-3 ;
P = 1-0 ;
P = 1-1 .

这显然不是完美的:例如,冗余地报告了一些对.但是,一般的想法应该是明确的:使用一个好的构建块来控制对的生成.