Comment générer des fonctions récursives mémorisées en Clojure ?

Question

J'essaie d'écrire une fonction qui renvoie une fonction récursive mémorisée en Clojure, mais j'ai du mal à faire en sorte que la fonction récursive voie ses propres liaisons mémorisées. Est-ce parce qu'il n'y a pas de var créé ? De même, pourquoi ne puis-je pas utiliser memoize sur la liaison locale créée avec let ?

Ce fabricant de séquences de Fibonacci légèrement inhabituelles qui commencent à un nombre particulier est un exemple de ce que j'aimerais pouvoir faire :

(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

Utilisation de with-local-vars semble être la bonne approche, mais ça ne marche pas pour moi non plus. Je suppose que je ne peux pas fermer sur les variables ?

(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!?! 

Je pourrais bien sûr écrire manuellement une macro qui crée un atome fermé et gérer moi-même la mémorisation, mais j'espérais pouvoir le faire sans avoir à recourir à de tels artifices.

Answer 1

Il existe un moyen intéressant de le faire, qui ne repose ni sur la réaffectation ni sur le comportement de la fonction def . L'astuce principale consiste à contourner les limites de la récursion en passant une fonction en argument à elle-même :

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

Ensuite :

> ((make-fibo 1) 50)
20365011074

Ce qui se passe ici :

• Le site fib La fonction récursive a reçu un nouvel argument mem-fib . Ce sera la version mémorisée de fib lui-même, une fois qu'il est défini.
• Le site fib est enveloppé dans un let qui redéfinit les appels à fib afin qu'ils passent le mem-fib jusqu'aux niveaux suivants de récurrence.
• mem-fib est défini comme mémorisé fib
• ... et sera adopté par partial comme premier argument à lui-même pour lancer le mécanisme ci-dessus.

Cette astuce est similaire à celle utilisée par le combinateur Y pour calculer le point fixe de la fonction en l'absence d'un mécanisme de récursion intégré.

Étant donné que def "voit le symbole en cours de définition, il y a peu de raisons pratiques d'utiliser cette méthode, sauf peut-être pour créer des fonctions anonymes récursives mémorisées sur place.

Answer 2

Cela semble fonctionner :

(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 ne fournit que des liaisons thread-local pour les Vars nouvellement créés, qui sont supprimés une fois que l'exécution quitte le processus d'exécution. with-local-vars d'où la nécessité de .bindRoot .

Answer 3

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

Answer 4

Voici la solution la plus simple :

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

Answer 5

Vous pouvez encapsuler le modèle de fonction récursive mémorisée dans une macro si vous prévoyez de l'utiliser plusieurs fois.

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