recursion - 如何在 Clojure 中生成记忆递归函数？

Question

我正在尝试编写一个在 Clojure 中返回记忆递归函数的函数，但我无法让递归函数看到它自己的记忆绑定。这是因为没有创建 var 吗？另外，为什么我不能在用 let 创建的本地绑定上使用 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似乎是正确的方法，但它对我也不起作用。我想我不能关闭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!?!

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

score 21 · Accepted Answer

有一种有趣的方法可以做到这一点，它既不依赖于重新绑定也不依赖于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被定义为记忆fib
...并将partial作为第一个参数传递给自身以启动上述机制。

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

鉴于def“看到”正在定义的符号，几乎没有实际理由这样做，除非可能是为了创建匿名的就地递归记忆函数。

score 19 · Accepted Answer

这似乎有效：

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

score 18 · Accepted Answer

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

score 3 · Accepted Answer

这是最简单的解决方案：

(def fibo
  (memoize (fn [n]
             (if (< n 2)
               n
               (+ (fibo (dec n))
                  (fibo (dec (dec n))))))))

score 2 · Accepted Answer

如果您打算多次使用它，您可以将递归记忆函数模式封装在一个宏中。

(defmacro defmemo
  [name & fdecl]
  `(def ~name
     (memoize (fn ~fdecl))))

score 1 · Accepted Answer

这是Y-combinator和 Clojure之间的交叉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))))))))

您可以对此进行宏糖化：

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

score 0 · Accepted Answer

您的第一个版本确实有效，但您并没有获得记忆化的所有好处，因为您只运行了一次算法。

尝试这个：

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]

score 0 · Accepted Answer

您可以使用 Y 组合器的变体在 Clojure 中生成记忆递归函数。例如，代码为factorial：

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

这在这篇关于Y 组合器现实生活应用的文章中有详细解释：clojure 中的递归记忆。

recursion - 如何在 Clojure 中生成记忆递归函数？

8 回答 8

Related

Reference