Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursion inside let function

I'm confused as to how def and let bind variables differently. Can someone explain to me why this works:

(def leven
  (memoize
   (fn [x y]
     (cond (empty? x) (count y)
           (empty? y) (count x)
           :else (min (+ (leven (rest x) y) 1)
                      (+ (leven x (rest y)) 1)
                      (+ (leven (rest x) (rest y)) (if (= (first x) (first y)) 0 1)))))))

But when I try to declare the function as let it fails to compile:

(def leven
  (let [l (memoize (fn [x y]
                     (cond (empty? x) (count y)
                           (empty? y) (count x)
                           :else (min (+ (l (rest x) y) 1)
                                      (+ (l x (rest y)) 1)
                                      (+ (l (rest x) (rest y)) (if (= (first x) (first y)) 0 1))))))]
    (l x y)))

EDIT: This works, using the technique showed by Ankur.

(defn leven [x y]
  (let [l (memoize (fn [f x y]
                     (cond (empty? x) (count y)
                           (empty? y) (count x)
                           :else (min (+ (f f (rest x) y) 1)
                                      (+ (f f x (rest y)) 1)
                                      (+ (f f (rest x) (rest y)) (if (= (first x) (first y)) 0 1))))))
        magic (partial l l)]
    (magic x y)))
like image 977
onit Avatar asked Oct 18 '12 12:10

onit


2 Answers

Below is such an example to do what you have asked for. I am using factorial just for the sake of simplicity and added println in factorial to make sure the memoization is working fine

(let [fact (memoize (fn [f x] 
                       (println (str "Called for " x))
                       (if (<= x 1) 1 (* x  (f f (- x 1))))))
      magic (partial fact fact)] 
     (magic 10)
     (magic 11))

First calculate factorial of 10 and then 11 in which case it should not again call factorial for 10 till 1 as that has been memoized.

Called for 10
Called for 9
Called for 8
Called for 7
Called for 6
Called for 5
Called for 4
Called for 3
Called for 2
Called for 1
Called for 11
39916800
like image 80
Ankur Avatar answered Sep 28 '22 00:09

Ankur


The let form binds names sequentially so in your second function definition the name l doesn't exist when you try to refer to it. You can either use letfn (with some minor mods) or give the defined function a name and instead refer to that instead, like so:

(def leven  
  (let [l (memoize (fn SOME-NAME [x y]
    (cond 
      (empty? x) (count y)
      (empty? y) (count x)
      :else (min (+ (SOME-NAME (rest x) y) 1)
                 (+ (SOME-NAME x (rest y)) 1)
                 (+ (SOME-NAME (rest x) (rest y)) (if (= (first x) (first y)) 0 1))))))]
l))

As you might notice I change the return from the let to be l itself since that is what you want leven bound to. The (l x y) was problematic because it referred to bindings only local to the function and not accessible to the let.

like image 39
fogus Avatar answered Sep 28 '22 01:09

fogus