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

В этом коде Пролога я собираюсь перечислить первые 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].

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

Источник

2 ответа

Решение

Отлично, вы обнаружили проблему с добавлением элементов в конец списка. В Прологе мы можем сделать это с

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

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

То, что мы создаем здесь, это открытый список, 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 примерно как неэкспонированная переменная, позволяющая позднее создать ее экземпляр, возможно, и с непустым списком (конечно, только один раз (если не произойдет возврат). Это составляет основу техники "списка различий".

Чтобы ответить на ваш буквальный вопрос - рассмотрим следующую запись взаимодействия:

1 ?- X=[a|b].

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

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

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

Источник

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

Источник
Другие вопросы по тегам