Prolog add N to 0 to the list

Question

I want to add to Result list N to 0 digits.

The sample query

?- add(5,R).

should return the answer:

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

I already tried the following code but it did not work.

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

Answer 1

You're so close!

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

So, what's different here?

1. add(0, [0]) has [0] instead of 0 because you're building a list, not an integer; otherwise you get the rather awkward looking [5,4,3,2,1|0] result.

2. N > 0 as a guard, to ensure that we don't loop crawling through negative numbers forever once we hit the base case.

3. The work is being done in the head of the second clause of add/2 instead of the body of it. To wit, our pattern is add(N, [N|R]) instead of add(N, [R]). This is because this term adds N to the head of the list rather than adding it before recurring.

4. Similarly, you have a simple inversion in [R|N]; this would build lists kind of backwards.

All in all, I think you were very close. A little more experimenting at the prompt may have been sufficient to fix it. Have you tried using trace/0 yet?

Answer 2

We show an analog of this answer (which dealed with consecutive integers ascending from 0).

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

Based on equidistant_stride/2 we query:

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

Let's re-run¹ the runtime measurements we did in this previous answer!

?- between(1,6,E),
   N is 10^E,
   garbage_collect,
   call_time(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.

---

Edit

Past revisions of this answer inadvertently sk(r)ewed runtime measurements in favor of clpfd. How? It's simple: A reverse/2 goal followed numlist/3, even though it is useless in this setting.

This should be better now: Thx 2 @JanWielemaker 4 reporting!

---

_{Footnote 1: Using SWI-Prolog version 7.3.11 (64-bit).}

Answer 3

Use clpfd!

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

We define n_to_0/2 like this:

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

Sample query as given by the OP:

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

How about the most general query using 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]
...

---

Edit

@JanWielemaker pointed out that n_to_0/2 (as defined above) is abysmally slow—particularly when comparing it to its non-clpfd counterpart: Thanks a lot for reporting! See for yourself...

?- between(1, 3, E),
   N is 10^E, 
   call_time((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
...

Check out this new, improved, clpfd-based answer!