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 mit 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.
%Vor%ODER
%Vor% Gleiche Ergebnisse wie die erste (sie scheinen im Grunde die gleichen 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, was ist das anderes als mein zweites Beispiel?
Was vermisse ich? Danke.
Der Schlüssel zum Verständnis von Differenzlisten besteht darin, zu verstehen, was sie auf der Ebene des geschachtelten zusammengesetzten Terms sind, der Listen darstellt. Normalerweise sehen wir eine Liste wie diese:
%Vor% Dies ist jetzt eine Liste mit drei Elementen. Der genau gleiche verschachtelte Ausdruck, der den Punkt als Listen-Funktor, ./2 , und das Atom [] als leere Liste verwendet, wäre:
Es ist wichtig, dass der Listenfunktor ein zusammengesetzter Term mit zwei Argumenten ist: dem Element und dem Rest der Liste. Die leere Liste ist ein Atom, das informell als ein zusammengesetzter Ausdruck mit der 0, also ohne Argumente, betrachtet werden kann.
Nun ist dies eine Liste mit drei Elementen, wobei das letzte Element eine freie Variable ist:
%Vor%ist das gleiche wie:
%Vor%Dies ist andererseits eine Liste mit zwei Elementen und einer freien Variable als Rest der Liste oder tail :
%Vor%ist das gleiche wie:
%Vor% Sehen Sie, wie .(a, .(b, .(Last, []))) nicht mit .(a, .(b, Tail)) identisch ist?
Ich versuche dies von der obersten Ebene aus (ich verwende SWI-Prolog 7, das das --traditional -Flag benötigt, um ./2 als Listenbegriff zu behandeln):
Nun ist eine "Differenzenliste" eine Liste wie diese: [a, b|Tail] , identisch mit .(a, .(b, Tail)) , wo Sie die Variable Tail behalten, die den Tail enthält. Dies ist nicht eine richtige Liste, bis das Tail in eine richtige Liste instanziiert wurde!
Sie können sich die vorherigen Abfragen ansehen, um zu verstehen, was genau Tail = [c, d, e] in dieser Konjunktion macht.
In einem Prädikat, das eine Differenzenliste verwendet, benötigen Sie zwei Argumente oder manchmal ein Paar , um an der unvollständigen Liste und ihrem Endstück festzuhalten :
%Vor% Das erste foo/2 hat zwei Argumente, das zweite hat eins, was 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.
An Ihren Anhang oder app/3 : Wenn Sie mit Differenzlisten arbeiten, benötigen Sie das zusätzliche Argument (oder ein Paar), damit Sie auf das Ende der Liste zugreifen können, mit der Sie es zu tun haben mit. Wenn Sie nur den Tail der Liste haben, der an der Front sein wird, können Sie immer noch ein Append schreiben, das nur drei Argumente hat, denn es genügt, den Tail der ersten Liste mit der zweiten Liste zu vereinheitlichen:
oder vereinheitlicht direkt im Kopf:
%Vor%Dies ist der exakt gleiche Code wie in dem von @Wouter bereitgestellten Link.
Wenn Sie die Schwänze beider Listen hatten, ersetzen Sie das Ende der ersten Liste durch die zweite Liste und behalten das Ende der zweiten Liste bei.
%Vor%Auch hier könntest du die Vereinigung im Kopf haben.
BEARBEITEN :
Sie können kein "Loch" machen, wenn die Liste bereits vollständig instanziiert wurde. Wie würdest du von diesem .(a, .(b, .(c, []))) zu diesem gehen: .(a, .(b, .(c, Tail))) ? Sie können nicht, außer zum Durchlaufen der Liste Kopf bis Ende und Ersetzen der [] mit Tail , aber das ist genau das, was die normale append/3 tut. Probieren Sie:
Oder wenn Sie diflist_append/3 als definiert haben:
Was die Back der Liste mit dem dritten Argument zusammenfasst:
Wie für Ihr Beispiel, X = [a,b,c], Y = [X|Z], Z = [z] , ist dies das Gleiche wie:
Siehst du es jetzt?
Paul Brna hat das sehr gut erklärt. Er benutzt die Variablen OpenList# und Hole# in seiner Differenzlistenversion von append:
Anwendungsbeispiel:
%Vor%Tags und Links prolog difference-lists