recursion рекурсивные Рекурсия внутри функции let



postgresql рекурсивный запрос (2)

Я смущен относительно того, как def и пусть связывают переменные по-разному. Может кто-нибудь объяснить мне, почему это работает:

(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))
              )
  )))
)

Но когда я пытаюсь объявить эту функцию так, чтобы она не скомпилировалась:

(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: Это работает, используя технику, показанную 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)
)
)

Answer #1

Ниже приведен пример того, что вы просили. Я использую factorial только для простоты и добавил println в factorial, чтобы убедиться, что memoization работает нормально

(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))

Сначала вычислите факториал 10, а затем 11, и в этом случае он не должен снова обращаться к факториалу в течение 10 до 1, поскольку это было запомнено.

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

Answer #2

Форма let связывает имена последовательно, поэтому в вашем втором определении функции имя l не существует, когда вы пытаетесь обратиться к нему. Вы можете использовать letfn (с некоторыми незначительными модификациями) или дать определенной функции имя и вместо этого ссылаться на это, например:

(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))

Как вы могли заметить, я меняю возврат с let на l так как это то, что вы хотите связать с leven . (lxy) была проблематичной, поскольку она ссылалась только на привязки, только локальные к функции и не доступные для let .





let