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

Question

Я пытаюсь написать функцию, которая возвращает 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!?! 

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

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 обеспечивает только внутрипотоковые привязки для вновь созданного Варса, которые хлопнутые когда выполнение покидает with-local-vars форма; следовательно, необходимо, чтобы .bindRoot.

Answer 2

Ваша первая версия на самом деле работает, но вы не получаете всех преимуществ 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] 

Answer 3

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

Answer 4

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

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

Answer 5

Существует интересный способ сделать это, что делает полагаться ни на перепривязки, ни поведение 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. Это будет memoized версия fib себя, как только она будет определена.
• Корпус fib обернут в форму let, которая переопределяет вызовы fib, чтобы они передавали mem-fib до следующих уровней рекурсии.
• mem-fib определяется как memoized fib
• ... и будет принят partial как первый аргумент сам по себе, чтобы начать выше механизма.

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

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

Answer 6

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

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

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

Вы можете macrosugar это вверх:

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

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

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

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

Или Levenshtein distance:

(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

Вы можете генерировать 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 real life application: recursive memoization in clojure.