Rekursiv reverse Sequenz in Clojure

Will ich das umkehren einer Reihenfolge, in Clojure ohne die reverse Funktion, und dies rekursiv.

Hier ist was ich kam mit:

(defn reverse-recursively [coll]
  (loop [r (rest coll)
         acc (conj () (first coll))]
    (if (= (count r) 0)
      acc
      (recur (rest r) (conj acc (first r))))))

Beispiel-Ausgabe:

user> (reverse-recursively '(1 2 3 4 5 6))
(6 5 4 3 2 1)
user> (reverse-recursively [1 2 3 4 5 6])
(6 5 4 3 2 1)
user> (reverse-recursively {:a 1 :b 2 :c 3})
([:c 3] [:b 2] [:a 1])

Fragen:

  1. Gibt es einen kürzeren Weg, dies zu tun, d.h. ohne Schleife/wiederholen?
  2. Gibt es eine Möglichkeit, dies zu tun, ohne mit einem "Akkumulator" - parameter in der Schleife?

Referenzen:

Was ist der beste Weg, um rekursiv reverse a string in Java?

http://groups.google.com/group/clojure/browse_thread/thread/4e7a4bfb0d71a508?pli=1

  • Waren Sie möglicherweise versucht, diese 4clojure problem? 🙂
  • Nein, ich war es nicht. "Reverse a string rekursiv" ist eine sehr häufige interview problem.
InformationsquelleAutor noahlz | 2011-12-06
  1. 24
    • Sie brauchen nicht zu zählen. Nur halt, wenn die Verbleibende Sequenz leer ist.
    • Sollten Sie nicht pre-bevölkern die acc, da die ursprüngliche Eingabe kann leer sein (und es ist mehr code).
    • Destructuring ist cool.
    (defn rückwärts-rekursiv [coll] 
(loop [[r & mehr :als alle] (seq coll) 
acc '()] 
(wenn alle 
(wiederholen mehr (cons r acc)) 
acc)))

    Als für loop/recur und die acc müssen Sie einige Weg, vorbei an rund um die Arbeits-Umgekehrt-Liste. Es ist entweder loop, oder fügen Sie einen anderen Parameter an die Funktion (die ist wirklich, was loop tut sowieso).

    Oder eine höhere Ordnung Funktion:

    user=> (conj reduzieren '() [1 2 3 4]) 
(4 3 2 1)
    • in Bezug auf "eine höhere Ordnung der Funktion" check-out (source reverse)
    • repl Abbrechen, wenn diese Funktion apply map ({:a 1 :b 2 :c 3}) .
    • Nun, technisch gesehen war meine Frage, "umgekehrte Sequenz" nicht "reverse alles, einschließlich einer Karte" ich denke, dass dieses problem nicht ausschließen. Hier ist der Fehler, btw: Clojure> (reverse-recursively {:a 1 :b 2}) java.lang.UnsupportedOperationException: nth not supported on this type: PersistentArrayMap
    • Auch, es sieht aus wie loop / recur ist natürlich erforderlich, für die tail-Rekursion, aber es gilt als ein "code smell" Clojure: twoguysarguing.wordpress.com/2010/07/26/...
    • Eigentlich ist der Artikel sagt, "loop/recur ist nicht ein code, der Geruch, aber seien Sie misstrauisch, es". Ich denke, was Sie bedeuten ist lieber, Landkarte, senken, etc. im Allgemeinen, aber nicht immer eine Lösung.
    • Die Lösung ermöglicht es, etwas zu arbeiten, mit der oben genannten Funktion (z.B. Karten), ist die Initialisierung der Schleife mit (seq coll), statt nur coll.
    • FWIW (reverse-recursively ()) zurück (nil). Dieses problem wird auch gelöst durch die Verwendung (seq coll), obwohl ich es lieber nicht destructure in der loop (das stellt eine ziemlich nutzlose :as), sondern um eine if-let innerhalb der Schleife.
    • Die :as all ist notwendig zu prüfen, die abschließende Bedingung, ohne die Einführung der null/false-as-element Probleme. Edit: nvm, ich habe herausgefunden, was du gemeint hast. Normalerweise mache ich das auch, aber ich habe auf ein destructuring kick in letzter Zeit.

    InformationsquelleAutor Alex Taggart
  2. 4

    Frage 1 mit ja beantwortet, das ist, was ich kam mit meiner Antwort auf die Rekursion koan (ich könnte nicht sagen, ob es gut war clojure praktizieren oder nicht).

    (defn recursive-reverse [coll]
    (if (empty? coll)
        []
        (conj (recursive-reverse (rest coll)) (first coll) )))
    • Nun, versuchen Sie dies: (recursive-reverse (apply str (seq (take 100000 (repeat "foo")))))
    • Fair genug, ich habe gerade auf den letzten Teil, das koan, wo die factorial-Funktion überläuft, wenn Sie nicht tun, ohne die loop/recur-Konstrukt. Also ich denke, jetzt kann ich sagen, dass es nicht gute Praxis 🙂 - cheers!
    • Das ist wirklich elegant!
    InformationsquelleAutor Fredrick Pennachi
  3. 4

    Zuliebe exhaustivenes, es gibt eine weitere Methode mit into. Da in intern verwendet conj es kann wie folgt verwendet werden :

    (defn reverse-list 
  "Reverse the element of alist."
  [lst]
  (into '() lst))
    InformationsquelleAutor pankajdoharey
  4. 2

    In der aktuellen version von Clojure gibt es eine eingebaute Funktion, die aufgerufen wird rseq. Für jeden, der vorbeifährt.

    • rseq erfordert die Eingabe-Sequenz Reversible, das es generell ungeeignet (nicht mit cons Listen, mit PersistentList mit LazySeq mit Saiten). Es ist gedacht als eine Optimierung für Sequenzen, die rückgängig gemacht werden können, in konstanter Zeit.
    InformationsquelleAutor
  5. 0
    (defn my-rev [col]
  (loop [ col col
          result []]
        (if (empty? col)
            result
            (recur (rest col) (cons (first col) result)))))

    Q1.

    Die JVM kann keine Optimierung der Rekursion eine rekursive Funktion, die würden direkt und stack overflow. Daher, Clojure, die die loop/recur. Also, ohne Verwendung einer Funktion, die sich wiederholen Tiefe der Rekursion können nicht definiert werden. (das wird auch intern verwendet, um wiederholt als eine Funktion Trampolin.)

    Q2.

    einer rekursiven Funktion durch wiederkehren, muss tail-rekursiv. Wenn der normale rekursive Funktion änderung tail-rekursive Funktion, so dass es notwendig ist, zu tragen über der Wert einer Variablen ist notwendig, da der Akku.

    • Die Reihenfolge einer Sequenz von anzeigen ändert sich nicht die Ausführung. Es wird aber wegen umgesetzt werden.
    • Ich verstehe nicht, Ihren Kommentar. "Folge umgesetzt werden?"
    • 1 :b 2 :c 3})->([:c (3)] [: b (2)] [: 1]) ist nicht notwendigerweise so. mein Ergebnis von Clojure1.3.0 ist ([:b (2)] [: c (3)] [: 1])
    • Ah, da PersistentArrayMap Clojure ist ungeordnet wie java.util.HashMap ? Das ist nicht intuitiv.
    • Ich weiß. Die Karte ist im Allgemeinen nicht bestimmt die Reihenfolge kennt. In der Reihenfolge, in der Sie eingefügt wurden, wie im Beispiel gezeigt, muss unbedingt.
    InformationsquelleAutor BLUEPIXY
  6. 0
    (defn reverse-seq [sss]
  (if (not (empty? sss))
    (conj (reverse-seq (rest sss)) (first sss))
  )
)
    InformationsquelleAutor Jiacai Liu
  7. 0
    (defn recursive-reverse [coll]
  (if (empty? coll)
    ()
    (concat (vector (peek coll)) (recursive-reverse (pop coll )))
  )
)
and test:
user=> (recursive-reverse [1])       
(1)
user=> (recursive-reverse [1 2 3 4 5])
(5 4 3 2 1)
    • Bitte fügen Sie eine Beschreibung zu Ihrem code.
    InformationsquelleAutor zongwu233
Schreibe einen Kommentar