क्या रिकर्सिव चलो एफएन को याद करने का कोई आसान तरीका है?

Question

मान लीजिए कि आप एक पुनरावर्ती समारोह एक लेट ब्लॉक में परिभाषित करते हैं:

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

यह यंत्रवत् memoize उपयोग करने के लिए परिवर्तित किया जा सकता:

1. लपेटें memoize के लिए एक कॉल में fn प्रपत्र।
2. फ़ंक्शन नाम को पहले तर्क के रूप में ले जाएं।
3. जहां भी इसे कहा जाता है, फ़ंक्शन को अपने आप पास करें।
4. partial का उपयोग करके फ़ंक्शन प्रतीक को रीबंड करें।

उपरोक्त कोड को बदलने के लिए सुराग के लिए:

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

यह काम करता है, लेकिन बहुत ज्यादा जटिल लगता है। सवाल यह है: क्या कोई आसान तरीका है?

Answer 1

मैं जवाब देने में जोखिम लेता हूं क्योंकि मैं विद्वान नहीं हूं लेकिन मुझे ऐसा नहीं लगता है। आपने मानक चीज को काफी हद तक सही किया है जो ठीक से एक निश्चित बिंदु संयोजक के माध्यम से ज्ञापन का आंशिक अनुप्रयोग है।

आप मैक्रोज़ के साथ परेशान करने का प्रयास कर सकते हैं (सरल मामलों के लिए यह आसान हो सकता है, वाक्यविन्यास-उद्धरण आपके लिए नाम समाधान करेगा और आप उस पर काम कर सकते हैं)। घर आने के बाद मैं कोशिश करूंगा।

संपादित करें: वापस घर चला गया और सामान बाहर करने की कोशिश की, इस साधारण मामलों

(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 

मैं क्या सोचा से अधिक आसान के लिए ठीक-ish हो रहा है!

Answer 2

मुझे यकीन नहीं है कि यह प्रति "सरल" है, लेकिन मैंने सोचा कि मैं एक सीपीएस ट्रांसफार्मर के लिए letfn को दोबारा लागू करने के लिए एक दृष्टिकोण साझा करूंगा।

कुंजी को लागू करने की कुंजी है, लेकिन जब तक वे सभी दायरे में नहीं हैं तब तक उन्हें मान निर्दिष्ट करने में देरी हो रही है। असल में, क्या आप लिखने के लिए चाहते हैं:

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

बेशक यह इसी रूप में काम नहीं करता है, क्योंकि let बाइंडिंग Clojure में अडिग हैं।

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

लेकिन यह अभी भी कम पड़ता है, क्योंकि हम (deref f) साथ <body-of-f> में f के प्रत्येक उदाहरण बदलना होगा: उदाहरण के लिए, एक promise - हम, कुछ मिल सकता है, हालांकि, एक संदर्भ प्रकार का उपयोग करके। लेकिन हम इसे एक और समारोह शुरू करके हल कर सकते हैं जो वादे में संग्रहीत समारोह को आमंत्रित करता है।तो पूरे समाधान इस प्रकार दिखाई देंगे:

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

आप परस्पर पुनरावर्ती कार्यों का एक सेट है, तो:

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

जाहिर है कि बॉयलर-प्लेट की एक बहुत कुछ है। लेकिन यह एक मैक्रो बनाने के लिए बहुत छोटा है जो आपको letfn -स्टाइल वाक्यविन्यास देता है।