有没有更简单的方法来记忆递归let fn？

Question

假设你有一个let块中定义的递归函数:

(let [fib (fn fib [n]
            (if (< n 2)
              n
              (+ (fib (- n 1))
                 (fib (- n 2)))))]
  (fib 42))

这可以通过机械方式转换为利用memoize:

1. fn在打电话中包裹表格memoize.
2. 将函数名称作为第一个参数移动.
3. 无论在何处调用函数,都将函数传递给自己.
4. 重新绑定功能符号以使用相同的功能partial.

转换上面的代码会导致:

(let [fib (memoize
            (fn [fib n]
              (if (< n 2)
                n
                (+ (fib fib (- n 1))
                   (fib fib (- n 2))))))
      fib (partial fib fib)]
  (fib 42))

这有效,但感觉过于复杂.问题是:有更简单的方法吗？

Answer 1

由于我不是学者，所以我冒险回答，但我不这么认为。您几乎完成了标准的事情，好的事情是通过定点组合器对备忘录进行部分应用。

但是，您可以尝试摆弄宏（在简单的情况下可能很容易，语法引号将为您进行名称解析，您可以对此进行操作）。我一回到家就尝试。

编辑：回到家并尝试了一些东西，对于简单的情况，这似乎还可以

(defmacro memoize-rec [form]
  (let [[fn* fname params & body] form
        params-with-fname (vec (cons fname params))]
    `(let [f# (memoize (fn ~params-with-fname
                         (let [~fname (partial ~fname ~fname)] ~@body)))]
       (partial f# f#))))

;; (clojure.pprint/pprint (macroexpand '(memoize-rec (fn f [x] (str (f x))))))
((memoize-rec (fn fib [n]
                (if (< n 2)
                  n
                  (+ (fib (- n 1))
                     (fib (- n 2)))))) 75) ;; instant

((fn fib [n]
                (if (< n 2)
                  n
                  (+ (fib (- n 1))
                     (fib (- n 2))))) 75) ;; slooooooow

比我想的要简单！