Prolog Differenzliste

Question

die folgenden Programme Betrachten wir ein Differenzlisten verwendet wird, und der andere nicht:

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

Da beide das gleiche tun, was ist der Nutzen der Differenzlisten mit?

Answer 1

In dem angegebenen Beispiel verwendet reverse1 keine echte Differenzliste, sondern nur eine andere Darstellung von reverse2. Sie verwenden beide dieselben Variablen auf die gleiche Weise. reverse verwendet einen - Funktor, um sie anzuhängen, und reverse2 verwaltet sie als separate Parameter. Aber das ist alles zwischen den beiden. Die Verhaltensweisen des Algorithmus sind gleich.

eine echte Unterschied Liste ist eine Listenstruktur mit einem „Loch“ in der es, wie X-T in denen T nicht instanziiert wird (bis zu einem späteren Zeitpunkt vielleicht) und X enthält T (z.B., [a,b,c|T]-T). Der Funktor - verknüpft die "exponierte" nicht instantiierte Variable mit der Struktur, die sie enthält.

Ein beliebtes und einfaches Beispiel ist eine Implementierung von append unter Verwendung von Differenzlisten. Eine traditionelle, rekursive Implementierung von append könnte wie folgt aussehen:

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

Einfach genug, und die Ausführungszeit ist auf die Länge der ersten Liste proportional.

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

Das alles, was Sie Listen, Listen mit Unterschied anhängen müssen ist:

Differenzlisten verwenden, können Sie eine append wie folgt implementieren. Keine Rekursion oder irgendetwas anderes. Ausführungszeit ist O(1) unabhängig von der Länge der Liste. Hier ist ein Beispiel der Ausführung:

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

Ausbeuten:

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

Sie auf die konkrete Antwort bekommen kann durch das Loch mit einer leeren Liste im letzten Parameter "Füllung":

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

Sie erhalten:

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

Answer 2

Was Sie dort in Ihrem Beispiel haben, ist nicht eine Differenzliste. Vergleichen Sie http://en.wikibooks.org/wiki/Prolog/Difference_Lists. Unterschiedslisten verwenden den Trick, den Schwanz als eine Variable zu behalten, die bekannt ist und direkt geändert werden kann. Daher erlaubt es eine konstante Zeit an Listen anzuhängen. Aber das ist nicht das, was Sie in Ihrem Beispiel tun.

Wenn Sie Ihr Beispiel betrachten, verwendet rev1 wirklich nur - als Trennzeichen, als wäre es ein Komma. Ich würde annehmen, dass der einzige Unterschied dann darin besteht, dass der Prolog-Interpreter in rev2 die Möglichkeit hat, die Regeln so zu indizieren, dass die Leistung verbessert wird. Nicht sicher, ob es in diesem Fall einen Unterschied machen würde. Ästhetisch scheint mir auch die zweite Lösung viel sauberer zu sein.

Answer 3

Ich habe nie Unterschiedslisten 'außerhalb des Kontextes' gesehen, und der Hauptkontext ist DCGs Implementierung.

Hier ist ein DCG-basiertes Reverse (na ja, ich habe es selbst geschrieben, aber Sie finden es auch auf der von Christian verlinkten Seite).

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

Listing es beweist, wie Sie Ihren reverse2 fast identisch ist:

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

All diese Definitionen teilen ein Problem: sie Schleifen, wenn in 'rückwärts' Modus verwendet wird, auf Rückzieher nach der ersten Lösung:

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

Es ist interessant, dann auf der richtigen, effizient, Bibliothek Umsetzung aussehen:

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

Kein Unterschied listet hier auf!

Dann über Ihre Frage, würde ich sagen, dass der einzige Vorteil von Differenzlisten ist ein besseres Verständnis des Prologs ...