clojure - 有没有更简单的方法来记住递归 let fn？

Question

假设您在 let block 中定义了一个递归函数:

(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 重新绑定(bind)函数符号以执行相同的操作。

转换上面的代码会导致:

(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

比我想象的要简单!