如何在 Clojure 中生成记忆化递归函数? [英] How do I generate memoized recursive functions in Clojure?

问题描述

我正在尝试编写一个在 Clojure 中返回记忆化递归函数的函数，但是我无法让递归函数看到它自己的记忆化绑定.这是因为没有创建 var 吗?另外，为什么我不能在用 let 创建的本地绑定上使用 memoize?

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

使用 with-local-vars 似乎是正确的方法，但它对我也不起作用.我想我不能关闭 vars?

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.

推荐答案

这似乎有效:

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

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.

这篇关于如何在 Clojure 中生成记忆化递归函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！