Почему пролог выводит странный древовидный список?

Question

В этом Prolog код, который я намерен перечислить первые N простых чисел,

(...) 

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). 

И это работает отлично, если я хочу, чтобы список упорядоченный назад:

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

Но если изменить последнюю строку код из [P | L] в [L | P], как это:

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

я получаю:

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

Что мне не хватает? Это сводит меня с ума!

Answer 1

Отлично, так что вы обнаружили проблему добавления элементов в конец end списка. В Prolog мы можем сделать это с помощью

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

wait, what? Как это прочитать? Мы должны знать здесь конвенцию. Мы ожидаем, L и Z прийти как uninstantiated переменных, и мы организуем для L теперь указать на вновь созданную конс узла с X на его голове, и Z его хвост. Z, который будет создан, возможно, в будущем вызове.

IOW что мы создаем здесь есть открытый список, 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 

Мы видим теперь, что Z на самом деле не нужен здесь, так как она несет в себе [] вниз цепочка рекурсивных вызовов, без изменений , Таким образом, мы можем переписать primeListAcc без Z аргумента, так что его окончательное положение будет

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

Сохраняя Z вокруг, как uninstantiated переменная позволяет ему быть позже экземпляр, возможно, с непустым списком, а также (из конечно, только один раз (если не происходит обратное отслеживание)). Это составляет основу техники «разностного списка».

---

Чтобы ответить на ваш буквального вопрос - здесь, рассмотрим это взаимодействие расшифровку:

1 ?- X=[a|b]. 

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

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

[a|b] выход является только как узел против распечатана, когда его хвост (здесь, b) является не список. Атомами, как номера, являются не списки.

Answer 2

Напомним, что список является либо пустым списком [], либо термином с функтором '.' и двумя аргументами, вторым аргументом которого является список. Синтаксис [P|Ps] является сокращенным обозначением для термина '.'(P, Ps), который является списком, если Ps - это список (как в вашем примере). С другой стороны, термин '.'(Ps, P), который также может быть записан как [Ps|P] (как вы это делаете), составляет не список, если P не является списком. Вы можете получить обратный список с reverse/2.