Bitte führen Sie mich durch dieses "Erlang Programming" rekursive Beispiel

Question

Ab Seite 90 von Erlang Programmierung von Cesarini und Thomson gibt es ein Beispiel, das keine detaillierte Diskussion hat. Ich bin der Neuling für funktionales Programmieren und rekursives Denken, daher bin ich nicht vertraut darin, Probleme auf diese Weise zu lösen.

„Zum Beispiel geht die folgende Funktion zwei Listen (von gleicher Länge) durch ihre Werte Verschachtelung:“

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 
mergeL([],[],Zs) -> Zs. 

mergeR(Xs,[Y|Ys],Zs) -> mergeL(Xs,Ys,[Y|Zs]); 
mergeR([],[],Zs) -> Zs. 

Wie funktionierts? Vielen Dank!

Answer 1

Diese Funktion zuerst aufgerufen wird:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

Die leere Liste [], um Mergel übergeben wird, der Speicher - das ist, wo die Antwort kommen soll. Beachten Sie, dass die erste Funktion mergeL aufruft - die linke Zusammenführung.

Lassen Sie uns so tun, als diese Funktion als so genannt wird:

merge([1, 2, 3], [a, b, c]) 

zwei Listen der gleichen Länge. Diese erste Funktion ruft dann mergeL auf:

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 
mergeL([],[],Zs) -> Zs. 

Es gibt 2 Klauseln in der linken Zusammenführung. Der Aufruf von mergeL mit Argumenten stimmt mit diesen Klauseln in umgekehrter Reihenfolge überein.

Die zweite dieser Klauseln hat drei Parameter - die ersten beiden sind leere Listen []. Wenn MergeL das erste Mal aufgerufen wird, sind diese zwei Listen nicht leer, sie sind die Listen Xs und Ys, so dass die erste Klausel übereinstimmt.

Lets brechen die Spiele. Dies ist der Aufruf von Mergel:

Mergel ([1, 2, 3], [a, b, c], [])

und es passt die erste Klausel in der folgenden Art und Weise:

X = 1 
Xs = [2, 3] 
Ys = [a, b, c] 
Zs = [] 

Dies ist wegen der besonderen Form der Liste:

[X | Xs] 

das bedeutet Spiel X auf den Kopf der Liste (ein Einzelstück) und machen Xs der Schwanz der Liste (eine Liste).

Wir bauen dann den neuen Funktionsaufruf auf. Wir können den Wert X am Anfang der Liste Zs auf die gleiche Art und Weise wie wir Muster angepasst haben, so dass wir den ersten mergeR-Aufruf erhalten:

mergeR ([2, 3], [a, b, c], [ 1])

Das letzte Argument ist eine Ein-Punkt-Liste, die durch Hinzufügen eines Elements am Anfang einer leeren Liste verursacht wird.

Dies zieht sich bis zum Ende durch.

Eigentlich ist die Endklausel von mergeL redundant. Per Definition wird diese Funktion im letzten Satz von mergeR erschöpfen (aber ich werde das als Übung für den Leser belassen).

Answer 2

Schritt durch

merge([1,2],[3,4]) 
reverse(mergeL([1,2],[3,4],[])) 
reverse(mergeR([2],[3,4],[1])) 
reverse(mergeL([2],[4],[3,1])) 
reverse(mergeR([], [4], [2,3,1])) 
reverse(mergeL([], [], [4,2,3,1])) 
reverse([4,2,3,1]) 
[1,3,2,4] 

Es ist immer gut, diese Funktionen mit der Hand auf ein Stück Papier mit einem kleinen Eingang zu arbeiten, wo Sie versuchen, es Figur. Sie werden schnell sehen, wie es funktioniert.

Answer 3

In diesem Beispiel werden einige Zustände definiert, die die Rekursion durchlaufen soll. Es gibt 3 'Funktionen', die definiert sind: merge, mergeL und mergeR.

Die Listen zum Zusammenführen sind Xs und Ys, während die Zs das Ergebnis der Zusammenführung sind.

Die Zusammenführung wird mit dem Aufruf von 'merge' beginnen und zwei Listen liefern. Der erste Schritt besteht darin, mergeL mit den beiden zusammenzuführenden Listen und einer leeren Ergebnismenge aufzurufen.

[X | Xs] nimmt das erste Element der Liste (sehr ähnlich wie array_shift). Dieses Element wird dem Kopf des Resultsets hinzugefügt ([X | Zs] tut dies). Diese Ergebnismenge (die jetzt ein Element enthält) wird dann an den nächsten Aufruf übergeben, mergeR. mergeR macht dasselbe, nur ein Element aus der zweiten Liste. Dieses Verhalten wird fortgesetzt, solange die Listen, die an mergeL oder mergeR übergeben wurden, nicht leer sind.

Wenn mergeL oder mergeR mit zwei leeren Listen ([]) und einem Resultset (Zs) aufgerufen wird, wird das Resultset zurückgegeben (und kein weiterer Lauf ausgeführt, wodurch die Rekursion gestoppt wird).

Zusammenfassung:

Die Start der Rekursion ist die erste Zeile, die 'merge' definiert. Dieser Start setzt das Ganze in Bewegung, indem er die erste mergeL aufruft.

Die Körper der Rekursion ist Zeilen 2 und 4, die das Verhalten definieren oder mergeL und mergeR, die beide einander aufrufen.

Der Stop der Rekursion wird durch die Zeilen 3 und 5 definiert, die dem Ganzen im Grunde sagen, was zu tun ist, wenn sich keine Elemente mehr im Array befinden.

Hoffe, das hilft!

Answer 4

ich für diese Funktionen suchen immer, die die Rekursion erste, in diesem Fall endet:

mergeL([],[],Zs) -> Zs. 

und

mergeR([],[],Zs) -> Zs. 

beide von denen im Grunde die „Verschmelzung“, wenn die ersten beiden beenden wird Parameter sind leere Listen.

Also dann schaue ich auf den ersten Aufruf der Funktion:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])). 

die Rückseite für eine zweite Ignorieren, werden Sie sehen, dass der letzte Parameter eine leere Liste ist.Also würde ich erwarten, dass die verschiedenen mergeL- und mergeR-Funktionen die Elemente dieses Arrays in den letzten Parameter verschieben - und wenn sie alle verschoben sind, wird die Funktion im Grunde beendet (obwohl schließlich die umgekehrte Funktion aufgerufen wird)

Und das ist genau das, was die übrigen Funktionen haben:

mergeL([X|Xs],Ys,Zs) -> mergeR(Xs,Ys,[X|Zs]); 

das erste Element X nimmt und sie in den Z-Array setzt und

mergeR(Xs,[Y|Ys],Zs) -> mergeL(Xs,Ys,[Y|Zs]); 

das erste Element von Y nimmt und sie in die Z-Array legt . Der Aufruf des mergeR von mergeL und umgekehrt führt den Verschachtelungsteil durch.

Was ist interessant zu sehen (und einfach zu beheben) ist, dass die Arrays X und Y müssen die gleiche Länge haben oder Sie werden am Ende mergeL oder mergeR mit einem leeren Array in X oder Y aufrufen - und das gewonnen ' t Übereinstimmung mit [X | Xs] oder [Y | Ys].

Und der Grund für das Gegenteil ist einfach um den relativen Wirkungsgrad von [X | Zs] gegen [Zs | X]. Ersteres ist viel effizienter.