Is there an easier way to memoize recursive let fn?

Question

Say you have a recursive function defined in a let block:

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

This can be mechanically converted to use memoize :

• Wrap the fn form when calling memoize .
• Move the function name as the first argument.
• Pass the function to yourself wherever it is called.
• Cancel the function symbol in the same way using partial .

Converting the above code results in:

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

It works, but feels too complicated. The question is, is there an easier way?

Answer 1

I risk answering because I'm not a scientist, but I don’t think so. You pretty much did the standard thing, which in order is a partial application of memoization through a fixed-point combinator.

You could try messing with macros, though (for simple cases this can be easy, the syntax quote will give name resolution for you, and you can work on that). I will try when I get home.

edit: got home and tried stuff, it looks like 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 (fx)))))) ((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 

easier than i thought!

Answer 2

I'm not sure if this is “simpler” as such, but I thought I'd share the approach I took to re-implement letfn for the CPS transformer I wrote.

The key is to enter the variables, but the delay assigns the values ​​until they are included in the scope. Basically, you would like to write:

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

Of course, this does not work as it is, because let bindings are immutable in Clojure. However, we can get around this using a reference type - for example, promise :

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

But this still doesn't work, because we have to replace each instance of f with <body-of-f> with (deref f) . But we can solve this by introducing another function that calls the function stored in the promise. So the whole 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, a lot of boiler stove. But it's pretty hard to create a macro that gives you the letfn syntax.