Пролог список отличий

Question

Рассмотрим следующие программы: одна использует списки различий, а другая нет:

reverse1(List1,R) :- rev1(List1, R-[]).
rev1([], A-A).
rev1([H|T], C-A) :-rev1(T, C - [H|A]).

reverse2(List1,R) :- rev2(List1, R, []).
rev2([], A, A).
rev2([H|T], C, A) :- rev2(T, C, [H|A]).

Поскольку оба делают одно и то же, какая польза от использования списков различий?

Answer 1

В приведенном примере reverse1 не использует истинный список различий, но просто другое представление reverse2, Они оба используют одни и те же переменные одинаковым образом. reverse использует - функтор, чтобы прикрепить их и reverse2 поддерживает их как отдельные параметры. Но это все, что отличается между двумя. Алгоритмы поведения одинаковы.

Реальный список отличий - это структура списка с "дырой", например X-T в котором T не создается (возможно, до более позднего момента времени), и X содержит T (например, [a,b,c|T]-T). - В этом случае functor связывает "открытую" необъявленную переменную со структурой, которая ее содержит.

Популярным и простым примером является реализация append используя списки различий. Традиционная рекурсивная реализация append может выглядеть так:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

Достаточно просто, а время выполнения пропорционально длине первого списка.

Используя списки различий, вы можете реализовать append следующее:

append(A-B, B-C, A-C).

Это все, что вам нужно, чтобы добавлять списки, используя списки различий. Никакой рекурсии или чего-то еще. Время выполнения O(1) не зависит от длины списка. Вот пример выполнения:

append([1,2,3|T]-T, [4,5,6|W]-W, DL).

Урожайность:

DL = [1,2,3,4,5,6|W]-W
T = [4,5,6|W]

Вы можете получить конкретный ответ, "заполнив" отверстие пустым списком в последнем параметре:

append([1,2,3|T]-T, [4,5,6|W]-W, L-[]).

Ты получаешь:

L = [1,2,3,4,5,6]
T = [4,5,6]
W = []

Answer 2

То, что у вас есть в вашем примере, не является списком различий. Сравните http://en.wikibooks.org/wiki/Prolog/Difference_Lists. Списки различий используют хитрость сохранения хвоста как известной переменной, которую можно изменить напрямую. Следовательно, это позволяет постоянному времени добавляться в списки. Но это не то, что вы делаете в своем примере.

Глядя на ваш пример, rev1 на самом деле просто использует - в качестве разделителя, как если бы это была запятая. Я бы сказал, что единственная разница в том, что в rev2интерпретатор пролога может индексировать правила таким образом, чтобы повысить производительность. Не уверен, что в этом случае это будет иметь какое-либо значение, хотя. Эстетически говоря, второе решение кажется мне намного чище.

Answer 3

Я никогда не видел, чтобы списки различий использовались вне контекста, а основным контекстом является реализация DCG.

Вот реверс на основе DCG (ну, я написал сам, но вы можете найти его также на странице, на которую ссылается Кристиан).

reverse3(L,R) :- phrase(rev3(L),R).
rev3([]) --> [].
rev3([H|T]) --> rev3(T),[H].

Перечисление показывает, что ваш reverse2 практически идентичен:

?- listing(rev3).
stackru:rev3([], A, A).
stackru:rev3([D|A], B, E) :-
    rev3(A, B, C),
    C=[D|E].

Все эти определения имеют общую проблему: они зацикливаются при использовании в режиме "назад", при возврате после первого решения:

?- reverse1(R,[a,b,c]).
R = [c, b, a] ; (^C here)
Action (h for help) ? abort
% Execution Aborted

Интересно взглянуть на правильную, эффективную реализацию библиотеки:

?- listing(reverse).
lists:reverse(A, B) :-
    reverse(A, [], B, B).

lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
    reverse(A, [B|C], D, E).

Нет разницы списки здесь!

Тогда, по поводу вашего вопроса, я бы сказал, что единственная выгода от списков различий - лучшее понимание Пролога...