;Simple example
(defn fib1 [n]
(if (or (= 0 n) (= 1 n))
1
(+ (fib1 (- n 1))
(fib1 (- n 2)))))
(defn-memo fib2 [n]
(if (or (= 0 n) (= 1 n))
1
(+ (fib2 (- n 1))
(fib2 (- n 2)))))
;workaround for this problem
(declare aux-fib)
(defn-memo fib3 [n]
(if (or (= 0 n) (= 1 n))
1
(+ (aux-fib (- n 1))
(aux-fib (- n 2)))))
(def aux-fib fib3)
(time (fib1 35))
"Elapsed time: 4729.9318 msecs"
14930352
=> (time (fib2 35))
"Elapsed time: 4727.70348 msecs"
14930352
=> (time (fib3 35))
"Elapsed time: 0.875 msecs"
14930352
The recursive call inside fib2 is not memoized because of the way
Clojure expands defn, adding the function name to the generated fn.
So, how to rewrite defn-memo so that fib2 behaves like fib3? It would
be much easier to make defn stop adding the function name to the fn,
but that makes normal recursive functions a little slower, and would
change the behaviour if dynamic scoping was being used in a program.
The problem is that if you change defn-memo so that it doesn't use
defn, you lose all of defn goodness or have to reproduce all of defn's
work inside of defn-memo. Memoization of recursive functions is very
useful, with problems that are normally solved with dynamic program
becoming much simpler and functional when used. Any idea on how to
rewrite defn-memo so that it does the right thing?
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
