Why prolog outputs a weird tree-like list?

Question

In this Prolog code I intend to list the first N primes,

(...)

biggerPrime(N,P) :-
    isPrime(N),
    P is N,
    !.

biggerPrime(N,P) :-
    N1 = N+1,
    biggerPrime(N1,P).

primeListAcc(0,A,R,R) :- !.

primeList(N,L) :-
    primeListAcc(N,1,[],L).

primeListAcc(N,A,L,R) :-
    N1 is N-1,
    biggerPrime(A,P),
    A1 is P+1,
    primeListAcc(N1,A1,[P|L],R).

And it works fine if I want the list ordered backwards:

?- primeList(5,L).
L = [11, 7, 5, 3, 2].

But if I change the last line of the code from [P|L] to [L|P] like this:

primeListAcc(N,A,L,R) :-
        N1 is N-1,
        biggerPrime(A,P),
        A1 is P+1,
        primeListAcc(N1,A1,[L|P],R).

I get:

?- primeList(5,L).
L = [[[[[[]|2]|3]|5]|7]|11].

What am I missing? This is driving me mad!

Answer 1

Great, so you've discovered the problem of adding elements to the end of a list. In Prolog, we can do it with

add(X,L,Z):- L=[X|Z].

wait, what? How to read this? We must know the calling convention here. We expect L and Z to come in as uninstantiated variables, and we arrange for L from now on to point to a newly created cons node with X at its head, and Z its tail. Z to be instantiated, possibly, in some future call.

IOW what we create here is an open-ended list, L = [X|Z] = [X, ...]:

primeList(N,L) :-
    primeListAcc(N,1,[],L).

primeListAcc(N,A,Z,L) :- N > 0,   % make it explicitly mutually-exclusive,
    N1 is N-1,                    %   do not rely on red cuts which are easily
    biggerPrime(A,P),             %   invalidated if clauses are re-arranged!
    A1 is P+1,                    
    L = [P|R],                    % make L be a new, open-ended node, holding P
    primeListAcc(N1,A1,Z,R).      % R, the tail of L, to be instantiated further

primeListAcc(0,A,R,R).            % keep the predicate's clauses together

We can see now that Z is not really needed here, as it carries the [] down the chain of recursive calls, unchanged. So we can re-write primeListAcc without the Z argument, so that its final clause will be

primeListAcc(0,A,R):- R=[].

Keeping Z around as uninstantiated variable allows for it to be later instantiated possibly with a non-empty list as well (of course, only once (unless backtracking occurs)). This forms the basis of "difference list" technique.

---

To answer your literal question - here, consider this interaction transcript:

1 ?- X=[a|b].

X = [a|b] 
2 ?- X=[a|b], Y=[X|c].

X = [a|b]
Y = [[a|b]|c] 

the [a|b] output is just how a cons node gets printed, when its tail (here, b) is not a list. Atoms, as numbers, are not lists.