क्लोजर

Question

में संरचनात्मक साझाकरण मैं क्लोजर में संरचनात्मक साझाकरण के बारे में अस्पष्ट हूं। नीचे जॉय ऑफ़ क्लोजर (ग्रेट बुक बीटीडब्ल्यू) से लिया गया एक फ़ंक्शन xconj है।

;;Building a naive binary search tree using recursion 
(defn xconj [t v] 
     (cond 
      (nil? t) {:val v :L nil :R nil} 
      (< v (:val t)) {:val (:val t) :L (xconj (:L t) v) :R (:R t)} 
      :else {:val (:val t) :L (:L t) :R (xconj (:R t) v)})) 

यदि कोई नीचे दिखाए गए दो पेड़ टी 1 और टी 2 को परिभाषित करता है।

(def t1 (xconj (xconj (xconj nil 5) 3) 2)) 
(def t2 (xconj t1 7)) 

यह स्पष्ट है कि वाम सबट्री t1 & t2

user> (identical? (:L t1) (:L t2)) 
true 

द्वारा साझा किया जाता लेकिन एक, एक नया पेड़ t3 बनाने के लिए बाईं सबट्री में एक नया मान '1' डालने से थे t1, इस तरह की:

(def t3 (xconj t1 1)) 

एक पूरी तरह से नया पेड़ में इस परिणाम के साथ सभी मूल्यों की नकल की होगी और कोई संरचनात्मक साझा करने, या कुछ संरचना अभी भी साझा किया जाएगा? क्या होगा यदि बाएं शाखा बड़ी थी 2-> 3-> 4-> 5-> 6-> 7 (* रूट) और 1 बाएं उपट्री में डाली गई थी, तो संरचना के कुछ साझाकरण जारी रहेगा?

Answer 1

जगह है जहाँ नया मान सम्मिलित करने के लिए बदल दिया जाएगा है के पथ पर नोड्स, लेकिन कम से कम दो बातें एक पूरी कहानी पाने के लिए सूचना के लिए चाहिए देखते हैं:

1. की जगह एक ऑपरेशन के दौरान गैर-nil नोड इसके उप-नियमों और उसके मूल्य को संरक्षित करता है; केवल एक subtree बाहर swapped है। (यदि आप "बाएं, बाएं, बाएं" पथ के साथ नोड्स को प्रतिस्थापित करते हैं, तो "बाएं, बाएं, दाएं" स्थिति पर नोड साझा किया जा रहा है।) इस प्रकार बहुत सारी संरचना संभावित रूप से साझा की जा सकती है भले ही सभी नोड्स पत्तियों में से एक के लिए पथ बदल दिया गया है।

2. नोड्स को प्रतिस्थापित किया जा रहा है नक्शे हैं। अगर वे सिर्फ तीन चाबियाँ से बड़े थे, यह भावना के बजाय नए नक्शे के निर्माण के assoc/assoc-in/update-in उपयोग करने के लिए होगा:

   ... 
   (< v (:val t)) (update-in t [:L] xconj v) 
   ... 
   

   नए नोड नक्शे से वर्ष नोड नक्शे के साथ संरचना साझा करने के लिए सक्षम होगा। अद्यतन-इन/Assoc में सुझाव के लिए