可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
I'm trying to write a function that returns a memoized recursive function in Clojure, but I'm having trouble making the recursive function see its own memoized bindings. Is this because there is no var created? Also, why can't I use memoize on the local binding created with let?
This slightly unusual Fibonacci sequence maker that starts at a particular number is an example of what I wish I could do:
(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
Using with-local-vars
seems like the right approach, but it doesn't work for me either. I guess I can't close over vars?
(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!?!
I could of course manually write a macro that creates a closed-over atom and manage the memoization myself, but I was hoping to do this without such hackery.
回答1:
This seems to work:
(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
only provides thread-local bindings for the newly created Vars, which are popped once execution leaves the with-local-vars
form; hence the need for .bindRoot
.
回答2:
There is an interesting way to do it that does rely neither on rebinding nor the behavior of def
. The main trick is to go around the limitations of recursion by passing a function as an argument to itself:
(defn make-fibo [y]
(let
[fib
(fn [mem-fib x]
(let [fib (fn [a] (mem-fib mem-fib a))]
(if (<= x 2)
y
(+ (fib (- x 1)) (fib (- x 2))))))
mem-fib (memoize fib)]
(partial mem-fib mem-fib)))
Then:
> ((make-fibo 1) 50)
12586269025
What happens here:
- The
fib
recursive function got a new argument mem-fib
. This will be the memoized version of fib
itself, once it gets defined.
- The
fib
body is wrapped in a let
form that redefines calls to fib
so that they pass the mem-fib
down to next levels of recursion.
mem-fib
is defined as memoized fib
- ... and will be passed by
partial
as the first argument to itself to start the above mechanism.
This trick is similar to the one used by the Y combinator to calculate function's fix point in absence of a built-in recursion mechanism.
Given that def
"sees" the symbol being defined, there is little practical reason to go this way, except maybe for creating anonymous in-place recursive memoized functions.
回答3:
(def fib (memoize (fn [x] (if (< x 2)
x
(+ (fib (- x 1))
(fib (- x 2)))))))
(time (fib 35))
回答4:
Here is the simplest solution:
(def fibo
(memoize (fn [n]
(if (< n 2)
n
(+ (fibo (dec n))
(fibo (dec (dec n))))))))
回答5:
You can encapsulate the recursive memoized function pattern in a macro if you plan to use it several times.
(defmacro defmemo
[name & fdecl]
`(def ~name
(memoize (fn ~fdecl))))
回答6:
Your first version actually works, but you're not getting all the benefits of memoization because you're only running through the algorithm once.
Try this:
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]
回答7:
Here's a cross between the Y-combinator and Clojure's memoize
:
(defn Y-mem [f]
(let [mem (atom {})]
(#(% %)
(fn [x]
(f #(if-let [e (find @mem %&)]
(val e)
(let [ret (apply (x x) %&)]
(swap! mem assoc %& ret)
ret))))))))
You can macrosugar this up:
(defmacro defrecfn [name args & body]
`(def ~name
(Y-mem (fn [foo#]
(fn ~args (let [~name foo#] ~@body))))))
Now for using it:
(defrecfn fib [n]
(if (<= n 1)
n
(+' (fib (- n 1))
(fib (- n 2)))))
user=> (time (fib 200))
"Elapsed time: 0.839868 msecs"
280571172992510140037611932413038677189525N
Or the Levenshtein distance:
(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))))))
回答8:
You can generate memoized recursive functions in Clojure with a variant of the Y combinator. For instance, the code for factorial
would be:
(def Ywrap
(fn [wrapper-func f]
((fn [x]
(x x))
(fn [x]
(f (wrapper-func (fn [y]
((x x) y))))))))
(defn memo-wrapper-generator []
(let [hist (atom {})]
(fn [f]
(fn [y]
(if (find @hist y)
(@hist y)
(let [res (f y)]
(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))
This is explained in details in this article about Y combinator real life application: recursive memoization in clojure.