ज़िप्पर और एचओएफ की वजह से एक गंध (मुहावरेदार क्लोजर में) रिकर्सन है?

Question

क्लासिक किताब The Little Lisper (The Little Schemer) दो बड़े विचारों

पर आधारित है

1. आप (यह मानते हुए आप पूंछ कॉल अनुकूलन है)
2. लिस्प महान है (बजाय छोरों का उपयोग कर के) एक पुनरावर्ती रास्ते में सबसे समस्याओं को हल कर सकते हैं क्योंकि यह अपने आप में लागू करना आसान है।

अब कोई सोच सकता है कि यह सभी लिस्पी भाषाओं (क्लोजर समेत) के लिए सच है। मुसीबत यह है कि पुस्तक अपने समय (1 9 8 9) का एक आर्टेफैक्ट है, संभवतः Functional ProgrammingHigher Order Functions (एचओएफ) के साथ हमारे पास आज है। (या कम से कम स्नातक के लिए आकर्षक माना जाता था)।

रिकर्सन (कम से कम भाग में) का लाभ ('a 'b ('c ('d 'e))) जैसे नेस्टेड डेटा संरचनाओं के ट्रैवर्सल की आसानी है।

example के लिए:

(def leftmost 
    (fn [l] 
    (println "(leftmost " l) 
    (println (non-atom? l)) 
    (cond 
     (null? l) '() 
     (non-atom? (first l)) (leftmost (first l)) 
     true (first l)))) 

अब Functional Zippers साथ - हम नेस्ट डेटा संरचनाओं traversing करने के लिए एक गैर पुनरावर्ती दृष्टिकोण है, और उन्हें हम करेंगे किसी भी आलसी डेटा संरचना के रूप में पार कर सकते हैं। example के लिए:

(defn map-zipper [m] 
    (zip/zipper 
    (fn [x] (or (map? x) (map? (nth x 1)))) 
    (fn [x] (seq (if (map? x) x (nth x 1)))) 
    (fn [x children] 
     (if (map? x) 
     (into {} children) 
     (assoc x 1 (into {} children)))) 
    m)) 

(def m {:a 3 :b {:x true :y false} :c 4}) 

(-> (map-zipper m) zip/down zip/right zip/node) 
;;=> [:b {:y false, :x true}] 

अब यह आप के साथ किसी भी नेस्टेड सूची ट्रेवर्सल समस्या को हल कर सकते हैं लगता है या तो:

• एक zipper ऊपर के रूप में, या
• एक zipper कि संरचना चलता है और का एक सेट देता है कुंजी जो आपको assoc का उपयोग करके संरचना को संशोधित करने देगी।

अनुमान:

• मैं पाठ्यक्रम डेटा संरचनाओं की यह सोचते हैं रहा है कि निश्चित-आकार, और पूरी तरह से पूर्व में जाना जाता Traversal को
• मैं स्ट्रीमिंग का डेटा स्रोत परिदृश्य को छोड़कर कर रहा हूँ।

मेरा प्रश्न है: ज़िप्पर और एचओएफ की वजह से एक गंध (मुहावरेदार क्लोजर में) रिकर्सन है?

Answer 1

मैं कहूंगा कि, हाँ, यदि आप मैन्युअल रिकर्सन कर रहे हैं तो आपको कम से कम पुनर्विचार करना चाहिए कि आपको क्या चाहिए। लेकिन मैं यह नहीं कहूंगा कि ज़िप्पर के पास इसके साथ कुछ लेना देना है। ज़िप्पर के साथ मेरा अनुभव यह रहा है कि वे सैद्धांतिक उपयोग के हैं, और क्लोजर नवागंतुकों के लिए बहुत ही रोमांचक हैं, लेकिन चीजों की लटकने के बाद थोड़ा व्यावहारिक मूल्य है, क्योंकि जिन स्थितियों में वे उपयोगी हैं वे दुर्लभ हैं।

यह वास्तव में उच्च-आदेश कार्यों के कारण है जो आपके लिए पहले से ही सामान्य पुनरावर्ती पैटर्न लागू कर चुके हैं कि मैन्युअल रिकर्सन असामान्य है। हालांकि, यह निश्चित रूप से ऐसा नहीं है कि आपको कभी भी मैन्युअल रिकर्सन का उपयोग नहीं करना चाहिए: यह केवल एक चेतावनी संकेत है, जो सुझाव देता है कि आप कुछ और करने में सक्षम हो सकते हैं। मैं क्लोजर का उपयोग करने के अपने चार वर्षों में एक परिस्थिति को भी याद नहीं कर सकता हूं कि मुझे वास्तव में एक जिपर की आवश्यकता है, लेकिन मैं अक्सर रिकर्सन का उपयोग करके समाप्त होता हूं।

Answer 2

क्लोजर मुहावरे स्पष्ट रिकर्सन को हतोत्साहित करते हैं क्योंकि कॉल स्टैक सीमित है: आम तौर पर लगभग 10 के गहरे तक। में संशोधन Halloway & bedra के छह Clojure कार्यात्मक प्रोग्रामिंग (Programming Clojure (पी 89)) के नियम के पहले,

बचें असीम प्रत्यावर्तन। JVM रिकर्सिव कॉल और क्लोजर प्रोग्राम अनुकूलित नहीं कर सकता है जो पर बाध्य किए बिना क्लोजर प्रोग्राम को अपना स्टैक उड़ाएगा।पूंछ प्रत्यावर्तन के साथ

• recur सौदों:

राहत दिला के एक जोड़े हैं।

आलसी अनुक्रम एक उथल-पुथल डेटा संरचना में एक उथले कॉल स्टैक
में एक गहरी कॉल स्टैक को बदल सकता है। अनुक्रम में कई एचओएफ
लाइब्रेरी, जैसे map और filter, ऐसा करें।