जैसा कि मैंने पाया, हास्केल में चर अपरिवर्तनीय हैं (इस प्रकार, वे वास्तव में 'चर' नहीं हैं)।हास्केल में जटिल डेटा संरचनाएं - वे कैसे काम करते हैं?
इस मामले में, यदि हमारे पास एक लाल और काले पेड़ की तरह एक जटिल और बड़ी डेटा संरचना है, तो हम वास्तव में डेटा संरचना को बदलने वाले संचालन को कैसे कार्यान्वित करना चाहते हैं?
हर बार तत्व को डालने या हटाए जाने पर पेड़ की एक प्रति बनाएं?
हां, समाधान एक नई डेटा संरचना को वापस करना है जो संशोधित मूल्य का प्रतिनिधित्व करता है, हालांकि आपके उदाहरण (लाल-काले पेड़) के लिए पूरी संरचना की प्रतिलिपि बनाने की कोई आवश्यकता नहीं है क्योंकि आप पथ पर नोड्स की प्रतिलिपि बना सकते हैं रूट से डाले गए नोड तक। यह डालने का ऑपरेशन अनिवार्य संस्करण के समान जटिलता होने की अनुमति देता है।
क्रिस ओकासाकी के Purely functional data structures अपरिवर्तनीय डेटा संरचनाओं के कार्यान्वयन के एक नंबर शामिल हैं - इस पुस्तक है जो आप को कॉपी करने के बारे में here
और ओकासाकी की पुस्तक से परे जाने के लिए: [ओकासाकी के बाद पूरी तरह से कार्यात्मक डेटा संरचनाओं में नया क्या है?] (Http://cstheory.stackexchange.com/questions/ 1539/व्हाट्स-न्यू-इन-विशुद्ध रूप से-कार्यात्मक-डेटा-संरचनाएं-से-ओकासाकी) – Gilles
पीएचडी थीसिस एक मृत लिंक है। – fuz
@FUZxxl: ऐसा लगता है कि citeseerx.ist.psu.edu कुछ कारणों से नीचे है, आइए आशा करते हैं कि यह वापस आ जाएगा। –
अपने अंतर्ज्ञान पा सकते हैं अपनी पीएचडी थीसिस का एक संशोधित संस्करण बिल्कुल सही दिशा आप सोच किया जाना चाहिए है। हालांकि, 'कॉपीिंग' बुद्धिमानी से हास्केल रनटाइम द्वारा कार्यान्वित किया गया। उदाहरण के लिए,
data Tree = Empty | Branch Tree Integer Tree
दिया आप बाईं शाखा को बदलने के लिए एक समारोह को लागू कर सकते हैं:
replaceLeft :: Tree -> Tree -> Tree
replaceLeft (Branch _ i r) newLeft = Branch newLeft i r
नतीजा यह है कि आप नए पेड़ की एक पूरी प्रतिलिपि बनाने के रूप में है कि नहीं है नहीं है ज़रूरी। मूल्य i और पेड़ r और newLeft अपरिवर्तित हैं इसलिए हमें अपनी सामग्री को ताजा स्मृति में कॉपी करने की आवश्यकता नहीं है।
नई Branch कि बनाई गई है (यह इस उदाहरण में केवल वास्तविक आवंटन है: संरचना Integer पर बाईं/सही पेड़ धारण करने के लिए के निर्माण) अभी भी संदर्भ देता पुराने शाखा से ठीक उसी मान, कोई नकल जरूरत है!
चूंकि डेटा संरचनाएं अपरिवर्तनीय हैं, इसलिए ऐसा करने में कोई हानि नहीं है।
मुझे अपरिवर्तनीयता पर ध्यान देना पसंद है: यह बिल्कुल अपरिवर्तनीयता है जो हमें प्राप्त करने की अनुमति देती है यह साझा करना – luqui
"इस प्रकार, वे वास्तव में \ 'चर' नहीं हैं" - निश्चित रूप से वे हैं। उदाहरण के लिए, जब एक गणितज्ञ कहता है "चलो * जी * समूह (* एस *, \ *) हो, जहां ...", * जी * एक चर है, भले ही यह कभी नहीं बदलेगा। हास्केल में यह वही सिद्धांत है। –
आप निश्चित रूप से एक दिलचस्प बिंदु उठाते हैं, वास्तव में संरचना प्रदर्शन को बलि किए बिना अपरिवर्तनीयता को समायोजित करने के लिए थोड़ा सा बदलती है। एक उन्मुख ग्राफ के रूप में अपनी संरचना के बारे में सोचें (जहां ए से बी के किनारे का अर्थ है कि ए को संदर्भ/सूचकांक बी है), फिर यदि आप बी को बदलना चाहते हैं, तो किसी भी वर्टेक्स से बी को सुलभ करने की आवश्यकता है और इसका संदर्भ अपडेट किया गया है । मुझे अभी भी पता नहीं है कि हास्केल में एक Skip सूची का प्रतिनिधित्व कैसे करें उदाहरण के लिए :) –