Akkus, Conj und Rekursion

Question

Ich habe 45 Probleme von 4clojure.com gelöst und ich bemerkte ein wiederkehrendes Problem in der Art, wie ich versuche, einige Probleme mit Rekursion und Akkumulatoren zu lösen.

Ich werde versuchen, das Beste zu erklären, was ich tun kann, um mit fugly Lösungen zu enden, in der Hoffnung, dass einige Clojurer "bekommen" würden, was ich nicht bekomme.

Zum Beispiel fragt Problem 34, eine Funktion zu schreiben (ohne Verwendung Bereich) zwei ganze Zahlen als Argumente und erstellt einen Bereich (ohne Verwendung von Bereich). Stellen Sie einfach (... 1 7) und Sie bekommen (1 2 3 4 5 6).

Nun geht es in dieser Frage nicht darum, dieses spezielle Problem zu lösen.

Was ist, wenn ich wollen, um dies zu lösen, indem ich Rekursion und einen Akkumulator verwende?

Mein Denkprozess geht so:

• Ich brauche eine Funktion nimmt zwei Argumente zu schreiben, beginne ich mit (fn [xy])

• Ich muss recurse und ich werde Spur einer Liste zu halten brauchen, ich werde einen Speicher verwenden, so schreibe ich eine zweite Funktion innerhalb der ersten ein zusätzliches Argument unter:

  (fn [xy]
  ((fn g [xy acc] ...) x y ‚())

(anscheinend kann ich nicht richtig formatiert werden, dass Clojure Code auf SO !?)

Hier bin ich mir schon nicht sicher ob ich es richtig mache: die erste Funktion muss genau zwei ganzzahlige Argumente nehmen (nicht mein Aufruf) und ich bin mir nicht sicher: wenn ich einen Akku verwenden möchte, kann ich einen verwenden Akkumulator ohne eine geschachtelte Funktion zu erstellen?

Dann möchte ich Konj, aber ich kann nicht tun:

(conj 0 1) 

so seltsame Dinge, die ich tun, um sicherzustellen, dass ich zum ersten Mal eine Sequenz haben und ich mit diesem Ende:

(fn 
    [x y] 
    ((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x))) 
    x 
    y 
    '())) 

Aber dies dann produzieren:

(1 (2 (3 4))) 

Statt dessen:

(1 2 3 4) 

So beende ich eine zusätzliche abflachen tun und es funktioniert, aber es ist völlig hässlich.

Ich fange an, ein paar Dinge zu verstehen, und ich fange manchmal an, in einer clojuresque Weise "zu denken", aber ich habe ein Problem, die Lösung zu schreiben.

Zum Beispiel hier habe ich beschlossen:

• einen Speicher zu verwenden
• durch Erhöhen x rekursiv, bis es erreicht y

Aber ich mit der Ungeheuerlichkeit oben am Ende .

Es gibt einen viele die Art und Weise, dieses Problem und wieder zu lösen, ist es nicht das, was ich bin nach.

Was ich nach, wie, nachdem ich cons/conj entschieden, einen Speicher verwenden, und recurse, ich kann mit diesem Ende (nicht von mir geschrieben):

#(loop [i %1 
     acc nil] 
    (if (<= %2 i) 
    (reverse acc) 
    (recur (inc i) (cons i acc)))) 

Statt dem :

((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 nehme es ein Anfang ein paar Probleme lösen zu können, aber ich bin ein bisschen durch die hässlichen Lösungen, die ich ...

Answer 1

ich denke, es gibt ein paar Dinge zu lernen hier.

erste, eine Art allgemeine Regel - rekursive Funktionen haben normalerweise eine natürliche Reihenfolge, und das Hinzufügen eines Akkumulators kehrt das um. Sie können sehen, dass, weil, wenn ein „normale“ (ohne Akkumulator) rekursive Funktion läuft, ist es etwas Arbeit hat einen Wert zu berechnen, dann recurses den Schwanz der Liste zu erzeugen, schließlich mit einer leeren Liste endet. im Gegensatz dazu, mit einem Akkumulator, beginnen Sie mit der leeren Liste und fügen Sie Dinge an die Front - es wächst in die andere Richtung.

so typisch, wenn Sie einen Speicher hinzufügen, erhalten Sie eine umgekehrte Reihenfolge.

jetzt ist das oft egal. Wenn Sie beispielsweise keine Sequenz generieren, sondern einen Wert, der die wiederholte Anwendung eines kommutativen Operators ist (wie Addition oder Multiplikation). dann bekommst du die gleiche Antwort.

aber in Ihrem Fall wird es wichtig sein. Sie gehen um die Liste zu bekommen 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 die beste Sie können dies tun, zu beheben ist nur am Ende dieser Liste umkehren.

aber hier gibt es eine Alternative - wir können die Arbeit nach hinten tatsächlich tun. statt Erhöhen die untere Grenze Sie können Dekrement die obere Grenze:

(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 

[Anmerkung - es ist eine andere Art, die Dinge unter Umkehr; ich habe nicht mein Argument Struktur sehr gut]

zweite, wie Sie in my-range-1 und my-range-2, eine nette Art und Weise des Schreibens eine Funktion mit einem Akkumulator ist als eine Funktion mit zwei unterschiedlichen Sätzen von Argumenten zu sehen. das gibt Ihnen eine sehr saubere (imho) Implementierung ohne die Notwendigkeit für verschachtelte Funktionen.

---

auch Sie haben einige allgemeinere Fragen zu Sequenzen, conj und dergleichen. Hier ist clojure irgendwie unordentlich, aber auch nützlich. oben habe ich eine sehr traditionelle Sicht mit Cons-basierten Listen gegeben. aber clojure ermutigt Sie, andere Sequenzen zu verwenden. und im Gegensatz zu den Cons-Listen wachsen Vektoren nach rechts, nicht nach links.so andere Weg, um dieses Ergebnis umzukehren ist, 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 nach rechts hinzuzufügen. i nicht genutzt conj in my-range-1, so ist es hier neu geschrieben klarer sein:

(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 sehr ähnlich sieht my-range-3 aber das Ergebnis nach hinten ist, weil wir mit einem fangen leere Liste, kein leerer Vektor. In beiden Fällen fügt conj das neue Element in die "natürliche" Position ein. für einen Vektor, der rechts ist, aber für eine Liste ist es auf der linken Seite.

und mir ist gerade eingefallen, dass Sie nicht wirklich verstehen, was eine Liste ist. im Grunde eine cons erstellt eine Box, die zwei Dinge (seine Argumente) enthält. der erste ist der Inhalt und der zweite ist der Rest der Liste. so ist die Liste (1 2 3) im Grunde (cons 1 (cons 2 (cons 3 nil))). Im Gegensatz dazu funktioniert der Vektor [1 2 3] mehr wie ein Array (obwohl ich denke, dass es mit einem Baum implementiert ist).

so ist conj ein bisschen verwirrend, weil die Art, wie es funktioniert, hängt vom ersten Argument ab. für eine Liste ruft es 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, dass conj eine vorhandene Sequenz als erstes arg und Ding als zweites, cons das Gegenteil (Ding zu add kommt zuerst) nimmt.

---

alle oben genannten Code verfügbar bei https://github.com/andrewcooke/clojure-lab

---

Update: umschrieb ich die Tests, so dass das erwartete Ergebnis eine zitierte Liste in den Fällen, in denen der Code eine Liste erzeugt. = vergleicht Listen und Vektoren und gibt true zurück, wenn der Inhalt derselbe ist, aber wenn er explizit gemacht wird, wird deutlicher, was Sie tatsächlich in jedem Fall erhalten. Beachten Sie, dass '(0 1 2) mit einer ' vorne ist genau wie (list 0 1 2) - die ' stoppt die Liste von ausgewertet (ohne es, 0 würde als ein Befehl behandelt werden).

Answer 2

nach der Lektüre all das zu produzieren, sind in der Regel enttäuscht, ich Ich bin mir immer noch nicht sicher, warum du eine brauchen würdest n Akku.

((fn r [a b] 
    (if (<= a b) 
     (cons a (r (inc a) b)))) 
    2 4) 
=> (2 3 4) 

scheint wie eine ziemlich intuitive rekursive Lösung. Die einzige Sache, die ich in "echtem" Code ändern würde, ist, lazy-seq zu verwenden, damit Sie nicht den Stapel für große Bereiche ausgehen.

, wie ich zu dieser Lösung:

Wenn Sie die Verwendung von Rekursion denkt, finde ich es hilft, das Problem mit möglichst wenig Bezug zu versuchen und zu erklären, Sie denken können, und versucht, die Hand so viel "Arbeit" an der Rekursion selbst.

Insbesondere wenn Sie vermuten, dass Sie ein oder mehrere Argumente/Variablen löschen können, ist dies normalerweise der Weg zu gehen - zumindest wenn Sie möchten, dass der Code einfach zu verstehen und zu debuggen; Manchmal schadet man der Einfachheit zugunsten der Ausführungsgeschwindigkeit oder der Speicherauslastung.

In diesem Fall, was ich dachte, als ich begann zu schreiben war: "Das erste Argument der Funktion ist auch das Startelement des Bereichs, und das letzte Argument ist das letzte Element". Rekursive Denken ist etwas, das Sie Art, sich von dem, zu trainieren, zu tun, aber eine ziemlich offensichtliche Lösung dann sagen: ein Bereich[a, b] eine Sequenz mit ab Element ist agefolgt von ein Bereich von [a + 1, b]. So können Bereiche tatsächlich rekursiv beschrieben werden. Der Code, den ich geschrieben habe, ist eine direkte Umsetzung dieser Idee.

Nachtrag:

Ich habe festgestellt, dass, wenn funktionellen Code zu schreiben, Akkumulatoren (und Indizes) werden am besten vermieden werden. Einige Probleme erfordern sie, aber wenn Sie einen Weg finden, um sie loszuwerden, sind Sie normalerweise besser dran, wenn Sie es tun.

Nachtrag 2:

In Bezug auf rekursive Funktionen und Listen/Sequenzen, die nützlichsten Weise zu denken, wenn diese Art von Code zu schreiben ist Ihr Problem in Bezug auf „das erste Element zum Zustand (Kopf) einer Liste "und" der Rest der Liste (Schwanz) ".

Answer 3

Wenn ich dies mit einem Akkumulator gelöst ich etwas tun würde, wie:

user=> (defn my-range [lb up c] 
     (if (= lb up) 
      c 
      (recur (inc lb) up (conj c lb)))) 
#'user/my-range 

dann nennt es mit

#(my-range % %2 []) 

Natürlich, ich letfn oder etwas verwenden würde, um zu bekommen, nicht mit defn verfügbar.

Also ja, Sie brauchen eine innere Funktion, um den Akku-Ansatz zu verwenden.

Mein Denkprozess ist, dass, sobald ich fertig bin, die Antwort, die ich zurückgeben will, im Akkumulator sein wird. (Das steht im Gegensatz zu deiner Lösung, wo du eine Menge Arbeit an der Endbedingung anknüpfst.) Also suche ich nach meiner Endbedingung und wenn ich sie erreicht habe, gebe ich den Akkumulator zurück. Ansonsten hefte ich den nächsten Gegenstand an den Akkumulator und wiederhole ihn für einen kleineren Fall. Es gibt also nur zwei Dinge zu klären, was die Endbedingung ist und was ich in den Akku legen möchte.

Die Verwendung eines Vektors hilft sehr, da conj an ihn angehängt wird und es keine Notwendigkeit gibt, reverse zu verwenden.

I'm on 4clojure too, zw. Ich war beschäftigt, also bin ich in letzter Zeit zurückgefallen.

Answer 4

Es sieht so aus, als ob Ihre Frage mehr über "wie man lernt", dann ein technisches/Codeproblem. Am Ende schreiben Sie diese Art von Code, denn von welcher Art oder Quelle Sie gelernt haben Programmierung im Allgemeinen oder Clojure im Besonderen hat eine "neurale Autobahn" in Ihrem Gehirn geschaffen, die Sie über die Lösungen auf diese besondere Weise denken, und Sie am Ende Code schreiben so was. Grundsätzlich, wenn Sie jedes Problem haben (in diesem speziellen Fall Rekursion und/oder Akkumulation) Sie am Ende mit dieser "neuralen Autobahn" und immer mit dieser Art von Code kommen. Die Lösung, um diese "neurale Autobahn" loszuwerden, besteht darin, den Code für den Moment nicht zu schreiben, diese Tastatur fernzuhalten und viel vorhandenen Clojure-Code zu lesen (von existierenden Lösungen des 4clojure-Problems zu Open Source-Projekten auf github)) und denke tief darüber nach (lies sogar 2-3 mal eine Funktion, damit es sich wirklich in deinem Gehirn niederlässt). Auf diese Weise würden Sie am Ende Ihre bestehende "neurale Autobahn" zerstören (die den Code produzieren, den Sie jetzt schreiben) und eine neue "neurale Autobahn" schaffen, die den schönen und idiomatischen Clojure-Code produzieren würde. Versuchen Sie auch nicht, sobald Sie ein Problem erkannt haben, zur Eingabe von Code zu springen, sondern geben Sie sich etwas Zeit, um klar und tief über das Problem und die Lösungen nachzudenken.

Answer 5

Ich kann nicht zu den bereits guten Antworten hinzufügen, die Sie erhalten haben, aber ich werde im Allgemeinen antworten. Wenn Sie den Clojure-Lernprozess durchlaufen, werden Sie vielleicht feststellen, dass viele, aber nicht alle Lösungen mit Clojure-Einbauten gelöst werden können, wie zum Beispiel Karten und auch die Problematik von Sequenzen. Dies bedeutet nicht, dass Sie die Dinge nicht rekursiv lösen sollten, aber Sie werden hören - und ich glaube, es ist ein weiser Ratschlag -, dass Clojure Rekursion für die Lösung sehr niedriger Probleme ist, die Sie nicht anders lösen können.

Ich mache viel CSV-Dateiverarbeitung und erhielt kürzlich einen Kommentar, dass nth Abhängigkeiten erstellt.Es tut, und die Verwendung von Karten kann mir erlauben, Elemente zum Vergleich nach Namen und nicht nach Position zu bekommen.

Ich bin nicht den Code zu werfen, gehen, die mit Clojure-csv analysierten Daten in zwei kleinen Anwendungen, die bereits in der Produktion n-ten verwendet. Aber ich werde beim nächsten Mal über Dinge auf eine sequentiellere Weise nachdenken.

Es ist schwierig, von Büchern zu lernen, die über Vektoren und n-ten, Schleife reden .. wiederholen und so weiter, und erkennt, dann Clojure Lernen Sie sich von dort wächst.

Eines der Dinge, die ich gefunden habe, dass über das Lernen Clojure gut ist, ist die Gemeinschaft respektvoll und nützlich ist. Immerhin helfen sie jemandem, dessen erste Lernsprache Fortran IV war, auf einer CDC Cyber ​​mit Lochkarten, und deren erste kommerzielle Programmiersprache PL/I war.