Как генерировать запомненные рекурсивные функции в Clojure?

Question

Я пытаюсь написать функцию, которая возвращает запомненную рекурсивную функцию в Clojure, но мне не удается заставить рекурсивную функцию видеть свои собственные запомненные привязки. Это потому, что там нет созданного var? Кроме того, почему я не могу использовать memoize для локальной привязки, созданной с помощью let?

Этот немного необычный создатель последовательности Фибоначчи, который начинается с определенного числа, является примером того, что я хотел бы сделать:

(defn make-fibo [y]
  (memoize (fn fib [x] (if (< x 2)
             y
             (+ (fib (- x 1))
                (fib (- x 2)))))))

(let [f (make-fibo 1)]
  (f 35)) ;; SLOW, not actually memoized

Использование with-local-vars кажется правильным подходом, но он также не работает для меня. Я полагаю, я не могу закрыть переменную?

(defn make-fibo [y]
  (with-local-vars [fib (fn [x] (if (< x 2)
                                  y
                                  (+ (@fib (- x 1))
                                     (@fib (- x 2)))))]
    (memoize fib)))

(let [f (make-fibo 1)]
  (f 35)) ;; Var null/null is unbound!?! 

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

Answer 1

Это похоже на работу:

(defn make-fibo [y]
  (with-local-vars
      [fib (memoize
            (fn [x]
              (if (< x 2)
                y
                (+ (fib (- x 2)) (fib (dec x))))))]
    (.bindRoot fib @fib)
    @fib))

with-local-vars предоставляет только локальные привязки потоков для вновь созданных Vars, которые появляются после того, как выполнение покидает форму with-local-vars; отсюда необходимость .bindRoot.

Answer 2

(def fib (memoize (fn [x] (if (< x 2)
                              x
                              (+ (fib (- x 1))
                                 (fib (- x 2)))))))
(time (fib 35))

Answer 3

Существует интересный способ сделать это, который не зависит ни от привязки, ни от поведения def. Основной трюк - обойти ограничения рекурсии, передав функцию в качестве аргумента самому себе:

(defn make-fibo [y]
  (let
    [fib
      (fn [mem-fib x]
         (let [fib (fn [a] (mem-fib mem-fib a))]
           (if (<= x 1)
             y
             (+ (fib (- x 1)) (fib (- x 2))))))
     mem-fib (memoize fib)]

     (partial mem-fib mem-fib)))

Тогда:

> ((make-fibo 1) 50)
20365011074

Что здесь происходит:

• Рекурсивная функция fib получила новый аргумент mem-fib. Это будет запомненная версия самого fib, как только она будет определена.
• Тело fib обернуто в форму let, которая переопределяет вызовы на fib, чтобы они передавали mem-fib на следующие уровни рекурсии.
• mem-fib определяется как запомненный fib
• ... и будет передан partial в качестве первого аргумента самому себе для запуска вышеуказанного механизма.

Этот прием аналогичен тому, который используется комбинатором Y для вычисления точки фиксации функции в отсутствие встроенного механизма рекурсии.

Учитывая, что def "видит" определяемый символ, практически нет практических причин для этого, за исключением, возможно, создания анонимных рекурсивных запоминаемых функций на месте.

Answer 4

Вот самое простое решение:

(def fibo
  (memoize (fn [n]
             (if (< n 2)
               n
               (+ (fibo (dec n))
                  (fibo (dec (dec n))))))))

Answer 5

Вы можете инкапсулировать шаблон рекурсивной запомненной функции в макрос, если планируете использовать его несколько раз.

(defmacro defmemo
  [name & fdecl]
  `(def ~name
     (memoize (fn ~fdecl))))

Answer 6

Вы можете генерировать запомненные рекурсивные функции в Clojure с вариантом Y-комбинатора.Например, код для factorial будет выглядеть следующим образом:

(def Ywrap
  (fn [wrapper-func f]
    ((fn [x]
       (x x))
     (fn [x]
       (f (wrapper-func (fn [y]
                      ((x x) y))))))))

 (defn memo-wrapper-generator [] 
   (let [hist (atom {})]
    (fn [f]
      (fn [y]
        (if (find @hist y)
          (@hist y)
         (let [res (f y)]
           (swap! hist assoc y res)
        res))))))

(def Ymemo 
  (fn [f]
   (Ywrap (memo-wrapper-generator) f)))

(def factorial-gen
  (fn [func]
    (fn [n]
      (println n)
     (if (zero? n)
      1
      (* n (func (dec n)))))))

(def factorial-memo (Ymemo factorial-gen))

Это подробно объясняется в этой статье о реальном приложении комбинатора Y: рекурсивное запоминание в clojure .

Answer 7

Вот что-то среднее между Y-комбинатором и Clojure's memoize:

(defn Y-mem [f]
  (let [mem (atom {})]
    (#(% %)
     (fn [x]
       (f #(if-let [e (find @mem %&)]
            (val e)
            (let [ret (apply (x x) %&)]
              (swap! mem assoc %& ret)
              ret))))))))

Вы можете макросахарировать это:

Теперь для его использования:

(defrecfn fib [n]
  (if (<= n 1)
      n
      (+' (fib (- n 1))
          (fib (- n 2)))))

user=> (time (fib 200))
"Elapsed time: 0.839868 msecs"
280571172992510140037611932413038677189525N

Или Расстояние Левенштейна :

(defrecfn edit-dist [s1 s2]
  (cond (empty? s1) (count s2)
        (empty? s2) (count s1)
        :else (min (inc (edit-dist s1 (butlast s2)))
                   (inc (edit-dist (butlast s1) s2))
                   ((if (= (last s1) (last s2)) identity inc)
                      (edit-dist (butlast s1) (butlast s2))))))

Answer 8

Ваша первая версия на самом деле работает, но вы не получаете всех преимуществ запоминания, потому что вы выполняете алгоритм только один раз.

Попробуйте это:

user>  (time (let [f (make-fibo 1)]
          (f 35)))
"Elapsed time: 1317.64842 msecs"
14930352

user>  (time (let [f (make-fibo 1)]
          [(f 35) (f 35)]))
"Elapsed time: 1345.585041 msecs"
[14930352 14930352]