Jak wygenerować zapamiętane funkcje rekurencyjne w Clojure?

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

Istnieje ciekawy sposób, aby to zrobić, który nie opiera się ani na rebindingu, ani na zachowaniu def. Główną sztuczką jest obejście ograniczeń rekursji poprzez przekazanie funkcji jako argumentu sobie:

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

Potem:

> ((make-fibo 1) 50)
20365011074

Co tu się dzieje:

• funkcja rekurencyjna otrzymała nowy argument mem-fib. Będzie to zapamiętana wersja fib, gdy zostanie zdefiniowana.
• ciało fib jest owinięte w formę let, która redefiniuje wywołania fib tak, że przechodzą mem-fib w dół do następnego poziomu rekurencji.
• mem-fib jest definiowane jako memoized fib
• ... i zostanie przekazany przez partial jako pierwszy argument do siebie, aby uruchomić powyższy mechanizm.

Ta sztuczka jest podobna do tej używanej przez kombinator Y do obliczania punktu stałego funkcji w przypadku braku wbudowanego mechanizmu rekurencyjnego.

Biorąc pod uwagę, że def "widzi" zdefiniowany symbol, nie ma praktycznego powodu, aby przejść do tego sposób, może poza tworzeniem anonimowych rekurencyjnych funkcji.

Oto najprostsze rozwiązanie:

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

Możesz zamknąć rekurencyjny, zapamiętany wzorzec funkcji w makrze, jeśli planujesz użyć go kilka razy.

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

Twoja pierwsza wersja faktycznie działa, ale nie otrzymujesz wszystkich korzyści z memoizacji, ponieważ używasz algorytmu tylko raz.

Spróbuj tego:

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]

Oto krzyżówka Y-combinator i 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))))))))

Możesz to makrosugar:

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

Teraz za użycie:

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

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

Lub odległość Levenshteina :

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

Możesz wygenerować zapamiętane funkcje rekurencyjne w Clojure z wariantem kombinatora Y. Na przykład, kod factorial brzmiałby:

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

Jest to szczegółowo wyjaśnione w tym artykule o Y combinator real life application: recursive memoization in clojure .