CODEWITHSUNDEEP
listprolog
ogarogar
ogarogar

Reputation: 345

Creating [1,2,3...,N] list in Prolog

I'd like to create a predicate arrayLEQ(L,N) that is true when L = [1,2,3,...,N].

I tried to do it recursively:

arrayLEQ(L,N) :- arrayLEQ([],L,1,N).
arrayLEQ(L1,L2,N,N) :- append(L1,[N],L2).
arrayLEQ(L1,L2,F,N) :- Fnext is F+1, append(L1,[F],L1n), arrayLEQ(L1n,L2,Fnext,N).

At first I thought that it will work, but sadly it doesn't.

When I do: ?- arrayLEQ(L,5) I get L = [1,2,3,4,5] which is the right answer, but Prolog is ready to look for another answer, which is not wanted.

Would you mind explaining to me what I did wrong and why Prolog tries to look for another answer to this predicate, even if it doesn't exist.

Upvotes: 0

Views: 306

Answers (1)

damianodamiano
damianodamiano

Reputation: 2662

Let's have a look at tracer after the first query succeed:

?- arrayLEQ(L,5).
L = [1,2,3,4,5].
more

 Redo:arrayLEQ([1, 2, 3, 4], _5040, 5, 5)
 Call:_5844 is 5+1
 Exit:6 is 5+1
 Call:lists:append([1, 2, 3, 4], [5], _5854)
 Exit:lists:append([1, 2, 3, 4], [5], [1, 2, 3, 4, 5])
 Call:...
 Call:_5880 is 6+1
 Exit:7 is 6+1
 Call:lists:append([1, 2, 3, 4, 5], [6], _5890)
 Exit:lists:append([1, 2, 3, 4, 5], [6], [1, 2, 3, 4, 5, 6])
 Call:arrayLEQ([1, 2, 3, 4, 5, 6], _5040, 7, 5)
 Call:_5922 is 7+1
 Exit:8 is 7+1
 Call:lists:append([1, 2, 3, 4, 5, 6], [7], _5932)
 Exit:lists:append([1, 2, 3, 4, 5, 6], [7], [1, 2, 3, 4, 5, 6, 7])
 Call:arrayLEQ([1, 2, 3, 4, 5, 6, 7], _5040, 8, 5)
 Call:_5970 is 8+1
 Exit:9 is 8+1
 and so on...

You can see that your program keeps adding element into the list, without stopping. So there are two solutions:

  • Adding a cut (!): arrayLEQ(L1,L2,N,N):- !, append(L1,[N],L2). It works but maybe (in my opinion) there is a better solution.
  • When adding an element, you don't check if you have already passed the threshod you set (in this case 5). So you just have to add F < N before doing Fnext is F+1. So: arrayLEQ(L1,L2,F,N) :- F < N, Fnext is F+1, append(L1,[F],L1n), arrayLEQ(L1n,L2,Fnext,N). (personally i prefer this solution)

So the query now (with second solution):

?- arrayLEQ(L,5).
L = [1, 2, 3, 4, 5].
more.
false.

I suggest you to not use append/3 because in this case is not necessary at all and write someting like this:

orderedList(L,N):-
    orderedList(L,1,N).
orderedList([N],N,N). %you can add a cut ! here, to avoid further search
orderedList([H|T],C,N):-
    C < N,
    H is C,
    C1 is C+1,
    orderedList(T,C1,N).

?- orderedList(L,5).
L = [1, 2, 3, 4, 5]
more
false

Then if you need to return an empty list, wou can add a predicate to handle this case easily... BTW check also the question linked in the comments by @repeat

Upvotes: 2

Related Questions