I was playing with "memoize" when I ran into some puzzling behavior. A test
case:
(defn f [n]
(println "f called with" n)
(if (zero? n)
0
(min (f (dec n))
(f (dec n)))))
(def f (memoize f))
*The usage of "def" to rebind a function to its memoized version is taken
from Programming Clojure.
The output when I call f with 2:
user=> (f 2)
f called with 2
f called with 1
f called with 0
f called with 0
f called with 1
f called with 0
f called with 0
0
Since f is memoized, my expectation was that I would see "f called with 2",
"f called with 1", "f called with 0" each printed just once. Instead, it's
as though I didn't memoize f at all. I know I did, because if I call f with
2 again, I get 0 back right away.
user=> (f 2)
0
This leads me to the second issue: Having evaluated (f 2), I assumed that
the results for (f 2), (f 1), and (f 0) are all now available for immediate
retrieval. If I call (f 3), I thought I would only see "f called with 3"
printed and then the result. Instead, this is what I saw:
user=> (f 3)
f called with 3
f called with 2
f called with 1
f called with 0
f called with 0
f called with 1
f called with 0
f called with 0
f called with 2
f called with 1
f called with 0
f called with 0
f called with 1
f called with 0
f called with 0
0
It's as though the recursive calls go to the unmemoized version of the
function instead of the memoized one.
I did find a way to get the expected behavior:
(def g
(memoize
(fn [n]
(println "g called with" n)
(if (zero? n)
0
(min (g (dec n))
(g (dec n)))))))
user=> (g 2)
g called with 2
g called with 1
g called with 0
0
user=> (g 3)
g called with 3
0
Up until now, I assumed the first formulation would work with recursive
functions as well. Was that incorrect? Is something like the second
formulation the only way to memoize recursive functions?
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
