Best way to generate integer numbers in Prolog

问题:

I want to generate integer numbers and I'm looking for the best way to do this. Example:

?- number2(N).
N = 0;
N = 1;
N = 2;
...
(and so on)

Now I'm simply using length/2:

number2(N) :- length(_, N).

But I think that there should be some better way (without creating temporary list). I could probably write some code myself basing on code of length/2 but I'm looking for solution that employs already existing, built-in predicates. Is there any built-in predicate that would work better than length/2? I couldn't find anything like that.

回答1:

It is hard to top your solution ; and probably it is not worth the effort. After all, there are now three suggestions that all are incorrect for one case or another:

?- time( (number2_gk(N), N == 10000) ). % your original
% 20,002 inferences, 0.007 CPU in 0.007 seconds (99% CPU, 3006132 Lips)
N = 10000 

?- time( (number2_cc(N), N == 10000) ). % quadratic overhead
% 50,025,001 inferences, 28.073 CPU in 28.196 seconds (100% CPU, 1781945 Lips)
N = 10000 

?- time( (next_integer(N), N == 10000) ).
% 20,002 inferences, 0.011 CPU in 0.011 seconds (100% CPU, 1822247 Lips)
N = 10000 

However, number2_cc(-1) and next_integer(-1) simply loop, length/2 actually should produce a domain error, like SICStus and many other systems do.

As you can see, CC's solution is worse than your original one.

Also the suggestion by mat produces different behavior in the following situation:

goal_expansion(length(Ls,L), between(0,infinite,L)) :-
   var_property(Ls, fresh(true)).

as(N) :-
   length(L,N),
   phrase(a, L).

a --> [a], a.
a --> [].

The goal as(N) now loops instead of enumerating all N.

If you really insist on an improvement, consider the following tail-recursive solution using library(clpfd):

nat(N) :-
   nat(N, 0).

nat(N, N0) :-
  N #>= N0,
  (  N = N0
  ;  N1 is N0+1,
     nat(N, N1)
  ).

?- time( (nat(N), N == 10000) ).
% 1,850,152 inferences, 0.544 CPU in 0.545 seconds (100% CPU, 3399793 Lips)

Which is only an improvement for queries like the following. Otherwise it is just a waste of resources.

?- N in 1..2, nat(N).

回答2:

To keep between/3 pure, i.e. only with integer arguments,
I have started providing the following predicate above/2
in a library (for the source code see here):

/**
 * above(L, X):
 * The predicate succeeds for every integer X above the integer L.
 */
% above(+Integer, -Integer)

So if you really want to generate integer numbers,
and not natural numbers, you can use:

gen_int(X) :-
    above(0, Y),
    (X is Y; X is -Y-1).

The above will give 0, -1, 1, -2, etc.. . If you want to
generate natural numbers including zero, you can use:

gen_nat(X) :-
    above(0, X).

The above will give 0, 1, 2, etc... The names gen_int/1
and gen_nat/1 are inspried by SICStus Prolog, see here.

Hope this helps.

Bye

回答3:

A tail-recursive alternative to Carlo's solution is:

next_integer(I) :-
    next_integer(0, I).

next_integer(I, I).
next_integer(I, J) :-
    I2 is I + 1,
    next_integer(I2, J).

A sample query:

?- next_integer(I).
I = 0 ;
I = 1 ;
I = 2 ;
I = 3 ;
...

You can also easily start from an integer other than zero. For example:

?- next_integer(-5, I).
I = -5 ;
I = -4 ;
I = -3 ;
I = -2 ;
I = -1 ;
I = 0 ;
I = 1 ;
I = 2 ;
I = 3 ;
...