Verständnis der Spaltung in Swi-Prolog

Question

Ich habe diesen Code zum Aufspalten der Eingangsliste in seine Hälften. Es scheint in Ordnung zu sein.

halve(List,A,B) :- halve(List,List,A,B), !. 
halve(B,[],[],B). 
halve(B,[_],[],B). 
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B). 

Ok, also habe ich versucht, es zu dekodieren. Der Anfang ist klar:

"Halve nahm Liste und 2 Logikvariablen" ist dies:

halve(List,A,B) 

(1) Dann kontinuierlicher dieser Teil:

:- halve(List,List,A,B). 

Und das bedeutet, dass ich bin Erstellen von zwei neuen Listen (Liste, Liste) von der ersten oder was? Was exacly stellt ": -" dar? Ich denke die neuen Listen = Hälften werden das A und B sein, oder?

(2) Zweitens, bitte, ich verstehe nicht ganz, diese beiden Linien erhalten:

halve(B,[],[],B). 
halve(B,[_],[],B). 

Vielleicht erklären Sie könnte es auf einige Beispiele, bitte?

(3) Nun, ich hoffe, nach der Erklärung von (1) und (2), werde ich den letzten Teil von mir bekommen ...

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B). 

Danke sehr, sehr viel für die Unterstützung mich.

---

Ok, unser erstes Problem hat bereits seine Lösung. Lange Rede kurzer Sinn, es funktioniert wie folgt aus:

halve([1,2,3,4,5],[1,2],[3,4,5]). 
->true 

Wenn Sie bemerken, dass es die Liste in seiner Hälften teilt, aber wenn die Liste eine ungerade Anzahl der Elemente hat, die zweite Hälfte ist die größere.

Jetzt was ich erhalten möchte, ist der erste größere zu haben.

diese So etwa ich denke:

ich dies erreichen werde:

Halves_div([1,2,3],A,B). 
A=[1,2], 
B=[3]. 

Lassen Sie uns meine Eingabe sagen Liste: [1,2,3]. Also werde ich mit dem Aufspalten der Listen Kopf und Schwanz beginnen: [H|T] und dann werde ich die H mit der neuen leeren Liste zusammenführen - meine 1. Hälfte (A). Danach habe ich A = [1], B = [] und Input = [2,3].

für das Zusammenführen ich habe:

merge([],List,List). 
merge([H|T],List,[H|New]) :- merge(T,List,New). 

Und noch etwas - ich brauche die erste Hälfte bereits zu prüfen, ob von> = 2. Hälfte, nicht wahr?

Also das ist meine Idee und das Einzige, was ich gerne hätte, wenn du mir hilfst, ist es in Prolog zu schreiben. Ich bin irgendwie verwirrt, wie man es zusammensetzt.

Danke!

---

Es scheint, dass meine Idee der Lösung zu kompliziert ist und ich etwas besseres gefunden habe!

Answer 1

zu starten, sieht eine Prolog-Klausel wie folgt aus:

Head :- Body 

Sie können das als "Head wenn Body" lesen, oder "Body impliziert Head".

Beachten Sie, dass man manchmal einfach

Head 

haben, das ist, weil Kopf immer true ist. Statt eine Klausel Head aufzurufen, nennen wir es in diesem Fall eher eine Tatsache.

Also hier haben wir:

halve(List,A,B) :- halve(List,List,A,B). 

Das bedeutet, dass halve(List, A, B) wahr ist, wenn halve(List, List, A, B) wahr ist. Konkret ist es nur ein Weg, die Arbeit von halve/3 an halve/4 zu delegieren, ein sogenanntes Worker-Prädikat.

Warum brauchen wir ein Worker-Prädikat? Nun, weil wir hier eine andere Variable verwenden möchten, um unsere A und B Begriffe zu berechnen. Aber wir konnten das nicht mit halve/3 tun, weil die 3-Punkte-Punkte von halve/3 wurden bereits von der Eingangsliste, List, die erste Hälfte des Ergebnisses, A und die zweite Hälfte des Ergebnisses, B.

Über die List, List Sache, es ist nur eine Möglichkeit zu sagen, dass wir halve/4 mit dem gleichen ersten und zweiten Argument aufrufen, wie Sie in jeder Programmiersprache würden.

Dann beginnt das interessante Zeug. Prolog wird versuchen, zu beweisen, dass halve/4 für einige gegebene Argumente wahr ist. Nehmen wir an, die Ausführung zu veranschaulichen, dass wir halve/3 diese Art und Weise genannt:

?- halve([1, 2], A, B). 

Dann, wenn Sie folgten dem, was ich über früher gesprochen wird Prolog nun versuchen zu beweisen, dass halve/3 durch den Nachweis, wahr ist, dass halve/4 mit folgenden Aussagen wahr ist Argumente: halve([1, 2], [1, 2], A, B)..

Um dies zu tun, hat Prolog 3 Möglichkeiten. Die erste Wahl ist die folgende Klausel:

Offensichtlich wird das nicht funktionieren. Denn wenn Prolog versucht, das zweite Argument des Aufrufers "in" das zweite Argument des Angerufenen durch Vereinheitlichung anzupassen, wird es fehlschlagen. Weil [1, 2] nicht mit [] vereinheitlicht werden kann.

nur noch zwei Möglichkeiten, die nächste ist:

halve(B,[_],[],B). 

Das Gleiche gilt hier, Prolog [1, 2] nicht vereinigen können und [_] weil _ nur eine Variable (siehe my post über die anonyme Variable _ wenn Sie Probleme haben mit es).

So ist die einzige Möglichkeit, Prolog, eine Lösung für das Problem finden Ihnen präsentiert es die letzte Klausel ist, das heißt:

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B). 

Hier finden Prolog eine Art und Weise, was zu vereinen, wollen wir sehen, welche Art und Weise :

• müssen wir [1, 2] mit [H|T] vereinen. Das bedeutet, dass H = 1. und T = [2].
• wir [1, 2] mit [_,_|T2] vereinheitlichen müssen. das heißt, dass
• jetzt beginnen wir, unsere Ergebnisse mit der nächsten Vereinheitlichung zu erstellen, dh A = [H|A'] (ich grundierte die zweite A, weil Variablen lokal begrenzt sind und sie nicht die gleichen sind). Hier sagen wir, wenn wir unser Ergebnis aus dem Rumpf der Klausel berechnen lassen, fügen wir H hinzu. Hier H ist 1 so wissen wir bereits, dass das erste Element von A1 sein wird.

Ok ok, Vereinigung gelungen, super! Wir können mit dem Text der Klausel fortfahren. Er fordert nur halve/4 in einer rekursiven Weise mit diesen Werten (berechnet oben):

halve([2], [], A, B). 

Und hier beginnen wir wieder von vorn. Obwohl diesmal die Dinge schnell sein, da die erste Wahl hat Prolog eine gute Passform sein wird:

halve(B,[],[],B). 

kann mit diesen Werten zu

halve([2], [], A, B). 

vereint werden: A = [] und B = [2].

Also das ist ein guter Schritt, wir haben jetzt den "Basisfall" der Rekursion erreicht. Wir müssen jetzt unser Ergebnis von unten nach oben aufbauen. Erinnern Sie sich, als wir unser Prädikat halve/4 ein paar Schritte rekursiv aufgerufen haben? Wir hatten bereits gesagt, dass das erste Element von A1 wäre. Jetzt wissen wir, dass der Schwanz [] ist, so dass wir das A = [1] angeben können. Wir hatten nichts besonderes über B gesagt, so dass B = [2] als Ergebnis unberührt bleibt.

Nun, da ich die Ausführung detailliert habe, fragen Sie sich vielleicht, warum das funktioniert? Nun, wenn Sie darauf achten, werden Sie feststellen, dass das zweite Argument von halve/4 zweimal so schnell durchlaufen wird wie das erste. [H|T] vs [_, _|T2]. Das bedeutet, dass wenn wir mit unserem zweiten Argument das Ende der Liste erreichen, das erste immer noch in der Mitte unserer Liste steht. Auf diese Weise können wir das Ding in zwei Teile teilen.

Ich hoffe, ich habe dir geholfen, einige der subtilen Dinge bei der Arbeit hier zu fangen.

Answer 2

halve(List,A,B) Kopien erste Halb List zu A und vereint zweite Hälfte mit B

, die wahr sein, wenn Länge unserer Liste auch sein: halve(B,[],[],B).

, die wahr sein, wenn Länge aus Liste ungerade: halve(B,[_],[],B).

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B). 

Hier haben wir 2 setzen nennen wir sie ‚Zeiger‘ in jedem Schritt kopieren wir ein Element f Vom Anfang unserer Liste zu A, weil wir die erste Hälfte bekommen wollen.
Da in jedem Schritt entfernen wir 2 Elemente aus unserer Liste [_,_|T2] Prädikat wird aufhören, wenn Liste nur ein Element links oder leer hat, dann wird es den Rest unserer Liste mit B vereinheitlichen. Wenn Sie schräges nutzen verstehen trace/0

Answer 3

Diese Version könnte als nützlich erweisen ...

split_in_half(Xs, Ys, Zs) :- length(Xs, Len), 
Half is Len // 2, % // denotes integer division, rounding down 
split_at(Xs, Half, Ys, Zs). 

split_at(Xs, N, Ys, Zs) :- length(Ys, N), append(Ys, Zs, Xs).