Как создать memoized рекурсивные функции в Clojure?

Я пытаюсь написать функцию, которая возвращает memoized рекурсивную функцию в Clojure, но у меня возникают проблемы с тем, чтобы рекурсивная функция отображала свои собственные memoized привязки. Это потому, что не создано 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!?!

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

Ответ 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.

Ответ 2

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

Ответ 3

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

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

     (partial mem-fib mem-fib)))

Тогда:

> ((make-fibo 1) 50)
12586269025

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

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

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

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

Ответ 4

Вот простейшее решение:

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

Ответ 5

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

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

Ответ 6

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

Попробуйте следующее:

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]

Ответ 7

Здесь находится крест между Y-combinator и Clojure 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))))))))

Вы можете сделать макросагар:

(defmacro defrecfn [name args & body]
  `(def ~name
       (Y-mem (fn [foo#]
                 (fn ~args (let [~name foo#] [email protected]))))))

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

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

Ответ 8

Вы можете генерировать memoized рекурсивные функции в Clojure с вариантом Y combinator. Например, код для 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 combinator приложении реального времени: рекурсивная memoization в clojure.