Списки различий в Прологе и изменяемых переменных

Question

Являются ли списки различий средством "обойти" тот факт, что переменные являются неизменяемыми в прологе?

Т.е. если я реализую добавление используя списки различий:

diff_append(OpenList, Hole, L2) :-
    Hole = L2.

А затем запустите:

X=[a,b,c|Hole], diff_append(X, Hole, [d,e,f]).

X, в некотором смысле, использовался как изменяемая переменная. Для наших намерений и целей это было изменено?

Другими словами, тот факт, что мы смогли изменить X (изменяемый) вместо того, чтобы создавать новый список, скажем, Z (неизменяемый), делает привлекательными списки различий. Так почему бы просто не иметь изменяемые переменные?

Обновить:

diff_append2(OpenList-Hole,L2):-
    Hole=L2.

X=[a,b,c|Ho]-Ho,diff_append2(X,[d,e,f]).

Answer 1

Списки различий, скорее, используются для обхода другого ограничения: вам необходимо пройти весь список, чтобы "добавить" его конец (вспомните односвязный список, в котором есть указатель на первый элемент, но не на страж).

В коде: так как список [a, b, c] это (традиционно) вложенный термин .(a, .(b, .(c, []))), добавив d в конце это означает "отслаивание" каждого термина перед заменой [] в конце (в центре) с .(d, []), Итак, реализовать append/3:

append([], L, L).
append([H|T], L, [H|R]) :-
    append(T, L, R).

как это традиционно осуществляется.

Это еще один ответ, который охватывает тему довольно широко.

Что-то, что этот ответ не затрагивает, - то, что предикаты библиотеки, что списки "возврата" могут предложить версию предиката с разностным списком, из соображений эффективности, на случай, если вы захотите добавить в конец списка. Примеры будут read_pending_codes/3 а также read_pending_chars/3 или версия с четырьмя аргументами findall/4,

DCG - это удобный способ работы со списками различий без явной передачи двух аргументов для списка и хвоста.

Реализация очереди

Три самые основные операции для очереди: создание пустой очереди, толчок назад и выталкивание спереди:

%% empty_queue(-Queue)
% make an empty queue
empty_queue(queue(0, Q, Q)).

%% queue_head(?Queue, ?Head, ?Queue0)
% Queue, with Head removed, is Queue0
queue_head(queue(s(X), [H|Q], Q0), H, queue(X, Q, Q0)).

%% queue_last(+Queue0, +Last, -Queue)
% Queue0, with Last at its back, is Queue
queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)).

Как следует заметить, queue_head/3 позволит вам выскочить с фронта или подтолкнуть к передней части очереди. queue_last/3 только позволяет нажать на заднюю часть: после нажатия на элемент у вас нет (постоянного времени) доступа к элементу до того, как он окажется в очереди.

Первый аргумент queue/3 Термин используется для предотвращения того, что Ричард О'Киф называет "галлюцинирующими" переменными, то есть выталкивает из очереди больше элементов, чем было помещено в нее. Интересно пропустить этот первый аргумент из предикатов выше и посмотреть, что произойдет:

?- empty_queue(Q0), queue_head(Q0, H, Q1).
Q0 = queue([H|_G341], [H|_G341]),
Q1 = queue(_G341, [H|_G341]).

вместо того, чтобы потерпеть неудачу.