Ich habe eine Frage zum Schreiben von rekursiven Algorithmen in einem funktionalen Stil. Ich werde Scala für mein Beispiel hier verwenden, aber die Frage gilt für jede funktionale Sprache.
Ich führe eine Depth-First-Enumeration eines n -arischen Baums durch, wobei jeder Knoten ein Label und eine variable Anzahl von Children hat. Hier ist eine einfache Implementierung, die die Beschriftungen der Blattknoten druckt.
%Vor%Sagen Sie jetzt, dass ich manchmal in der Lage sein möchte, übergroße Bäume zu analysieren, indem ich eine Ausnahme ausspreche. Ist das in einer funktionalen Sprache möglich? Konkret ist das möglich, ohne einen veränderlichen Zustand zu verwenden? Das hängt davon ab, was Sie mit "Übergröße" meinen. Hier ist eine rein funktionale Version des Algorithmus, der eine Ausnahme auslöst, wenn er versucht, einen Baum mit einer Tiefe von 3 oder größer zu behandeln.
%Vor% Aber was ist, wenn ein Baum überdimensioniert ist, weil er zu breit und nicht zu tief ist? Was genau, wenn ich eine Ausnahme zum n -ten Zeitpunkt auslösen will, wird die Funktion dfs() rekursiv aufgerufen, unabhängig davon, wie tief die Rekursion ist? Der einzige Weg, wie ich das sehen kann, ist ein veränderbarer Zähler, der bei jedem Aufruf erhöht wird. Ich kann nicht sehen, wie es ohne eine veränderbare Variable geht.
Ich bin neu in der funktionalen Programmierung und habe unter der Annahme gearbeitet, dass alles, was Sie mit einem veränderlichen Zustand tun können, ohne sein kann, aber ich sehe die Antwort hier nicht. Das einzige, was ich tun kann, ist eine Version von dfs() zu schreiben, die eine Ansicht über alle Knoten in der Baumstruktur in der Reihenfolge der Tiefe zurückgibt.
Dann könnte ich mein Limit mit dfs(r).take(n) festlegen, aber ich sehe nicht, wie ich diese Funktion schreiben soll. In Python würde ich einfach einen Generator von yield ing Knoten erstellen, wenn ich sie besuche, aber ich sehe nicht, wie man in Scala denselben Effekt erzielt. (Scala entspricht einer Python-ähnlichen yield -Anweisung, die als Parameter übergeben wird, aber ich kann nicht herausfinden, wie ich eine dieser Funktionen schreiben soll, die eine Sequenzansicht erzeugt.)
BEARBEITEN Näher an die Antwort kommen.
Hier ist eine Funktion, die Stream der Knoten in der Reihenfolge der Tiefe zurückgibt.
Das ist fast so. Das einzige Problem ist, dass Stream alle Ergebnisse protokolliert, was eine Verschwendung von Speicher ist. Ich möchte eine verfahrbare Ansicht. Folgendes ist die Idee, aber kompiliert nicht.
Es gibt einen "gefunden TraversableView[Node[T], Traversable[Node[T]]] , erforderlich TraversableView[Node[T], Traversable[_]] Fehler für den Operator ++ . Wenn ich den Rückgabetyp zu TraversableView[Node[T], Traversable[_]] ändere, bekomme ich das gleiche Problem mit den" gefunden "und" erforderlich "-Klauseln Es gibt also eine Zauberformel, die ich noch nicht angezündet habe, aber das ist knapp.
Im Folgenden wird eine verzögerte Tiefensuche über Knoten in einer Struktur implementiert.
%Vor%Dadurch werden die Beschriftungen aller Knoten in der Reihenfolge der Tiefe gedruckt.
%Vor%Dies ist die gleiche Sache, nachdem 3 Knoten besucht wurden.
%Vor% Wenn Sie nur Blattknoten möchten, können Sie filter usw. verwenden.
Beachten Sie, dass die full-Klausel der dfs -Funktion eine explizite asInstanceOf -Cast benötigt. Siehe "Varianzfehler in Scala eingeben, wenn Machen Sie eine FoldLeft über Traversable Ansichten " für eine Diskussion der Scala Typisierung Probleme, die dies erfordern.
Es kann gemacht werden: Sie müssen nur etwas Code schreiben, um die Kinder auf die gewünschte Weise zu durchlaufen (im Gegensatz zu for ).
Genauer gesagt müssen Sie Code schreiben, um eine Liste von Kindern zu durchlaufen und zu überprüfen, ob die "Tiefe" Ihren Schwellenwert überschritten hat. Hier ist ein paar Haskell code (Es tut mir wirklich leid, Scala kann ich nicht fließend sprechen, aber das kann wahrscheinlich leicht transkribiert werden):
In diesem Code habe ich im Grunde die for -Schleife für eine explizite rekursive Version ersetzt. Dadurch kann ich die Rekursion stoppen, wenn die Anzahl der besuchten Knoten bereits zu tief ist (d. H.% Co_de% ist nicht positiv). Wenn ich rekrutiere, um das nächste Kind zu untersuchen, subtrahiere ich die Anzahl der Knoten, die limit des vorherigen Kindes besucht, und setze dies als Grenze für das nächste Kind.
Funktionale Sprachen machen Spaß, aber sie sind ein großer Sprung von der imperativen Programmierung. Es macht dich wirklich aufmerksam auf das Konzept von state , denn all das ist in den Argumenten, wenn du funktionstüchtig bist, quälend explizit.
BEARBEITEN: Erklären Sie dies ein wenig mehr.
Ich konvertierte schließlich von "nur die Blattknoten drucken" (was der ursprüngliche Algorithmus vom OP war) in "alle Knoten drucken". Dadurch konnte ich auf die Anzahl der Knoten zugreifen, die der Teilbereich über die Länge der resultierenden Liste besucht hat. Wenn Sie bei den Blattknoten bleiben möchten, müssen Sie angeben, wie viele Knoten Sie bereits besucht haben:
Nochmal BEARBEITEN Um diese Antwort zu klären, setze ich den gesamten Haskell-Code auf ideone, und ich habe meinen Haskell-Code in Scala transkribiert, damit dies hier als definitive Antwort bleiben kann die Frage:
%Vor%Ausgabe:
%Vor%P.S. Dies ist mein erster Versuch bei Scala, also enthält das obige wahrscheinlich einen schrecklichen nicht-idiomatischen Code. Es tut mir leid.
Tags und Links scala functional-programming recursion depth-first-search