Why does this recursive Prolog predicate add some "_1508"-like numbers to lists?

Question

My task is to split a given sorted list (LSorted) into several other ones, where the first one would contain values from the LSorted that are smaller than the first prime number (1 is not considered prime) (from Primes list), the second one would contain values from LSorted smaller than the second prime number but greater or equal to the first prime, etc.

ans(L, Res):-
    max_list(L, X),             /*determine the max value X of L*/
    listPrimes(X, Primes),      /*generate a list of primes up to X and the prime greater than X*/
    msort(L, LSorted),          /*sort L*/
    ans_recur(LSorted, Primes, Res),!.

ans_recur([], _, [[]|[]]).

ans_recur([InH|Input], [PrimeH|Primes], [[InH|Res]|ResT]):-
    InH < PrimeH,
    ans_recur(Input, [PrimeH|Primes], [Res|ResT]).

ans_recur([InH|Input], [_|Primes], [_|ResT]):-
    ans_recur([InH|Input], Primes, ResT).

When I run a query: ans([1,2,3,4], L)., I get this result:

L = [_1508, [1|_1522], [2|_1534], [3, 4]], while I expect [[1], [2], [3,4]]. The program does "put" the numbers into the "correct" lists, but adds some values like _1508. As far as I understand, the reason for that is that Prolog is trying to assign some value to Res in ans_recur predicate, but why does it do that?
Tracing:

Call:ans([1, 1, 2, 2, 3, 4], _13636)
 Call:lists:max_list([1, 1, 2, 2, 3, 4], _14050)
 Exit:lists:max_list([1, 1, 2, 2, 3, 4], 4)
 Call:listPrimes(4, _14080)
 Exit:listPrimes(4, [1, 2, 3, 5])
 Call:sort([1, 1, 2, 2, 3, 4], _14224)
 Exit:sort([1, 1, 2, 2, 3, 4], [1, 2, 3, 4])
 Call:ans_recur([1, 2, 3, 4], [1, 2, 3, 5], _13636)
 Call:1<1
 Fail:1<1
 Redo:ans_recur([1, 2, 3, 4], [1, 2, 3, 5], _13636)
 Call:ans_recur([1, 2, 3, 4], [2, 3, 5], _14156)
 Call:1<2
 Exit:1<2
 Call:ans_recur([2, 3, 4], [2, 3, 5], [_14174|_14168])
 Call:2<2
 Fail:2<2
 Redo:ans_recur([2, 3, 4], [2, 3, 5], [_14174|_14168])
 Call:ans_recur([2, 3, 4], [3, 5], _14168)
 Call:2<3
 Exit:2<3
 Call:ans_recur([3, 4], [3, 5], [_14204|_14198])
 Call:3<3
 Fail:3<3
 Redo:ans_recur([3, 4], [3, 5], [_14204|_14198])
 Call:ans_recur([3, 4], [5], _14198)
 Call:3<5
 Exit:3<5
 Call:ans_recur([4], [5], [_14234|_14228])
 Call:4<5
 Exit:4<5
 Call:ans_recur([], [5], [_14252|_14228])
 Exit:ans_recur([], [5], [[]])
 Exit:ans_recur([4], [5], [[4]])
 Exit:ans_recur([3, 4], [5], [[3, 4]])
 Exit:ans_recur([3, 4], [3, 5], [_14204, [3, 4]])
 Exit:ans_recur([2, 3, 4], [3, 5], [[2|_14204], [3, 4]])
 Exit:ans_recur([2, 3, 4], [2, 3, 5], [_14174, [2|_14204], [3, 4]])
 Exit:ans_recur([1, 2, 3, 4], [2, 3, 5], [[1|_14174], [2|_14204], [3, 4]])
 Exit:ans_recur([1, 2, 3, 4], [1, 2, 3, 5], [_14154, [1|_14174], [2|_14204], [3, 4]])
 Exit:ans([1, 1, 2, 2, 3, 4], [_14154, [1|_14174], [2|_14204], [3, 4]])
L = [_1282, [1|_1296], [2|_1308], [3, 4]]

Thanks in advance.

_1508 is a free variable. The numbe ris used such that you can see if the variable is used somewhere else. Since you di not bind Primes to anything, it remains that way. — Willem Van Onsem
@WillemVanOnsem thanks! but Primes is binded, in line `listPrimes(X, Primes). sorry, perhaps i should've clarified this in the question itself. — Andrewklayk

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2020-04-25T09:13:15

ans_recur([InH|Input], [PrimeH|Primes], [[InH|Res]|ResT]):-
    InH < PrimeH,
    ans_recur(Input, [PrimeH|Primes], [Res|ResT]).

ans_recur([InH|Input], [_|Primes], [_|ResT]):-
    ans_recur([InH|Input], Primes, ResT).

What you are trying to express in these clauses is something like this:

if InH is less than the next prime, it should be part of the current running result
otherwise, it should be part of some later running result

But in the last case, the "current running result" is finished, it has no more elements. So its tail, which is so far open, must be closed. You need to change the head of the last clause accordingly:

ans_recur([InH|Input], [_|Primes], [[]|ResT]):-

This now behaves like this:

?- ans_recur([1,2,3,4,5,6,7,8,9,10], [2,3,5,7,11], Result).
Result = [[1], [2], [3, 4], [5, 6], [7, 8, 9, 10]] ;
Result = [[1], [2], [3, 4], [5], [6, 7, 8, 9|...]] ;
Result = [[1], [2], [3, 4], [], [5, 6, 7, 8|...]] ;
Result = [[1], [2], [3], [4, 5, 6], [7, 8, 9, 10]] .  % further incorrect answers

The problem is that you don't express the "otherwise" condition explicitly, and Prolog will not guess implicitly that it was what you meant. You can change the last clause to this:

ans_recur([InH|Input], [PrimeH|Primes], [[]|ResT]):-
    InH >= PrimeH,
    ans_recur([InH|Input], Primes, ResT).

And only get the expected answer:

?- ans_recur([1,2,3,4,5,6,7,8,9,10], [2,3,5,7,11], Result).
Result = [[1], [2], [3, 4], [5, 6], [7, 8, 9, 10]] ;
false.

As you can see, I only dealt with your implementation of ans_recur/3. There might be more bugs lingering in the rest of the code. We cannot tell because the code you posted is incomplete. In the future, please only post complete programs. Many contributors will not bother to try to complete your question for you, and you will get fewer answers.

Why does this recursive Prolog predicate add some "_1508"-like numbers to lists?

1 Answers