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

Question

Estoy tratando de 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 poco inusual secuencia de Fibonacci que comienza en un número en particular es un ejemplo de lo que me gustarí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 

Usando with-local-vars parece que el enfoque correcto, pero no funciona para mí ya sea. ¿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!?! 

Podría, por supuesto, escribir manualmente una macro que crea un átomo-sobre cerrado y gestionar el memoization mí mismo, pero yo estaba esperando para hacer esto sin tal hackery.

Answer 1

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 sólo proporciona enlaces de subproceso local para el Vars nueva creación, que se metió una vez que la ejecución sale de la with-local-vars formar; de ahí la necesidad de .bindRoot.

Answer 2

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 3

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

Answer 4

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 5

Hay una interesante manera de hacerlo que no se basan ni en reencuadernación ni el comportamiento de def. El truco principal es dar la vuelta a las limitaciones de la recursividad haciendo pasar una función como 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))) 

continuación:

> ((make-fibo 1) 50) 
20365011074 

lo que sucede aquí:

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

Este truco es similar al usado por el combinador en 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 memorables recursivas en el lugar anónimas.

Answer 6

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

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

Answer 7

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

Usted puede macrosugar esto:

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

Ahora para el uso it:

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

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

O el 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

Puede generar memoized funciones recursivas 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 detalles en este artículo sobre Y combinator real life application: recursive memoization in clojure.