Wie erstellt man eine anonyme rekursive Funktion in Clojure, die eine Lazy-Seq erzeugt?

Question

Editar : Ich habe beim Schreiben dieses Artikels eine Teilantwort auf meine eigene Frage gefunden, aber ich denke, sie kann noch verbessert werden, also werde ich sie trotzdem veröffentlichen. Vielleicht gibt es da draußen eine bessere Lösung?

Ich suche nach einer einfachen Möglichkeit, rekursive Funktionen in einer let Form ohne Rückgriff auf letfn . Dies ist wahrscheinlich eine unvernünftige Anfrage, aber der Grund, warum ich nach dieser Technik suche, ist, weil ich eine Mischung aus Daten und rekursiven Funktionen habe, die voneinander abhängig sind, so dass eine Menge verschachtelter let et letfn Erklärungen.

Ich wollte die rekursiven Funktionen schreiben, die faule Sequenzen wie diese erzeugen (am Beispiel der Fibonacci-Folge):

(let [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  (take 10 fibs))

Aber es scheint in Clojure, dass fibs kann sein eigenes Symbol während der Bindung nicht verwenden. Der offensichtliche Weg, dies zu umgehen, ist die Verwendung von letfn

(letfn [(fibo [] (lazy-cat [0 1] (map + (fibo) (rest (fibo)))))]
  (take 10 (fibo)))

Aber wie ich bereits sagte, führt dies zu einer Menge umständlicher Verschachtelungen und abwechselnder let et letfn .

Um dies zu tun, ohne letfn und nur mit let Ich habe damit begonnen, etwas zu schreiben, das meiner Meinung nach den U-Kombinator verwendet (ich habe erst heute von diesem Konzept gehört):

(let [fibs (fn [fi] (lazy-cat [0 1] (map + (fi fi) (rest (fi fi)))))]
  (take 10 (fibs fibs)))

Aber wie wird man die Redundanz von (fi fi) ?

An diesem Punkt entdeckte ich die Antwort auf meine eigene Frage, nachdem ich mich eine Stunde lang abgemüht und schrittweise Bits zum Kombinator Q hinzugefügt hatte.

(let [Q (fn [r] ((fn [f] (f f)) (fn [y] (r (fn [] (y y))))))
      fibs (Q (fn [fi] (lazy-cat [0 1] (map + (fi) (rest (fi))))))]
  (take 10 fibs))

Was ist das? Q Kombinator genannt, den ich zur Definition einer rekursiven Folge verwende? Es sieht aus wie der Y-Kombinator ohne Argumente x . Ist es dasselbe?

(defn Y [r] 
  ((fn [f] (f f)) 
   (fn [y] (r (fn [x] ((y y) x))))))

Gibt es eine andere Funktion in clojure.core oder clojure.contrib, die die Funktionalität von Y oder Q bietet? Ich kann mir nicht vorstellen, dass das, was ich gerade getan habe, idiomatisch war...

Answer 1

Letrec

Ich habe eine letrec Makro für Clojure zu entwickeln, hier ist das Wesentliche . Es wirkt wie Schemes letrec (falls Sie das zufällig wissen), was bedeutet, dass es eine Kreuzung ist zwischen let et letfn : Sie können eine Menge von Namen an gegenseitig rekursive Werte binden, ohne dass diese Werte Funktionen sein müssen (träge Sequenzen sind auch in Ordnung), solange es möglich ist, den Kopf jedes Elements auszuwerten, ohne auf die anderen zu verweisen (das ist Haskell -- oder vielleicht typentheoretische -- Sprache; "Kopf" könnte hier z.B. für das träge Sequenzobjekt selbst stehen, mit -- entscheidend! -- keine Erzwingung involviert ist).

Sie können damit Dinge schreiben wie

(letrec [fibs (lazy-cat [0 1] (map + fibs (rest fibs)))]
  fibs)

was normalerweise nur auf höchster Ebene möglich ist. Siehe die Gist für weitere Beispiele.

Wie im Text der Frage erwähnt, könnte die obige Formulierung ersetzt werden durch

(letfn [(fibs [] (lazy-cat [0 1] (map + (fibs) (rest (fibs)))))]
  (fibs))

für dasselbe Ergebnis in exponentieller Zeit die letrec Version hat lineare Komplexität (ebenso wie eine Top-Level (def fibs (lazy-cat [0 1] (map + fibs (rest fibs)))) Form).

iterieren

Selbstrekursive Sequenzen können oft mit iterate -- nämlich dann, wenn ein fester Bereich von look-behind ausreicht, um ein bestimmtes Element zu berechnen. Siehe clojure.contrib.lazy-seqs für ein Beispiel, wie man berechnet fibs con iterate .

clojure.contrib.seq

c.c.seq bietet eine interessante Funktion namens rec-seq und ermöglicht Dinge wie

(take 10 (cseq/rec-seq fibs (map + fibs (rest fibs))))

Es hat die Einschränkung, dass man nur eine einzige selbstrekursive Sequenz konstruieren kann, aber es könnte möglich sein, aus dem Quelltext einige Implementierungsideen zu übernehmen, die vielfältigere Szenarien ermöglichen. Wenn eine einzelne selbstrekursive Sequenz, die nicht auf oberster Ebene definiert ist, das ist, was Sie wollen, muss dies die idiomatische Lösung sein.

Kombinatoren

Bei Kombinatoren wie den in der Frage genannten ist zu beachten, dass sie durch das Fehlen von TCO (Tail-Call-Optimierung) auf der JVM (und damit in Clojure, das die Aufrufkonventionen der JVM direkt nutzt, um die beste Leistung zu erzielen) behindert werden.

oberste Ebene

Es gibt auch die Möglichkeit, die sich gegenseitig rekursiven "Dinge" auf oberster Ebene zu platzieren, möglicherweise in einem eigenen Namensraum. Das funktioniert nicht so gut, wenn diese "Dinge" irgendwie parametrisiert werden müssen, aber Namespaces können bei Bedarf dynamisch erstellt werden (siehe clojure.contrib.with-ns für Ideen zur Umsetzung).

abschließende Bemerkungen

Ich gebe bereitwillig zu, dass die letrec ist weit davon entfernt, idiomatisches Clojure zu sein, und ich würde es vermeiden, es in Produktionscode zu verwenden, wenn irgendetwas anderes ausreichen würde (und da es immer die Option der obersten Ebene gibt...). Allerdings ist es (IMO!) nett, damit zu spielen und es scheint gut genug zu funktionieren. Ich persönlich bin daran interessiert, herauszufinden, wie viel man ohne diese Option erreichen kann. letrec und inwieweit ein letrec Makro macht die Dinge einfacher / sauberer... Ich habe mir dazu noch keine Meinung gebildet. Also, hier ist es. Noch einmal, für den Fall einer einzelnen selbstrekursiven Seq, iterate oder Contrib könnte der beste Weg sein.

Answer 2

fn nimmt ein optionales Namensargument an, wobei dieser Name an die Funktion in ihrem Körper gebunden ist. Mit dieser Funktion könnten Sie schreiben fibs als:

(def fibs ((fn generator [a b] (lazy-seq (cons a (generator b (+ a b))))) 0 1))