Well, a more important matter, this example in the documentation of
atom is wrong!
The recursive calls will not be memoized if called like that. Running
this code clearly shows:
(defn memoize [f]
(let [mem (atom {})]
(fn [& args]
(if-let [e (find @mem args)]
(val e)
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret)))))
(defn fib [n]
(if (<= n 1)
n
(+ (fib (dec n)) (fib (- n 2)))))
(time (fib 35))
user=> "Elapsed time: 1218.15834 msecs"
(def fib (memoize fib))
(time (fib 35))
user=> "Elapsed time: 953.94816 msecs"
I believe this is caused because defn creates a named fn:
user=> (macroexpand '(defn fib [n]
(if (<= n 1)
n
(+ (fib (dec n)) (fib (- n 2))))))
(def fib (.withMeta (clojure.core/fn fib ([n] (if (<= n 1) n (+ (fib
(dec n)) (fib (- n 2)))))) (.meta (var fib))))
So the recursive call don't go through the global user/fib that has
been memoized, but by the local fib which hasn't.
So a correct way to write it would be:
(defn fib [n]
(if (<= n 1)
n
(+ (user/fib (dec n)) (user/fib (- n 2)))))
(def fib (memoize fib))
(time (fib 35))
user=> "Elapsed time: 0.814599 msecs"
By fully qualifying the recursive call, it forces it to use the global
var, memoizing all the recursive calls.
This example should be corrected.
On Nov 12, 2:13 pm, Joseph Smith <[email protected]> wrote:
> In this case 'memoize' returns a memoized version of the function 'f', which
> closes over 'mem'. Each time 'memoize' is called a new atom is created, not
> each time the function it returns is called.
>
> ---
> Joseph Smith
> [email protected]
>
> On Nov 11, 2010, at 2:06 PM, Manoj wrote:
>
>
>
>
>
>
>
> > I am a newbie to Clojure, so have some confusion around lexical
> > scoping especially when "let" is used in a recursive function call. To
> > be more precise, I am taking the example memoize() function used for
> > explaining the concept of atom at clojure.org.
>
> > Here is how it is explained:
>
> > (defn memoize [f]
> > (let [mem (atom {})]
> > (fn [& args]
> > (if-let [e (find @mem args)]
> > (val e)
> > (let [ret (apply f args)]
> > (swap! mem assoc args ret)
> > ret)))))
>
> > (defn fib [n]
> > (if (<= n 1)
> > n
> > (+ (fib (dec n)) (fib (- n 2)))))
>
> > (time (fib 35))
> > user=> "Elapsed time: 941.445 msecs"
>
> > (def fib (memoize fib))
>
> > (time (fib 35))
>
> > user=> "Elapsed time: 0.044 msecs"
>
> > My question is when "let" is used in this context, wouldn't it create
> > a fresh binding to a new atom{}? Any explanation would be highly
> > appreciated.
>
> > Thanks.
>
> > --
> > 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
--
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
