Prolog 添加 N 到 0 到列表

Question

我想将结果列表 N 添加到 0 位数字。

示例查询

?- add(5,R).

应该return答案：

R = [5,4,3,2,1,0].

我已经尝试了以下代码，但它没有用。

add(0, 0).
add(N, [R]) :-
   N1 is N-1,
   add(N1, [R|N]).

Answer 1

你太接近了！

add(0, [0]).
add(N, [N|R]) :- 
  N > 0, 
  N1 is N-1, 
  add(N1, R).

那么，这里有什么不同？

1. add(0, [0]) 有 [0] 而不是 0 因为你正在构建一个列表，而不是一个整数；否则你会得到相当尴尬的 [5,4,3,2,1|0] 结果。

2. N > 0 作为守卫，以确保我们不会在达到基本情况后永远循环遍历负数。

3. 这项工作是在 add/2 第二个子句的头部而不是它的主体中完成的。也就是说，我们的模式是 add(N, [N|R]) 而不是 add(N, [R])。这是因为这个术语将 N 添加到列表的头部而不是在循环之前添加它。

4. 同样，你在[R|N]中有一个简单的反转；这将构建列表有点倒退。

总而言之，我认为你们非常亲密。在提示符下多做一些试验可能就足以修复它。您尝试过使用 trace/0 了吗？

Answer 2

使用clpfd!

:- use_module(library(clpfd)).
:- set_prolog_flag(toplevel_print_anon, false).

我们这样定义n_to_0/2：

n_to_0(N,[Z|Zs]) :-
   length(Zs,N),
   [Z|Zs] ins 0..N,
   chain([Z|Zs],#>).

OP 给出的示例查询：

?- n_to_0(5,Zs).
Zs = [5,4,3,2,1,0].

使用 n_to_0/2 的最一般查询怎么样？

?- n_to_0(N,Zs).
  N = 0, Zs =             [0]
; N = 1, Zs =           [1,0]
; N = 2, Zs =         [2,1,0]
; N = 3, Zs =       [3,2,1,0]
; N = 4, Zs =     [4,3,2,1,0]
; N = 5, Zs =   [5,4,3,2,1,0]
; N = 6, Zs = [6,5,4,3,2,1,0]
...

---

编辑

@JanWielemaker 指出 n_to_0/2（如上定义）非常慢——特别是与非 clpfd 对应物相比时： 非常感谢您的报告！ 自己看看...

?- between(1, 3, E),
   N is 10^E, 
   ((numlist(0, N, _Zs0), reverse(_Zs0, _)), T1_in_ms),
   call_time(n_to_0(N, _), T2_in_ms).
  E = 1, N =   10, T1_in_ms = 0, T2_in_ms =     1
; E = 2, N =  100, T1_in_ms = 0, T2_in_ms =   104
; E = 3, N = 1000, T1_in_ms = 0, T2_in_ms = 29701
...

查看 ！

Answer 3

我们展示了 的模拟（它处理从 0 开始 升序 的连续整数）。

:- use_module(library(clpfd)).
:- set_prolog_flag(toplevel_print_anon, false).

基于我们查询：

?- N = 10, Zs = [N|_Zs0], length(_Zs0, N), equidistant_stride(Zs, -1).
N = 10, Zs = [10,9,8,7,6,5,4,3,2,1,0].

让我们重新[​​=47=]¹我们在!

中进行的运行时间测量

?- between(1,6,E),
   N is 10^E,
   garbage_collect,
   (numlist(0, N, _), T1_in_ms),
   garbage_collect,
   call_time((_Zs = [N|_Z], length(_Z, N), equidistant_stride(_Zs, -1)), T2_in_ms).
  N =      10, T1_in_ms =  0, T2_in_ms =   0
; N =     100, T1_in_ms =  1, T2_in_ms =   0
; N =    1000, T1_in_ms =  1, T2_in_ms =   1
; N =   10000, T1_in_ms =  3, T2_in_ms =  12
; N =  100000, T1_in_ms = 14, T2_in_ms =  32
; N = 1000000, T1_in_ms = 90, T2_in_ms = 280.

---

编辑

此答案的过去修订版无意中忽略了 运行 时间测量以支持 clpfd。如何？ 很简单：reverse/2 进球后 numlist/3，尽管在这种情况下毫无用处。

现在应该更好了：感谢 2 @JanWielemaker 4 报告！

---

_{脚注 1： 使用 SWI-Prolog 版本 7.3.11（64 位）。}