如何在Clojure中生成memoized递归函数？

Question

我正在尝试编写一个在Clojure中返回memoized递归函数的函数,但是我在使递归函数看到它自己的memoized绑定时遇到了麻烦.这是因为没有创建var吗？另外,为什么我不能在用let创建的本地绑定上使用memoize？

这个稍微不同寻常的Fibonacci序列制作者从一个特定的数字开始就是我希望我能做的一个例子:

(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似乎是正确的方法,但它对我也不起作用.我想我不能关闭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!?! 

我当然可以手动编写一个宏来创建一个封闭的原子并自己管理memoization,但我希望没有这样的hackery这样做.

Answer 1

这似乎有效:

(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只为新创建的Vars提供线程局部绑定,一旦执行离开with-local-vars表单就弹出; 因此需要.bindRoot.

Answer 2

(def fib (memoize (fn [x] (if (< x 2)
                              x
                              (+ (fib (- x 1))
                                 (fib (- x 2)))))))
(time (fib 35))

Answer 3

有一种有趣的方法,既不依赖于重新绑定也不依赖于行为def.主要技巧是通过将函数作为参数传递给自身来绕过递归的限制:

(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)))

然后:

> ((make-fibo 1) 50)
12586269025

这里发生了什么:

• 该fib递归函数有一个新的论点mem-fib.fib一旦定义,这将是自身的记忆版本.
• 将fib身体包裹在一个let重新定义调用的形式fib,让他们传递mem-fib到递归的下一个水平.
• mem-fib 被定义为memoized fib
• ......并将partial作为第一个参数传递给自己以启动上述机制.

这个技巧类似于Y组合器在没有内置递归机制的情况下计算函数的定点的技巧.

鉴于def"看到"正在定义的符号,除了可能用于创建匿名就地递归memoized函数之外,没有什么实际的理由去这种方式.