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

问题描述

我试图写一个函数，返回一个记忆的递归函数在Clojure，但我有麻烦让递归函数看到自己的记忆绑定。这是因为没有var创建？此外，为什么我不能在使用let创建的本地绑定上使用memoize？

这个稍微不寻常的斐波那契序列生成器从一个特定的数字开始是一个例子希望我能做到：

 （defn make-fibo [y] 
（memnize（fn fib [x] if（< x 2）
y 
（+（fib（ -  x 1））
（fib（ -  x 2））））））
 
 （let [f（make-fibo 1）] 
（f 35））;; SLOW，不实际记忆
  

使用 with-local-vars 似乎是正确的方法，但它不适用于我。我想我不能关闭vars？

 （defn make-fibo [y] 
 -vars [fib（fn [x]（if（< x 2）
y 
（+（@fib（ -  x 1））
（@fib ））] 
（memoize fib）））
 
（let [f（make-fibo 1）] 
（f 35） Var null / null是unbound！？！ 
 

我当然可以手动编写一个宏来创建一个封闭原子，并自己管理memoization，但我希望没有这样的黑客做到这一点。

解决方案

这似乎有效：

 （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 。

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.

解决方案

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.

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