C'è un modo più semplice per memoizzare un let fn ricorsivo?

Question

Diciamo che si dispone di una funzione ricorsiva definita in un blocco let:

(let [fib (fn fib [n] 
      (if (< n 2) 
       n 
       (+ (fib (- n 1)) 
       (fib (- n 2)))))] 
    (fib 42)) 

Questo può essere trasformato meccanicamente di utilizzare memoize:

1. Wrap forma fn in una chiamata a memoize.
2. Sposta il nome della funzione come primo argomento.
3. Passa la funzione in se stessa ovunque venga chiamata.
4. Ricollegare il simbolo della funzione per fare lo stesso utilizzando partial.

Trasformare il codice di cui sopra porta a:

(let [fib (memoize 
      (fn [fib n] 
       (if (< n 2) 
       n 
       (+ (fib fib (- n 1)) 
        (fib fib (- n 2)))))) 
     fib (partial fib fib)] 
    (fib 42)) 

Questo funziona, ma si sente troppo complicato. La domanda è: c'è un modo più semplice?

Answer 1

Ho dei rischi nel rispondere poiché non sono uno studioso ma non la penso così. Hai praticamente fatto la cosa standard che in fine è un'applicazione parziale della memoizzazione attraverso un combinatore a virgola fissa.

Si potrebbe provare a giocherellare con i macro però (per i casi semplici potrebbe essere facile, la sintassi-preventivo farebbe la risoluzione dei nomi per voi e potreste operare su quello). Ci proverò una volta tornato a casa.

edit: tornò a casa e ha cercato fuori roba, questo sembra essere ok-ish per i casi semplici

(defmacro memoize-rec [form] 
    (let [[fn* fname params & body] form 
     params-with-fname (vec (cons fname params))] 
    `(let [f# (memoize (fn ~params-with-fname 
         (let [~fname (partial ~fname ~fname)] ~@body)))] 
     (partial f# f#)))) 

;; (clojure.pprint/pprint (macroexpand '(memoize-rec (fn f [x] (str (f x)))))) 
((memoize-rec (fn fib [n] 
       (if (< n 2) 
        n 
        (+ (fib (- n 1)) 
        (fib (- n 2)))))) 75) ;; instant 

((fn fib [n] 
       (if (< n 2) 
        n 
        (+ (fib (- n 1)) 
        (fib (- n 2))))) 75) ;; slooooooow 

più semplice di quello che ho pensato!

Answer 2

Non sono sicuro che questo sia "più semplice" di per sé, ma ho pensato di condividere un approccio che ho preso per ri-implementare letfn per un trasformatore CPS che ho scritto.

La chiave è introdurre le variabili, ma ritardare l'assegnazione dei valori finché non sono tutti nell'ambito. Fondamentalmente, ciò che si desidera scrivere è:

(let [f nil] (set! f (memoize (fn [] <body-of-f>))) (f))

Naturalmente questo non funziona come è, perché let attacchi sono immutabili in Clojure. Siamo in grado di andare in giro che, però, utilizzando un tipo di riferimento - ad esempio, un promise:

(let [f (promise)] (deliver! f (memoize (fn [] <body-of-f>))) (@f))

Ma questo cade ancora breve, perché dobbiamo sostituire ogni istanza di f in <body-of-f> con (deref f). Ma possiamo risolvere questo problema introducendo un'altra funzione che richiama la funzione memorizzata nella promessa.Così l'intera soluzione potrebbe essere simile a questo:

(let [f* (promise)] (letfn [(f [] (@f*))] (deliver f* (memoize (fn [] <body-of-f>))) (f)))

Se si dispone di un insieme di funzioni ricorsive reciprocamente:

(let [f* (promise) g* (promise)] (letfn [(f [] (@f*)) (g [] (@g*))] (deliver f* (memoize (fn [] (g)))) (deliver g* (memoize (fn [] (f)))) (f)))

Ovviamente questo è un sacco di caldaia-piastra. Ma è piuttosto semplice costruire una macro che ti dia la sintassi in stile letfn.