interprete - swi prolog editor windows

Lista de diferencia Prolog

Question

Considere los siguientes programas, uno que usa listas de diferencias, y el otro no:

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

Como ambos hacen lo mismo, ¿cuál es el beneficio de usar listas de diferencias?

Answer 1

En el ejemplo dado, reverse1 no está usando la lista de diferencia verdadera, pero es solo una representación diferente de reverse2 . Ambos usan las mismas variables de la misma manera. reverse usa un - functor para unirlos y reverse2 mantiene como parámetros separados. Pero eso es todo lo que es diferente entre los dos. Los comportamientos del algoritmo son iguales.

Una lista de diferencias real es una estructura de lista con un "agujero" en ella, como XT en la que T no está instanciado (hasta un punto posterior en el tiempo) y X contiene T ( por ejemplo , [a,b,c|T]-T ). El - functor en esto asocia la variable "expuesta" desinstalada con la estructura que la contiene.

Un ejemplo popular y simple es una implementación de append usando listas de diferencias. Una implementación recursiva tradicional de append podría verse así:

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

Lo suficientemente simple, y el tiempo de ejecución es proporcional a la longitud de la primera lista.

Usando listas de diferencias, puede implementar un append siguiente manera:

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

Eso es todo lo que necesita para agregar listas usando listas de diferencias. Sin recursividad ni nada más. El tiempo de ejecución es O(1) independiente de la longitud de la lista. Aquí hay una ejecución de ejemplo:

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

Rendimientos:

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

Puede obtener la respuesta concreta "llenando" el agujero con una lista vacía en el último parámetro:

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

Usted obtiene:

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

Answer 2

Lo que tienes allí en tu ejemplo no es una lista de diferencias. Compare http://en.wikibooks.org/wiki/Prolog/Difference_Lists . Las listas de diferencias usan el truco de mantener la cola como una variable que se conoce y se puede cambiar directamente. Por lo tanto, permite que el tiempo constante se agregue a las listas. Pero eso no es lo que estás haciendo en tu ejemplo.

En cuanto a su ejemplo, rev1 solo lo usa - como separador, como si fuera una coma. Considero que la única diferencia es que en rev2 , el intérprete de prólogo tiene la oportunidad de indexar las reglas de una manera que mejora el rendimiento. Sin embargo, no estoy seguro de si en este caso hubiera alguna diferencia. Estéticamente hablando, la segunda solución parece mucho más limpia para mí también.

Answer 3

Nunca he visto listas de diferencias que se usen fuera de contexto, y el contexto principal es la implementación de DCG.

Aquí hay un reverso basado en DCG (bueno, lo escribí yo mismo, pero también lo puedes encontrar en la página enlazada por Christian).

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

Listarlo evidencia cómo tu reverse2 es casi idéntico:

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

Todas estas definiciones comparten un problema: se repiten cuando se usan en modo ''hacia atrás'', al retroceder después de la primera solución:

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

Entonces, es interesante observar la implementación adecuada y eficiente de la biblioteca:

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

¡No hay listas de diferencias aquí!

Luego, sobre su pregunta, diría que el único beneficio de las listas de diferencias es una mejor comprensión de Prolog ...