разница список Пролог

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). Функтор - в этом связывает «разоблаченную» неизведанную переменную со структурой, которая ее содержит.

Популярным и простым примером является реализация 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). 
stackoverflow:rev3([], A, A). 
stackoverflow: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). 

Здесь нет списков различий!

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