Understand lists and recursion in Prolog

Question

I'm having a difficult time thinking in Prolog. What is incorrect about this statement:

numberList([], 0).
numberList([H|T], Limit) :-
    H is Limit,
    numberList(T, Limit - 1).

I would like

?- numberList(X,Limit).

to determine [Limit, Limit-1 ... 1] as the only solution for a given value for Limit, ie

?- numberList(X, 100).

would yield X = [100, 99, 98, ..., 1]..

My guess is that there is something pretty wrong with my understanding here for this not to be working. I'm not necessarily asking for a solution to what I am trying to do, I would just like to understand why my first attempt is wrong.

Answer 1

There are two main problems lurking around here:

1- You have troubles getting unification and arithmetic operations at the right places

2- You're not checking your input enough

Remarks about 1- (is)/2 is used to perform arithmetic, here it would be, for example, to substract 1 to Limit. (is)/2 can but should not be used to unify a variable to an already evaluated arithmetic expression. (=)/2 should be prefered (unification).

Remarks about 2- even if you get the operators right, your program'd loop. More on that later.

You won't gain much by just switching operators up yourself, so here is the correct way:

numberList([], 0).
numberList([Limit|T], Limit) :-
    NewLimit is Limit - 1,
    numberList(T, NewLimit).

Here you can see that I use unification implicitely in the head of the second clause, another way to put it is the following:

numberList([], 0).
numberList([H|T], Limit) :-
    H = Limit,
    NewLimit is Limit - 1,
    numberList(T, NewLimit).

But now, as you could see by trying this program out, it finds a correct solution but loops if you ask for another one with ;.

The reason might be harder to spot for the eyes of the beginner: when Prolog succeeds and returns a solution, it can only find new one by exploring choice points left during the execution. Here, the only choice point left is when Limit is 0. So it tries the second clause instead of the first one in that case and loops until it reaches NegativeInfinity. Sadly, since the trip is quite long to get there, it overflows before. The solutions to this problem are to add a guard to the second clause, specifying that Limit should be greater than 0 or to add a cut to the first clause or even better: to do both. Ask if you have troubles doing that yourself!