Verständnis Prolog "anhängen" rekursive Definition

Question

Ich lese Programming in Prolog: Using the ISO Standard, aber ich habe Probleme zu verstehen, die rekursive Definition von append durch das Buch vorgestellt:

append([], List, List). 
append([X|List1], List2, [X|Result]) :- append(List1, List2, Result). 

Zum Beispiel:

?- append([a, b, c], [3, 2, 1], Result). 
Result = [a, b, c, 3, 2, 1] 

Soweit ich weiß, besagt die Definition, dass die resultierende Liste den Kopf der ersten Liste als Kopf enthalten sollte, so dass die resultierende Liste anfänglich [ a ] ist. Dann führen wir rekursiv append() am Ende des ersten und dritten Arguments und lassen das zweite Argument so, wie es ist. Das dritte Argument (also [ a ]) sollte den Kopf des neuen ersten Arguments als Kopf enthalten, also das Ergebnis Liste ist [ b, a ] (was rückwärts ist, so klar, ich folge nicht richtig). Irgendwann ist die erste Liste [] und die resultierende Anordnung ist [ c, b, a ], so treffen wir den Basisfall:

append([], List, List). 

So append([], [3, 2, 1], [ c, b, a ])., die keinen Sinn macht. Ich befolge auch nicht, wie der Inhalt der zweiten Liste berücksichtigt wird, wenn in der gesamten Definition keine Manipulation daran vorgenommen wird.

Answer 1

[...] die Definition besagt, dass die resultierende Liste den Kopf der ersten Liste als Kopf enthalten soll, also ist die resultierende Liste anfänglich [a].

Wie Sie erwähnt haben, sagt die Definition, dass der Kopf der resultierenden Liste a ist, ist es nicht, dass die gesamte Liste [a] ist sagt. Außerdem wird diese Liste nicht als Argument für den rekursiven Aufruf übergeben. Die resultierende Liste wird als definiert. Wir wissen noch nichts über Result, aber wir "übergeben" es als drittes Argument an den rekursiven Aufruf. Insgesamt bedeutet dies, dass die Ausgabe gefolgt von der Ausgabe des rekursiven Aufrufs ist.

Die Schritte für b und c sind genau die gleichen, so können Sie den Stapel wie folgt vorstellen:

R = [a|R1] 
R1 = [b|R2] 
R2 = [c|R3] 

Oder abgeflacht: [a|[b|[c|R3]]]. Beachten Sie jetzt, die Reihenfolge ist in der Tat richtig?

Jetzt ist die einzige Frage, was ist R3? Nun, das erste Argument an dieser Stelle ist die leere Liste, also haben wir den Basisfall erreicht. Dies sagt einfach, dass "wenn die erste Liste leer ist, das Ergebnis die zweite Liste ist". so R3 = [3, 2, 1]. Danach wickelt sich der Stapel ab und gibt Ihnen die angehängte Liste als Ausgabe.

Answer 2

Aus meiner Sicht eine solche operativen Lesen werden Sie wegführen vom wahren Vorteil der Logik-Programmierung, da sie es äußerst verlockend machen in Bezug auf die „Eingänge“ und „Ausgänge“ zu denken, wie in funktionale Programmierung. Solch eine prozedurale oder sogar funktionale Lesung ist zu begrenzt in dem es nicht die volle Allgemeinheit der Beziehung gerecht wird.

Zusätzlich, wie Sie auch schon bemerken, ist das Lesen dieser Definition operational extrem hart. Der genaue Anrufverlauf von Prolog ist komplex und im Allgemeinen für Anfänger und Experten zu schwer zu verstehen.

---

Meiner Meinung nach ist ein guter Weg, um Ihre Definition zu denken ist, die beiden Klauseln zu betrachten und verstehen, ihre Bedeutung, uns zu einem deklarativen Lesen führt.

Zunächst betrachten:

append([], List, List). 

Dies gibt einfach was hält, und einfach richtig gesehen werden kann, um sein: Wenn die erste Liste leer ist, die zweite Liste ist die   gleichen wie die dritte Liste.

Hinweis des Wortlaut: Wir sind noch nicht eine resultierende Liste erwähnen, da alle Argumente angegeben werden können oder nicht.

Als nächstes betrachten die zweite Klausel:

append([X|List1], List2, [X|Result]) :- append(List1, List2, Result). 

Lesen Sie die :- als das, was es ist, nämlich & ;. leftarrow Also, das sagt:

Wennappend(List1, List2, Result) hält, dannappend([X|List1], List2, [X|Result])auch hält.

Auch dies kann leicht richtig zu sehen sein, und ermöglicht eine Lektüre, die in alle   Richtungen anwendbar ist.

In diesem Licht kann man prüfen, ob Result ein guter Name für das dritte Argument ist, und ferner, wie @WillNess richtig weist darauf hin, ob auch append/3 insgesamt ein guter Name ist diese Beziehung zu beschreiben.