Is there a simpler way to memoize a recursive let fn?

I'm not sure this is "simpler" per se, but I thought I'd share an approach I took to re-implement letfn for a CPS transformer I wrote.

The key is to introduce the variables, but delay assigning them values until they are all in scope. Basically, what you would like to write is:

(let [f nil] (set! f (memoize (fn [] <body-of-f>))) (f))

Of course this doesn't work as is, because let bindings are immutable in Clojure. We can get around that, though, by using a reference type — for example, a promise:

(let [f (promise)] (deliver! f (memoize (fn [] <body-of-f>))) (@f))

But this still falls short, because we must replace every instance of f in <body-of-f> with (deref f). But we can solve this by introducing another function that invokes the function stored in the promise. So the entire solution might look like this:

(let [f* (promise)] (letfn [(f [] (@f*))] (deliver f* (memoize (fn [] <body-of-f>))) (f)))

If you have a set of mutually-recursive functions:

(let [f* (promise) g* (promise)] (letfn [(f [] (@f*)) (g [] (@g*))] (deliver f* (memoize (fn [] (g)))) (deliver g* (memoize (fn [] (f)))) (f)))

Obviously that's a lot of boiler-plate. But it's pretty trivial to construct a macro that gives you letfn-style syntax.

I take risks in answering since I am not a scholar but I don't think so. You pretty much did the standard thing which in fine is a partial application of memoization through a fixed point combinator.

You could try to fiddle with macros though (for simple cases it could be easy, syntax-quote would do name resolution for you and you could operate on that). I'll try once I get home.

edit: went back home and tried out stuff, this seems to be ok-ish for simple cases

(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

simpler than what i thought!

Yes, there is a simpler way. It is not a functional transformation, but builds on the impurity allowed in clojure.

(defn fib [n]
  (if (< n 2)
    n
    (+ (#'fib (- n 1))
       (#'fib (- n 2)))))

(def fib (memoize fib))

First step defines fib in almost the normal way, but recursive calls are made using whatever the var fib contains. Then fib is redefined, becoming the memoized version of its old self.