Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(require '(clojure [zip :as zip]))
(defn memoize-calls
"Takes an expression, and replaces calls to func with cache checks, and calls
if cache is missing."
([func cache expr] (memoize-calls func cache expr (zip/seq-zip expr)))
([func cache expr pos]
(if (zip/end? pos) (zip/root pos) ; if at the end, return the tree.
(if (and (= func (zip/node pos))
(empty? (zip/lefts pos)))
;; replace function call with if-let cache check expression
(let [args (zip/rights pos)
call (-> pos zip/up zip/node)
retval (gensym)
pos ;; write over pos with new expression
(-> pos zip/up
(zip/replace
`(if-let [~retval (get-in (deref ~cache) [~@args])]
~retval
(let [~retval (~func ~@args)]
(swap! ~cache assoc-in [~@args] ~retval)
~retval))))]
(recur func cache expr (zip/next pos))) ; keep traversing
;; if not at a function call, keep traversing (DFS)
(recur func cache expr (zip/next pos))))))
(defmacro defn-memo-rec
"Replaces recursion with memoization checks"
[name args expr]
(let [cache (gensym)
new-expr (memoize-calls name cache expr)]
`(let [~cache (atom {})]
(defn ~name ~args
~new-expr))))
(defn-memo-rec
fib [n]
(if (<= n 1) 1
(+ (fib (dec n))
(fib (- n 2)))))
(time (fib 1000))
;; "Elapsed time: 52.709875 msecs"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.