Akkumulatoren, Konj und Rekursion
https://stackoverflow.com//questions/10666228
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe 45 Probleme von 4clojure.com gelöst und mir ist ein wiederkehrendes Problem bei der Art und Weise aufgefallen, wie ich versuche, einige Probleme mithilfe von Rekursion und Akkumulatoren zu lösen.
Ich werde versuchen, so gut ich kann zu erklären, was ich tue, um am Ende hässliche Lösungen zu finden, in der Hoffnung, dass einige Clojurer „bekommen“, was ich nicht bekomme.
In Aufgabe 34 wird beispielsweise darum gebeten, eine Funktion zu schreiben (ohne zu verwenden). Reichweite) nimmt zwei Ganzzahlen als Argumente und erstellt einen Bereich (ohne Bereich zu verwenden).Einfach gesagt, Sie tun (...1 7) und Sie erhalten (1 2 3 4 5 6).
Bei dieser Frage geht es nun nicht um die Lösung dieses speziellen Problems.
Was wenn ich wollen um dies mit Rekursion und einem Akkumulator zu lösen?
Mein Denkprozess läuft so ab:
Ich muss eine Funktion schreiben, die zunächst zwei Argumente benötigt (fn [x y] )
Ich muss eine Rekursion durchführen und den Überblick über eine Liste behalten. Ich verwende einen Akkumulator, also schreibe ich eine zweite Funktion in die erste und verwende ein zusätzliches Argument:
(Fn [xy
((fn g [xy acc] ...) x y '())
(Anscheinend kann ich diesen Clojure-Code auf SO nicht richtig formatieren!?)
Hier bin ich mir schon nicht sicher, ob ich es richtig mache:die erste Funktion muss Nehmen Sie genau zwei ganzzahlige Argumente (nicht mein Aufruf) und ich bin mir nicht sicher:Wenn ich einen Akkumulator verwenden möchte, kann ich dann einen Akkumulator verwenden, ohne eine verschachtelte Funktion zu erstellen?
Dann möchte ich Konj, aber ich kann nicht:
(conj 0 1)
Also mache ich seltsame Dinge, um sicherzustellen, dass ich zuerst eine Sequenz habe, und am Ende erhalte ich Folgendes:
(fn
[x y]
((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x)))
x
y
'()))
Aber dann ergibt das Folgendes:
(1 (2 (3 4)))
An Stelle von:
(1 2 3 4)
Also mache ich am Ende noch eine zusätzliche ebnen und es funktioniert, aber es ist total hässlich.
Ich fange an, ein paar Dinge zu verstehen und fange in manchen Fällen sogar an, eher clojuresker zu „denken“, aber ich habe ein Problem damit, die Lösung zu schreiben.
Hier habe ich mich zum Beispiel entschieden:
- einen Akku verwenden
- durch Inkrementieren rekursiv machen X bis es erreicht j
Aber am Ende lande ich bei der Monstrosität oben.
Es gibt eine viel Es gibt keine Möglichkeit, dieses Problem zu lösen, und wieder einmal ist es nicht das, was ich suche.
Was ich suche, ist, wie ich, nachdem ich mich für conj/conj, die Verwendung eines Akkumulators und die Rekursion entschieden habe, zu Folgendem kommen kann (nicht von mir geschrieben):
#(loop [i %1
acc nil]
(if (<= %2 i)
(reverse acc)
(recur (inc i) (cons i acc))))
An Stelle von:
((fn
f
[x y]
(flatten
((fn
g
[x y acc]
(if (= x y) acc (conj (conj acc (g (inc x) y acc)) x)))
x
y
'())))
1
4)
Ich denke, es ist ein Anfang, ein paar Probleme lösen zu können, aber ich bin etwas enttäuscht von den hässlichen Lösungen, die ich normalerweise vorbringe ...
Lösung
Ich denke, hier gibt es ein paar Dinge zu lernen.
Erste, eine Art allgemeine Regel – rekursive Funktionen haben normalerweise eine natürliche Reihenfolge, und das Hinzufügen eines Akkumulators kehrt diese um.Sie können das sehen, denn wenn ein „normales“ (ohne Wenn die rekursive Funktion „Akkumulator“ ausgeführt wird, berechnet sie einen Wert, führt dann eine Rekursion durch, um das Ende der Liste zu generieren, und endet schließlich mit einer leeren Liste.Im Gegensatz dazu beginnt man bei einem Akkumulator mit der leeren Liste und fügt Dinge an den Anfang hinzu – sie wächst in die andere Richtung.
Wenn Sie also einen Akkumulator hinzufügen, erhalten Sie normalerweise eine umgekehrte Reihenfolge.
Jetzt ist das oft egal.Wenn Sie beispielsweise keine Sequenz, sondern einen Wert generieren, der die wiederholte Anwendung von a darstellt kommutativ Operator (wie Addition oder Multiplikation).dann bekommst du in beiden Fällen die gleiche Antwort.
Aber in Ihrem Fall wird es eine Rolle spielen.Sie erhalten die Liste rückwärts:
(defn my-range-0 [lo hi] ; normal recursive solution
(if (= lo hi)
nil
(cons lo (my-range-0 (inc lo) hi))))
(deftest test-my-range-1
(is (= '(0 1 2) (my-range-0 0 3))))
(defn my-range-1 ; with an accumulator
([lo hi] (my-range-1 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (cons lo acc)))))
(deftest test-my-range-1
(is (= '(2 1 0) (my-range-1 0 3)))) ; oops! backwards!
Und oft können Sie das Problem am besten dadurch beheben, dass Sie die Liste am Ende einfach umkehren.
Aber hier gibt es eine Alternative: Wir können die Arbeit tatsächlich rückwärts machen.anstatt inkrementieren die untere Grenze, die Sie können dekrementieren die Obergrenze:
(defn my-range-2
([lo hi] (my-range-2 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(let [hi (dec hi)]
(recur lo hi (cons hi acc))))))
(deftest test-my-range-2
(is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order
[Hinweis – es gibt unten eine andere Möglichkeit, die Dinge umzukehren;ich habe meine Argumentation nicht sehr gut strukturiert]
zweite, wie Sie in sehen können my-range-1 Und my-range-2, Eine gute Möglichkeit, eine Funktion mit einem Akkumulator zu schreiben, ist als Funktion mit zwei verschiedenen Argumentsätzen.Dadurch erhalten Sie eine (meiner Meinung nach) sehr saubere Implementierung, ohne dass verschachtelte Funktionen erforderlich sind.
Sie haben auch allgemeinere Fragen zu Sequenzen, conj und dergleichen.Hier ist Clojure etwas chaotisch, aber auch nützlich.Oben habe ich eine sehr traditionelle Sichtweise mit auf Nachteile basierenden Listen dargelegt.Clojure empfiehlt Ihnen jedoch, andere Sequenzen zu verwenden.und im Gegensatz zu Cons-Listen wachsen Vektoren nach rechts, nicht nach links.Also ein anderer Eine Möglichkeit, dieses Ergebnis umzukehren, besteht darin, einen Vektor zu verwenden:
(defn my-range-3 ; this looks like my-range-1
([lo hi] (my-range-3 lo hi []))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-3 ; except that it works right!
(is (= [0 1 2] (my-range-3 0 3))))
Hier conj fügt nach rechts hinzu.Ich habe es nicht verwendet conj In my-range-1, also wird es hier umgeschrieben, um es klarer zu machen:
(defn my-range-4 ; my-range-1 written using conj instead of cons
([lo hi] (my-range-4 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-4
(is (= '(2 1 0) (my-range-4 0 3))))
Beachten Sie, dass dieser Code aussieht sehr ähnlich zu my-range-3 aber das Ergebnis ist rückwärts, weil wir mit einer leeren Liste beginnen, nicht mit einem leeren Vektor.in beiden Fällen, conj fügt das neue Element an der „natürlichen“ Position hinzu.Bei einem Vektor befindet er sich rechts, bei einer Liste jedoch links.
Und mir ist gerade aufgefallen, dass Sie möglicherweise nicht wirklich verstehen, was eine Liste ist.im Grunde ein cons erstellt eine Box, die zwei Dinge (seine Argumente) enthält.Das erste ist der Inhalt und das zweite ist der Rest der Liste.also die Liste (1 2 3) ist grundsätzlich (cons 1 (cons 2 (cons 3 nil))).im Gegensatz dazu der Vektor [1 2 3] funktioniert eher wie ein Array (obwohl ich denke, dass es mithilfe eines Baums implementiert wird).
Also conj ist etwas verwirrend, da die Funktionsweise vom ersten Argument abhängt.für eine Liste ruft es auf cons und fügt so Dinge auf der linken Seite hinzu.aber für einen Vektor erweitert es das Array (ähnliches Ding) nach rechts.Beachten Sie auch das conj Nimmt eine vorhandene Sequenz als erstes Argument und das hinzuzufügende Ding als zweites, while cons ist das Gegenteil (das hinzuzufügende Ding kommt zuerst).
Der gesamte oben genannte Code ist unter verfügbar https://github.com/andrewcooke/clojure-lab
aktualisieren:Ich habe die Tests so umgeschrieben, dass das erwartete Ergebnis eine Liste in Anführungszeichen ist, wenn der Code eine Liste generiert. = vergleicht Listen und Vektoren und gibt true zurück, wenn der Inhalt derselbe ist. Wenn Sie ihn jedoch explizit machen, wird deutlicher, was Sie in jedem Fall tatsächlich erhalten.beachten Sie, dass '(0 1 2) mit einem ' Vorne ist es genau so (list 0 1 2) - Die ' verhindert, dass die Liste ausgewertet wird (ohne sie, 0 würde als Befehl behandelt werden).
Andere Tipps
Nachdem ich das alles gelesen habe, bin ich mir immer noch nicht sicher, warum man einen Akku braucht.
((fn r [a b]
(if (<= a b)
(cons a (r (inc a) b))))
2 4)
=> (2 3 4)
scheint eine ziemlich intuitive rekursive Lösung zu sein.Das Einzige, was ich am „echten“ Code ändern würde, ist die Verwendung von Lazy-Seq, damit Ihnen bei großen Bereichen nicht der Stapel ausgeht.
wie ich zu dieser Lösung gekommen bin:
Wenn Sie darüber nachdenken, eine Rekursion zu verwenden, ist es meiner Meinung nach hilfreich, das Problem mit möglichst wenigen Begriffen zu formulieren, die Ihnen einfallen, und möglichst viel „Arbeit“ der Rekursion selbst zu überlassen.
Insbesondere wenn Sie vermuten, dass Sie ein oder mehrere Argumente/Variablen weglassen können, ist dies normalerweise der richtige Weg – zumindest wenn Sie möchten, dass der Code leicht zu verstehen und zu debuggen ist;Manchmal gehen Sie am Ende Kompromisse bei der Einfachheit ein, um die Ausführungsgeschwindigkeit zu erhöhen oder die Speichernutzung zu reduzieren.
In diesem Fall dachte ich, als ich anfing zu schreiben:„Das erste Argument der Funktion ist auch das Startelement des Bereichs, und das letzte Argument ist das letzte Element.“Rekursives Denken ist etwas, das man sich erst einmal aneignen muss, aber eine ziemlich naheliegende Lösung wäre dann zu sagen:A Reichweite [a, b] ist eine Sequenz, die mit element beginnt a gefolgt von A Reichweite von [a + 1, b].Bereiche können also tatsächlich rekursiv beschrieben werden.Der Code, den ich geschrieben habe, ist so ziemlich eine direkte Umsetzung dieser Idee.
Nachtrag:
Ich habe festgestellt, dass beim Schreiben von Funktionscode Akkumulatoren (und Indizes) am besten vermieden werden sollten.Manche Probleme erfordern sie, aber wenn Sie einen Weg finden, sie loszuwerden, ist es in der Regel besser, wenn Sie dies tun.
Nachtrag 2:
In Bezug auf rekursive Funktionen und Listen/Sequenzen, Die Die nützlichste Denkweise beim Schreiben dieser Art von Code besteht darin, Ihr Problem in Form von „dem ersten Element (Kopf) einer Liste“ und „dem Rest der Liste (Ende)“ zu formulieren.
Ich kann den bereits guten Antworten, die Sie erhalten haben, nichts hinzufügen, werde aber allgemein antworten.Während Sie den Clojure-Lernprozess durchlaufen, werden Sie möglicherweise feststellen, dass viele, aber nicht alle Lösungen mithilfe der in Clojure integrierten Funktionen gelöst werden können, z. B. einer Karte und auch der Betrachtung von Problemen in Form von Sequenzen.Das bedeutet nicht, dass Sie Dinge nicht rekursiv lösen sollten, aber Sie werden hören – und ich halte es für einen klugen Rat –, dass die Clojure-Rekursion für die Lösung von Problemen auf sehr niedriger Ebene gedacht ist, die Sie auf andere Weise nicht lösen können.
Ich verarbeite zufällig viel CSV-Dateien und habe kürzlich einen Kommentar erhalten, dass nth Abhängigkeiten erstellt.Dies ist der Fall, und die Verwendung von Karten kann es mir ermöglichen, Elemente zum Vergleich anhand ihres Namens und nicht anhand ihrer Position zu ermitteln.
Ich werde den Code, der nth mit clojure-csv-analysierten Daten in zwei kleinen Anwendungen verwendet, die sich bereits in der Produktion befinden, nicht wegwerfen.Aber ich werde das nächste Mal in einer geordneteren Reihenfolge über die Dinge nachdenken.
Es ist schwierig, aus Büchern zu lernen, in denen es um Vektoren und n-te Schleifen geht.wiederkehren und so weiter, und dann erkennen Sie, dass das Erlernen von Clojure Sie von dort aus weiterbringt.
Eines der Dinge, die meiner Meinung nach beim Erlernen von Clojure gut sind, ist, dass die Gemeinschaft respektvoll und hilfsbereit ist.Schließlich helfen sie jemandem, dessen erste Lernsprache Fortran IV auf einem CDC Cyber mit Lochkarten war und dessen erste kommerzielle Programmiersprache PL/I war.
Wenn ich das mit einem Akku lösen würde, würde ich so etwas tun:
user=> (defn my-range [lb up c]
(if (= lb up)
c
(recur (inc lb) up (conj c lb))))
#'user/my-range
dann ruf es mit an
#(my-range % %2 [])
Natürlich würde ich es verwenden letfn oder etwas, das man umgehen kann, wenn man es nicht hat defn verfügbar.
Also ja, Sie benötigen eine innere Funktion, um den Akkumulator-Ansatz verwenden zu können.
Mein Denkprozess ist, dass, sobald ich fertig bin, die Antwort, die ich zurückgeben möchte, im Akkumulator sein wird.(Das steht im Gegensatz zu Ihrer Lösung, bei der Sie viel Arbeit darauf verwenden, die Endbedingung zu finden.) Also suche ich nach meiner Endbedingung und wenn ich sie erreicht habe, gebe ich den Akkumulator zurück.Ansonsten hefte ich den nächsten Artikel an den Akku an und greife zu einem kleineren Gehäuse zurück.Es gibt also nur zwei Dinge herauszufinden, was die Endbedingung ist und was ich in den Akkumulator einfügen möchte.
Die Verwendung eines Vektors hilft sehr, weil conj wird daran angehängt und es besteht keine Notwendigkeit, es zu verwenden reverse.
Ich nehme auch 4clojure, übrigens.Da ich beschäftigt war, bin ich in letzter Zeit in Rückstand geraten.
Es sieht so aus, als ob es bei Ihrer Frage eher darum geht, wie man lernt, als um ein technisches/codetechnisches Problem.Am Ende schreiben Sie diese Art von Code, weil aus welcher Art und Weise oder Quelle auch immer Sie das Programmieren im Allgemeinen oder Clojure im Besonderen gelernt haben, in Ihrem Gehirn eine „neuronale Autobahn“ entstanden ist, die Sie dazu bringt, auf diese bestimmte Weise über die Lösungen nachzudenken, und am Ende schreiben Sie Code so was.Grundsätzlich nutzen Sie bei jedem Problem (in diesem speziellen Fall Rekursion und/oder Akkumulation) diese „neuronale Autobahn“ und kommen immer auf diese Art von Code.
Die Lösung, um diese „neuronale Autobahn“ loszuwerden, besteht darin, für den Moment mit dem Schreiben von Code aufzuhören, die Tastatur fernzuhalten und damit zu beginnen, viel vorhandenen Clojure-Code zu lesen (von vorhandenen Lösungen des 4clojure-Problems bis hin zu Open-Source-Projekten auf Github) und darüber nachzudenken es tief (lesen Sie eine Funktion sogar zwei- bis dreimal, damit sie sich wirklich in Ihrem Gehirn niederlassen kann).Auf diese Weise würden Sie am Ende Ihre bestehende „neuronale Autobahn“ zerstören (die den Code erzeugt, den Sie jetzt schreiben) und eine neue „neuronale Autobahn“ erstellen, die den schönen und idiomatischen Clojure-Code produzieren würde.Versuchen Sie außerdem, nicht direkt mit der Codeeingabe zu beginnen, sobald Sie ein Problem sehen, sondern nehmen Sie sich etwas Zeit, um klar und gründlich über das Problem und die Lösungen nachzudenken.
