Understanding Difference Listen

Question

Ich versuche, Unterschiedslisten in Prolog zu verstehen, aber ich habe Mühe, einen richtig zu implementieren, jedes Mal, wenn ich es versuche, bekomme ich eine Liste von Listen, aber das ist nicht das, was ich will. Ich versuche ein Append-Prädikat zu implementieren, habe aber bisher wenig Glück. Wenige Versuche, die alle nicht funktionieren.

app(X, Y, Z) :- Z = [X|Y]. 

?- app([a,b,c], [z], Z). 
Z = [[a,b,c],z]. 

ODER

app(X, Y, Z) :- Z = [X|Hole], Hole = Y. 

gleichen Ergebnisse wie die erste, (sie scheinen im Grunde das gleiche zu sein). Ich habe ein Beispiel in einem Buch, das funktioniert (obwohl es kein Prädikat ist), und ich verstehe den Unterschied nicht. X wird in die richtige Antwort [a,b,c,z] instanziiert, wie ist das viel anders als mein zweites Beispiel?

X = [a,b,c|Y], Y = [z]. 

Was fehlt mir? Vielen Dank.

Answer 1

Der Schlüssel zum Verständnis Unterschied auflistet, zu verstehen, was sie sind auf die Ebene des verschachtelten zusammengesetzten Begriffs, der Listen darstellt. Normalerweise sehen wir eine Liste wie folgt:

[a, b, c] 

Dies ist jetzt eine Liste mit drei Elementen. Die genau gleiche verschachtelte Term des Punkt als Liste Funktors verwenden, ./2, und das Atom [] als leere Liste wäre:

.(a, .(b, .(c, []))) 

Es ist wichtig hier, dass die Liste Funktors eine Verbindung Begriff mit zwei Argumenten ist: das Element und der Rest der Liste. Die leere Liste ist ein Atom, das informell als zusammengesetzter Ausdruck mit der 0, also ohne Argumente, betrachtet werden kann.

Nun, dies ist eine Liste mit drei Elementen, bei denen das letzte Element eine freie Variable ist:

[a, b, Last] 

, die die gleiche ist wie:

.(a, .(b, .(Last, []))) 

Diese auf der anderen Seite ist eine Liste mit zwei Elementen und einer freien Variable, wie der Rest der Liste oder die tail:

[a, b|Tail] 

, die gleich wie:

.(a, .(b, Tail)) 

Sie sehen, wie .(a, .(b, .(Last, []))) nicht das gleiche wie .(a, .(b, Tail)) ist?

Der Versuch, dies auf der obersten Ebene (Ich bin mit SWI-Prolog 7, die die --traditional Flagge muss die ./2 wie die Liste Begriff behandeln):

$ swipl --traditional 
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.26) 
Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam 
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, 
and you are welcome to redistribute it under certain conditions. 
Please visit http://www.swi-prolog.org for details. 

For help, use ?- help(Topic). or ?- apropos(Word). 

?- [a, b, Last] = [a, b|Tail]. 
Tail = [Last]. 

?- .(a, .(b, .(Last, []))) = .(a, .(b, Tail)). 
Tail = [Last]. 

nun eine „Differenzliste“ ist eine Liste wie diese: [a, b|Tail], identisch mit .(a, .(b, Tail)), wo Sie die Variable Tail halten, die den Schwanz hält. Dies ist nicht eine ordnungsgemäße Liste, bis die Tail in eine ordnungsgemäße Liste instanziiert wurde!

?- L = [a, b|Tail], is_list(L). 
false. 

?- L = [a, b|Tail], Tail = [c,d,e], is_list(L). 
L = [a, b, c, d, e], 
Tail = [c, d, e]. 

Sie können an den vorhergehenden Abfragen aussehen zu verstehen, was genau Tail = [c, d, e] in diesem Zusammenhang der Fall ist.

In einem Prädikat, das eine Differenzliste verwendet, müssen Sie zwei Argumente, oder manchmal, ein Paar, die unvollständige Liste zu halten und mit dem Schwanz, wie folgt aus:

% using two arguments 
foo([a,b|Tail], Tail). 
% using a pair 
foo([a,b|Tail]-Tail). 

Die erste foo/2 hat zwei Argumente, die zweite hat eine, die ein "Paar" ist. Moderner Prolog-Code scheint zwei Argumente gegenüber einem Paar vorzuziehen, aber Sie sehen das Paar häufig in Lehrbüchern und Tutorien.

Um Ihre Anfügen oder app/3: Wenn Sie mit Differenzlisten arbeiten, können Sie Notwendigkeit das zusätzliche Argument (oder ein Paar), so dass Sie das Ende der Liste zugreifen können Sie es zu tun. Wenn Sie nur das Ende der Liste haben, die an der Front sein wird, können Sie immer noch ein Append schreiben, das nur drei Argumente hat, weil es nur das Endstück der ersten Liste mit der zweiten Liste vereinheitlichen muss:

% app(List1, Tail1, List2) 
app(List1, Tail1, List2) :- Tail1 = List2. 

oder direkt im Kopf zu vereinen:

app(_L1, L2, L2). 

?- L1 = [a,b|Tail], app(L1, Tail, [c]). 
L1 = [a, b, c], 
Tail = [c]. 

Dies ist genau die gleiche Code wie in der Verbindung von @Wouter zur Verfügung gestellt.

Wenn Sie die Schwänze der beiden Listen hatten, ersetzen Sie das Ende der ersten Liste durch die zweite Liste und behalten das Ende der zweiten Liste.

app(List1, Tail1, List2, Tail2) :- Tail1 = List2. 

Wiederum könnten Sie die Vereinigung im Kopf gemacht haben.

EDIT:

Sie können nicht ein „Loch“ machen, sobald die Liste bereits vollständig instanziiert. Wie würden Sie von diesem .(a, .(b, .(c, []))) zu diesem gehen: .(a, .(b, .(c, Tail)))? Sie können nicht, außer zum Durchlaufen der Liste Kopf zu Ende und Ersetzen der [] durch Tail, aber das ist genau das, was die gewöhnlichen append/3 tut.Versuchen:

?- L = [a,b,c,d], append(L, Back, Front), Back = [x,y,z]. 
L = [a, b, c, d], 
Back = [x, y, z], 
Front = [a, b, c, d, x, y, z]. 

Oder, wenn Sie ein diflist_append/3 haben wie folgt definiert:

diflist_append(Front, Back, Back). 

, die die Back der Liste mit dem dritten Argument vereint:

?- L = [a,b,c,d], append(L, Back, Front), diflist_append(Front, Back, [x,y,z]). 
L = [a, b, c, d], 
Back = [x, y, z], 
Front = [a, b, c, d, x, y, z]. 

Wie bei Ihrem Beispiel X = [a,b,c], Y = [X|Z], Z = [z] , das ist das gleiche wie:

X = .(a, .(b, .(c, []))), 
Y = .(X, Z), % Y = .(.(a, .(b, .(c, []))), Z) 
Z = [z] % Y = .(.(a, .(b, .(c, []))), .(z, [])) 

So sehen Sie es jetzt?

Answer 2

Paul Brna has explained this very well. Er nutzt Variablen OpenList# und Hole# in seiner Differenz-Liste Version von append:

difference_append(OpenList1-Hole1, Hole1-Hole2, OpenList1-Hole2). 

Beispiel:

?- difference_append([a,b,c|H1]-H1, [d,e,f|H2]-H2, L). 
H1 = [d, e, f|H2], 
L = [a, b, c, d, e, f|H2]-H2.