Nehmen wir an, Sie haben eine rekursive Funktion, die in einem let-Block definiert ist:
%Vor% Dies kann mechanisch transformiert werden, um memoize zu verwenden:
fn in einem Aufruf in memoize . partial . Die Umwandlung des obigen Codes führt zu:
%Vor%Das funktioniert, fühlt sich aber zu kompliziert an. Die Frage ist: Gibt es einen einfacheren Weg?
Ich gehe Risiken ein, da ich kein Gelehrter bin, aber das glaube ich nicht. Sie haben so ziemlich das Standard-Ding gemacht, was im Endeffekt eine partielle Anwendung von Memoization durch einen Fixpunktkombinator ist.
Sie könnten jedoch versuchen, mit Makros herumzuhantieren (in einfachen Fällen könnte es einfach sein, Syntax-Quote würde Namensauflösung für Sie tun und Sie könnten damit arbeiten). Ich werde es versuchen, sobald ich nach Hause komme.
edit: ging nach Hause und probierte Sachen aus, das scheint für einfache Fälle ok zu sein
%Vor%einfacher als das, was ich dachte!
Ich bin mir nicht sicher, ob das per se "einfacher" ist, aber ich dachte, ich würde einen Ansatz teilen, den ich für die Implementierung von letfn für einen CPS-Transformator, den ich geschrieben habe, verwendete.
Der Schlüssel besteht darin, die Variablen einzuführen, aber die Zuweisung der Werte zu verzögern, bis sie alle im Gültigkeitsbereich sind. Was du eigentlich schreiben möchtest ist:
(let [f nil]
(set! f (memoize (fn []
<body-of-f>)))
(f))
Natürlich funktioniert das nicht wie es ist, weil let bindings in Clojure unveränderbar sind. Wir können das aber umgehen, indem wir einen Referenztyp verwenden - zum Beispiel ein promise :
(let [f (promise)]
(deliver! f (memoize (fn []
<body-of-f>)))
(@f))
Aber das ist noch zu kurz, denn wir müssen jede Instanz von f in <body-of-f> durch (deref f) ersetzen. Aber wir können dies lösen, indem wir eine andere Funktion einführen, die die im Versprechen gespeicherte Funktion aufruft. Die gesamte Lösung könnte also so aussehen:
(let [f* (promise)]
(letfn [(f []
(@f*))]
(deliver f* (memoize (fn []
<body-of-f>)))
(f)))
Wenn Sie eine Reihe von gegenseitig rekursiven Funktionen haben:
(let [f* (promise)
g* (promise)]
(letfn [(f []
(@f*))
(g []
(@g*))]
(deliver f* (memoize (fn []
(g))))
(deliver g* (memoize (fn []
(f))))
(f)))
Offensichtlich ist das eine Menge Kesselplatte. Aber es ist ziemlich trivial, ein Makro zu konstruieren, das Ihnen letfn -Stil -Syntax gibt.
Ja, es gibt einen einfacheren Weg. Es ist keine funktionale Transformation, sondern baut auf der in clojure erlaubten Verunreinigung auf.
%Vor% Der erste Schritt definiert fib fast normal, aber rekursive Aufrufe werden mit durchgeführt, unabhängig davon, welche Variable fib enthält . Dann wird fib neu definiert und wird zur Memo-Version seines alten Selbst.
Tags und Links clojure