如何在Clojure中生成记忆recursion函数？
我试图编写一个函数，返回在Clojure memoizedrecursion函数，但我有困难使recursion函数看到自己的memoized绑定。 这是因为没有创buildvar？ 另外，为什么我不能使用let创build的本地绑定使用memoize？
这个稍微不寻常的斐波那契序列制造商，从一个特定的数字开始，是我希望我能做的一个例子：
(defn make-fibo [y] (memoize (fn fib [x] (if (< x 2) y (+ (fib (- x 1)) (fib (- x 2))))))) (let [f (make-fibo 1)] (f 35)) ;; SLOW, not actually memoized 使用with-local-vars似乎是正确的方法，但它也不适用于我。 我想我不能closuresvars？
(defn make-fibo [y] (with-local-vars [fib (fn [x] (if (< x 2) y (+ (@fib (- x 1)) (@fib (- x 2)))))] (memoize fib))) (let [f (make-fibo 1)] (f 35)) ;; Var null/null is unbound!?!
我当然可以手动编写一个macros，创build一个闭合的primefaces，并自己pipe理memoization，但我希望能做到这一点没有这样的hackery。
这似乎工作：
(defn make-fibo [y] (with-local-vars [fib (memoize (fn [x] (if (< x 2) y (+ (fib (- x 2)) (fib (dec x))))))] (.bindRoot fib @fib) @fib))
with-local-vars只为新创build的Vars提供线程本地绑定，一旦执行离开with-local-vars表单，popup该Vars。 因此需要.bindRoot 。
(def fib (memoize (fn [x] (if (< x 2) x (+ (fib (- x 1)) (fib (- x 2))))))) (time (fib 35))
有一种有趣的方式，既不依赖重新绑定，也不依赖于def的行为。 主要的技巧是通过将函数作为parameter passing给自身来解决recursion的限制：
(defn make-fibo [y] (let [fib (fn [mem-fib x] (let [fib (fn [a] (mem-fib mem-fib a))] (if (<= x 1) y (+ (fib (- x 1)) (fib (- x 2)))))) mem-fib (memoize fib)] (partial mem-fib mem-fib)))
然后：
> ((make-fibo 1) 50) 20365011074
这里发生了什么：
-
fibrecursion函数有一个新的参数mem-fib。 一旦它被定义，这将是fib本身的memoized版本。 -
fib主体被包装成letforms，重新定义了对fib调用，以便它们将mem-fib传递给下一级recursion。 -
mem-fib被定义为memoizedfib - …并将
partial作为第一个parameter passing给自己，以启动上述机制。
这个技巧类似于Y combinator用于在没有内置recursion机制的情况下计算函数的固定点的技巧。
鉴于def “看见”被定义的符号，除了创build匿名就地recursionmemoized函数外，没有什么实际的理由去这样做。
这是最简单的解决scheme：
(def fibo (memoize (fn [n] (if (< n 2) n (+ (fibo (dec n)) (fibo (dec (dec n))))))))
如果您计划多次使用，可以将recursionmemoized函数模式封装在一个macros中。
(defmacro defmemo [name & fdecl] `(def ~name (memoize (fn ~fdecl))))
你的第一个版本实际上可行，但是你没有得到memoization的所有好处，因为你只运行一次algorithm。
尝试这个：
user> (time (let [f (make-fibo 1)] (f 35))) "Elapsed time: 1317.64842 msecs" 14930352 user> (time (let [f (make-fibo 1)] [(f 35) (f 35)])) "Elapsed time: 1345.585041 msecs" [14930352 14930352]
这是Y-combinator和Clojure的memoize之间的交叉：
(defn Y-mem [f] (let [mem (atom {})] (#(% %) (fn [x] (f #(if-let [e (find @mem %&)] (val e) (let [ret (apply (xx) %&)] (swap! mem assoc %& ret) ret))))))))
你可以macros观上这个：
(defmacro defrecfn [name args & body] `(def ~name (Y-mem (fn [foo#] (fn ~args (let [~name foo#] ~@body))))))
现在使用它：
(defrecfn fib [n] (if (<= n 1) n (+' (fib (- n 1)) (fib (- n 2))))) user=> (time (fib 200)) "Elapsed time: 0.839868 msecs" 280571172992510140037611932413038677189525N
或Levenshtein距离 ：
(defrecfn edit-dist [s1 s2] (cond (empty? s1) (count s2) (empty? s2) (count s1) :else (min (inc (edit-dist s1 (butlast s2))) (inc (edit-dist (butlast s1) s2)) ((if (= (last s1) (last s2)) identity inc) (edit-dist (butlast s1) (butlast s2))))))
您可以在Clojure中使用Y组合器的变体生成memoizedrecursion函数。 例如， factorial的代码是：
(def Ywrap (fn [wrapper-func f] ((fn [x] (xx)) (fn [x] (f (wrapper-func (fn [y] ((xx) y)))))))) (defn memo-wrapper-generator [] (let [hist (atom {})] (fn [f] (fn [y] (if (find @hist y) (@hist y) (let [res (fy)] (swap! hist assoc y res) res)))))) (def Ymemo (fn [f] (Ywrap (memo-wrapper-generator) f))) (def factorial-gen (fn [func] (fn [n] (println n) (if (zero? n) 1 (* n (func (dec n))))))) (def factorial-memo (Ymemo factorial-gen))
在这篇关于Y combinator实际应用的文章中详细解释了这个：clojure中的recursion记忆 。
