recursion - variable - ¿Cómo puedo generar funciones recursivas memorizadas en Clojure?

groovy when then

Question

Intento escribir una función que devuelva una función recursiva memorable en Clojure, pero estoy teniendo problemas para que la función recursiva vea sus propios enlaces memorados. ¿Esto es porque no hay var creada? Además, ¿por qué no puedo usar memoize en el enlace local creado con let?

Este fabricante de secuencias de Fibonacci ligeramente inusual que comienza en un número particular es un ejemplo de lo que desearía poder hacer:

(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

Usar with-local-vars parece ser el enfoque correcto, pero tampoco funciona para mí. ¿Supongo que no puedo cerrar sobre 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!?! 

Por supuesto, podría escribir manualmente una macro que crea un átomo cerrado y gestionar la memoria yo mismo, pero esperaba hacer esto sin tal piratería.

Answer 1

Aquí está la solución más simple:

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

Answer 2

Aquí hay un cruce entre el Y-combinator 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))))))))

Puede macrosugar esto:

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

Ahora para usarlo:

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

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

O la distancia Levenshtein :

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

Esto parece funcionar:

(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 solo proporciona enlaces locales de subprocesos para los Vars recién creados, que se abren una vez que la ejecución abandona el formulario with-local-vars ; de ahí la necesidad de .bindRoot .

Answer 4

Hay una forma interesante de hacerlo que no depende ni de la reconsolidación ni del comportamiento de def . El truco principal es sortear las limitaciones de la recursión pasando una función como un argumento a sí mismo:

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

Entonces:

> ((make-fibo 1) 50)
20365011074

Qué pasa aquí:

• La función recursiva fib obtuvo un nuevo argumento mem-fib . Esta será la versión memorable de fib , una vez que se define.
• El cuerpo fib está envuelto en una forma let que redefine las llamadas a fib para que pasen la mem-fib a los siguientes niveles de recursión.
• mem-fib se define como fib memoria
• ... y se aprobará por partial como el primer argumento en sí mismo para iniciar el mecanismo anterior.

Este truco es similar al utilizado por el combinador Y para calcular el punto fijo de la función en ausencia de un mecanismo de recursión incorporado.

Dado que def "ve" que se está definiendo el símbolo, hay pocas razones prácticas para ir por este camino, excepto tal vez para crear funciones recordadas recursivas en el lugar anónimas.

Answer 5

Puede encapsular el patrón de función recursivo memorizado en una macro si planea usarlo varias veces.

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

Answer 6

Puede generar funciones recursivas memorizadas en Clojure con una variante del combinador Y. Por ejemplo, el código para factorial sería:

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

Esto se explica en detalle en este artículo sobre la aplicación de la vida real Y combinator: memoria recursiva en clojure .

Answer 7

Su primera versión realmente funciona, pero no obtiene todos los beneficios de la memorización porque solo está ejecutando el algoritmo una vez.

Prueba esto:

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 8

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