Prolog: list all elements of countably endless results

Question

Are there any prolog implementations that can list all elements of countably infinite results?

Consider listing all pairs of natural numbers. If we list the pairs in order {(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...}, we can list all pairs. However, if we list the pairs in the order {(0,0), (0,1), (0,2), (0,3) ...} as the next GNU prolog program, we never reach such pairs as (1,1).

% cat nats.pl nat(0). nat(X1) :- nat(X), X1 is X + 1. pair_of_nats(X, Y) :- nat(X), nat(Y). % prolog GNU Prolog 1.3.0 By Daniel Diaz Copyright (C) 1999-2007 Daniel Diaz | ?- ['nats.pl']. compiling /home/egi/prolog/nats.pl for byte code... /home/egi/prolog/nats.pl compiled, 4 lines read - 762 bytes written, 9 ms yes | ?- pair_of_nats(X,Y). X = 0 Y = 0 ? ; X = 0 Y = 1 ? ; X = 0 Y = 2 ? ; X = 0 Y = 3 ? 

Answer 1

The reason you find it difficult to complete this nat/1 definition is because the required order requires a search for a evidence tree that is neither depth nor width. Answer @CapelliC is the first width search. The answer from @lurker gives you the answers you are after.

If for one reason or another you do not want to use CLPFD, here is the solution in pure Prolog:

 pairs(A, B) :- pairs_1(0, 0, A, B). pairs_1(A, B, A, B). pairs_1(A, B, RA, RB) :- ( succ(B1, B) -> succ(A, A1), pairs_1(A1, B1, RA, RB) ; succ(A, B1), pairs_1(0, B1, RA, RB) ). 

It simply describes how to "navigate" through a matrix of rational numbers to list all pairs of integers.

Answer 2

You can use CLPFD (programming of domain restriction logic) to generate all pairs:

 nat(0). nat(X1) :- nat(X), X1 is X + 1. pairs((A, B)) :- nat(X), A + B #= X, fd_labeling([A,B]). 

This roughly follows the passage of the rational number matrix used in the classic Cantor proof that rationality is countable (works in one direction on each diagonal instead of alternating), resulting in:

 | ?- pairs(P). P = (0,0) ? ; P = (0,1) ? ; P = (1,0) ? ; P = (0,2) ? ; P = (1,1) ? ; P = (2,0) ? ; P = (0,3) ? ; P = (1,2) ? ; P = (2,1) ? ; P = (3,0) ? ; P = (0,4) ? ; ... 

Answer 3

At first, I thought the CappeliCs solution was fine. But then, looking at lurkers
CLP (FD), I think this is a complete Prolog solution:

 ?- between(0, inf, X), between(0, X, A), B is XA. 

Bye

PS: Here is an example running in SWI-Prolog:

 Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.33) Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam ?- [user]. pair((A, B)) :- between(0, inf, X), between(0, X, A), B is XA. ?- pair(P). P = (0, 0) ; P = (0, 1) ; P = (1, 0) ; P = (0, 2) ; P = (1, 1) ; P = (2, 0) ; ... 

Answer 4

I would suggest using a generator with an additional limited upper value, for example between / 3, instead of nat / 1, to saturate the "internal levels". For instance,

 ?- between(0,inf,A),between(0,A,B). A = B, B = 0 ; A = 1, B = 0 ; A = B, B = 1 ; A = 2, B = 0 ; A = 2, B = 1 ; A = B, B = 2 ; A = 3, B = 0 .... 

GNU Prolog does not allow between(0,inf,A) , so maybe add current_prolog_flag(max_integer,Z) and use Z instead of inf .