क्लोजर जिपर कार्यान्वयन ह्यूट के जिपर से विभिन्न प्रकार और डेटा संरचनाओं का उपयोग क्यों करता है?

Question

मैं Huet's original paper की तुलना Clojure's implementation के साथ कर रहा हूं और यह पता लगाने की कोशिश कर रहा हूं कि परिवर्तन क्यों किए गए थे। मैं क्लोजर नौसिखिया हूं, इसलिए यदि मैं क्लोजर कोड की अपनी व्याख्या पर गलत हूं, तो कृपया मुझे सही करें।

ह्यूएट के पेपर में, पथ का प्रकार (ओकैम में) Top | Node of tree list * path * tree list;; है। क्लोजर में, दो अतिरिक्त फ़ील्ड हैं, pnodes और changed?। इन क्षेत्रों का उद्देश्य क्या है? क्या मुझे विश्वास है कि l और r ह्यूएट के प्रकार में पहली और तीसरी प्रविष्टियों के अनुरूप है, और ppath दूसरा है?

ह्यूएट का जिपर पूरे लिंक्ड सूचियों का उपयोग करता है (ध्यान दें कि मैं लोक प्रकार के बारे में बात कर रहा हूं, न कि जिपर ऑपरेटिंग डेटा संरचना नहीं), जबकि कुछ स्थानों पर, उदाहरण के लिए l, क्लोजर कार्यान्वयन वैक्टर का उपयोग करता है। परिवर्तन क्यों, और क्लोजर कार्यान्वयन की समय जटिलता के लिए क्या प्रभाव है?

Answer 1

सबसे पहले, l, r और ppath की आपकी समझ सही है।

pnodes और changed? एक अनुकूलन के रूप में एक साथ काम: जब तुम जाओ up अगर changed? गलत है तो आप pnodes से नोड बल्कि वर्तमान नोड और छोड़ दिया और सही भाई बहन सूची से यह पुनर्निर्माण की तुलना में पॉप।

l के लिए वेक्टर के उपयोग के लिए और r के लिए एक सूची के रूप में। फिर यह एक नोड पुनर्निर्माण की लागत के बारे में है। ह्यूएट के पेपर में (rev left) @ (t::right) है जो ओ (एनएबी) है जहां बाएं बाएं आकार का है। क्लोजर में हमारे पास (concat l (cons node r)) है जो ओ (1) [1] है क्योंकि l वेक्टर होने की आवश्यकता नहीं है (क्लोजर में वैक्टरों को किसी भी दिशा में कुशलतापूर्वक घुमाया जा सकता है लेकिन केवल दाईं ओर संलग्न हो सकता है)।

[1] ठीक है यह केवल निर्माण समय पर ओ (1) है: nleft conses को आलसी रूप से आवंटित किया जाएगा क्योंकि परिणामी अनुक्रम आगे गणना द्वारा उपभोग किया जाता है।