How to generate all pairs of natural numbers in Prolog?

Question

Problem statement:

I'm trying to generate all pairs of natural numbers in Prolog (SWI-Prolog),

i.e. formally have a function f(X,Y), such that:

after calling f(X,Y) with unbound variables X, Y, for each pair of natural numbers (m, n) there exists an n0 such that after pressing semicolon n0 times, Prolog will return (X,Y)=(m,n).

Failed attempt:

I was hoping to write the function using Cantor's pairing function. In short, it enumerates the pairs as follows: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3), (4,0)...

I expressed it as follows:

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'

However because of how Prolog search actually works, this ends up with the 2nd rule repeatedly invoking itself, ad infinitem, eventually crashing due to running out of stack space (the only results it returns before that are (0,0) and (1,0), then it gets stuck, repeatedly failing the 2nd rule on '0 is 0+1').

Do you have any ideas how to make this or any other elegant approach work?

Thank you.

Edit - my solution.

Based on the accepted answer (thanks!), I wrote the following code, working as intended:

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.

When used:

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

Just as a point of terminology, Prolog doesn't have functions but predicates. They aren't the same thing. — lurker

mat mat · Accepted Answer · 2018-01-01T22:10:15

I give you a start:

Let us start with a predicate that creates all natural numbers on backtracking, yielding a single such number with each solution:

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

Sample query:

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

Then, we observe that we can generate such pairs without falling into an infinite loop by restricting the sum of each pair. For example:

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

Sample query:

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

This is obviously not perfect: For example, some pairs are reported redundantly. However, the general idea should be clear: Use a good building-block to keep the generation of pairs in check.

How to generate all pairs of natural numbers in Prolog?

Problem statement:

Failed attempt:

Edit - my solution.

1 Answers