How do I generate memoized recursive functions in Clojure?

Question

I'm trying to write a function that returns a memoized recursive function in Clojure, but I'm having trouble making the recursive function see its own memoized bindings. Is this because there is no var created? Also, why can't I use memoize on the local binding created with let?

This slightly unusual Fibonacci sequence maker that starts at a particular number is an example of what I wish I could do:

(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

Using with-local-vars seems like the right approach, but it doesn't work for me either. I guess I can't close over 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!?! 

I could of course manually write a macro that creates a closed-over atom and manage the memoization myself, but I was hoping to do this without such hackery.

Answer 1

This seems to work:

(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 only provides thread-local bindings for the newly created Vars, which are popped once execution leaves the with-local-vars form; hence the need for .bindRoot.

Answer 2

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

Answer 3

There is an interesting way to do it that does rely neither on rebinding nor the behavior of def. The main trick is to go around the limitations of recursion by passing a function as an argument to itself:

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

Then:

> ((make-fibo 1) 50)
12586269025

What happens here:

• The fib recursive function got a new argument mem-fib. This will be the memoized version of fib itself, once it gets defined.
• The fib body is wrapped in a let form that redefines calls to fib so that they pass the mem-fib down to next levels of recursion.
• mem-fib is defined as memoized fib
• ... and will be passed by partial as the first argument to itself to start the above mechanism.

This trick is similar to the one used by the Y combinator to calculate function's fix point in absence of a built-in recursion mechanism.

Given that def "sees" the symbol being defined, there is little practical reason to go this way, except maybe for creating anonymous in-place recursive memoized functions.

Answer 4

Here is the simplest solution:

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

Answer 5

You can encapsulate the recursive memoized function pattern in a macro if you plan to use it several times.

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

Answer 6

Your first version actually works, but you're not getting all the benefits of memoization because you're only running through the algorithm once.

Try this:

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]

Answer 7

Here's a cross between the Y-combinator and Clojure's 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))))))))

You can macrosugar this up:

(defmacro defrecfn [name args & body]
  `(def ~name
       (Y-mem (fn [foo#]
                 (fn ~args (let [~name foo#] ~@body))))))

Now for using it:

(defrecfn fib [n]
  (if (<= n 1)
      n
      (+' (fib (- n 1))
          (fib (- n 2)))))

user=> (time (fib 200))
"Elapsed time: 0.839868 msecs"
280571172992510140037611932413038677189525N

Or the Levenshtein distance:

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

Answer 8

You can generate memoized recursive functions in Clojure with a variant of the Y combinator. For instance, the code for factorial would be:

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

This is explained in details in this article about Y combinator real life application: recursive memoization in clojure.