在 Prolog 中生成整数的最佳方法

Question

我想生成整数，并且我正在寻找实现此目的的最佳方法。示例：

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

现在我只是使用

length/2

:

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

但我认为应该有一些更好的方法（不创建临时列表）。我可能可以根据

length/2

的代码自己编写一些代码，但我正在寻找采用现有内置谓词的解决方案。是否有比

length/2

更好的内置谓词？我找不到类似的东西。

Answer 1

很难超越你的解决方案；也许这不值得付出努力。毕竟，现在有三种建议，但对于某种情况来说都是不正确的：

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

但是，

number2_cc(-1)

和

next_integer(-1)

只是循环，

length/2

实际上应该产生域错误，就像SICStus和许多其他系统所做的那样。

如您所见，CC 的解决方案比您原来的解决方案更糟糕。

垫子的建议在以下情况下也会产生不同的行为：

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 --> [].

目标

as(N)

现在循环，而不是枚举所有

N

。

如果您确实坚持改进，请考虑以下使用

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)

这只是对如下查询的改进。否则只是浪费资源。

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

Answer 2

保持/3之间的纯，即仅使用整数参数，
我已经开始提供以下谓词上面/2
在库中（源代码请参阅[链接已删除]）：

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

所以如果你真的想生成整数，
而不是自然数，您可以使用：

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

上面将给出 0、-1、1、-2 等...。如果你愿意
生成包括零的自然数，你可以使用：

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

上面将给出 0、1、2 等...名称 gen_int/1
和 gen_nat/1 受到 SICStus Prolog 的启发，请参阅此处。

希望这有帮助。

再见

Answer 3

卡罗解决方案的尾递归替代方案是：

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

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

示例查询：

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

您还可以轻松地从零以外的整数开始。例如：

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