Prolog: Wyliczyć wszystkie elementy niezmiernie nieskończonych wyników

Question

Czy są jakieś implementacje prolog, które są w stanie wyliczyć wszystkie elementy niezliczonych wyników?

Rozważmy wyliczenie wszystkich par liczb naturalnych. Jeśli wymieniamy pary w kolejności {(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...}, możemy może wyliczyć wszystkie pary. Jednakże, jeśli wyliczymy pary w kolejności {(0,0), (0,1), (0,2), (0,3) ...} jako następujący program prologu GNU, nigdy nie osiągniemy par takich jak (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

sugeruję stosowanie generatora z możliwością ograniczonej wartości górnej, jak między/3, zamiast NAT/1, jest w stanie nasycenia "wewnętrzne poziomu. Na przykład

?- 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 nie pozwala between(0,inf,A), więc może dodać current_prolog_flag(max_integer,Z) i używać Z zamiast inf.

Answer 2

Można użyć CLPFD (ograniczenie programowania logiki nad domenami skończonych) do generowania wszystkich par:

nat(0). 
nat(X1) :- nat(X), X1 is X + 1. 

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

to około następuje przechodzenie racjonalnego matrycy numer używany w klasycznej Cantor's proof that the rationals are countable (działa w tym samym kierunku na każdej przekątnej zamiast przemiennego), w wyniku czego:

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

powodem, dla którego nie jest łatwo wykonalne z tej definicji nat/1 że masz to, że kolejność chcesz wymaga poszukiwania drzewa próbnego, które nie jest ani głębokie jako pierwsze, ani szerokość jako pierwsza. Odpowiedź @CapelliC jest pierwszym rozszerzeniem. Odpowiedź @lurkera daje ci odpowiedzi, których szukasz.

Jeśli z tego czy innego powodu nie chcesz używać CLPFD, o to rozwiązanie w czystej Prologu:

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

To po prostu opisuje w jaki sposób „przenieść” poprzez racjonalne numer matrycy wyliczyć wszystkie pary liczb całkowitych.

Answer 4

Po raz pierwszy pomyślałem, że rozwiązanie CappeliCs jest w porządku. Ale patrząc na lurkers
CLP rozwiązanie (FD), myślę, że po to kompletne rozwiązanie Prolog:

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

Bye

PS: Oto przykład uruchomić w 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 X-A. 

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