Purely functional data structure
कंप्यूटर विज्ञान में, विशुद्ध रूप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे विशुद्ध रूप से कार्यात्मक भाषा में सीधे लागू किया जा सकता है। एक मनमाना डेटा संरचना और विशुद्ध रूप से कार्यात्मक संरचना के बीच मुख्य अंतर यह है कि बाद वाला (दृढ़ता से) अपरिवर्तनीय है। यह प्रतिबंध यह सुनिश्चित करता है कि डेटा संरचना में अपरिवर्तनीय वस्तुओं के लाभ हैंः (पूर्ण) दृढ़ता, वस्तुओं की त्वरित प्रतिलिपि, और धागे की सुरक्षा। कुशल विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं के लिए आलसी मूल्यांकन और ज्ञापन के उपयोग की आवश्यकता हो सकती है। परिभाषा निरंतर डेटा संरचनाओं में अपने पिछले संस्करणों को अपरिवर्तित रखने का गुण होता है। दूसरी ओर, सरणी जैसी संरचनाएँ एक विनाशकारी अद्यतन को स्वीकार करती हैं, यानी एक अद्यतन जिसे उलट नहीं किया जा सकता है। एक बार जब कोई प्रोग्राम सरणी के कुछ सूचकांक में एक मान लिख देता है, तो उसका पिछला मान अब पुनः प्राप्त नहीं किया जा सकता है। औपचारिक रूप से, एक विशुद्ध रूप से कार्यात्मक डेटा संरचना एक डेटा संरचना है जिसे विशुद्ध रूप से कार्यात्मक भाषा में लागू किया जा सकता है, जैसे कि हास्केल। व्यवहार में, इसका मतलब है कि डेटा संरचनाओं का निर्माण केवल स्थायी डेटा संरचनाओं जैसे कि टुपल्स, सम प्रकार, उत्पाद प्रकार और मूल प्रकार जैसे पूर्णांक, वर्ण, स्ट्रिंग्स का उपयोग करके किया जाना चाहिए। इस तरह की डेटा संरचना अनिवार्य रूप से स्थायी है। हालाँकि, सभी स्थायी डेटा संरचनाएँ विशुद्ध रूप से कार्यात्मक नहीं हैं। उदाहरण के लिए, एक स्थायी सरणी एक डेटा-संरचना है जो स्थायी है और जिसे एक सरणी का उपयोग करके लागू किया जाता है, इस प्रकार यह विशुद्ध रूप से कार्यात्मक नहीं है। विशुद्ध रूप से कार्यात्मक डेटा संरचना पुस्तक में, ओकासाकी ने विनाशकारी अद्यतनों की तुलना मास्टर शेफ के चाकू से की है। विनाशकारी अद्यतनों को पूर्ववत नहीं किया जा सकता है, और इस प्रकार उनका उपयोग तब तक नहीं किया जाना चाहिए जब तक कि यह सुनिश्चित न हो कि पिछले मूल्य की अब आवश्यकता नहीं है। हालांकि, विनाशकारी अद्यतन भी दक्षता की अनुमति दे सकते हैं जिसे अन्य तकनीकों का उपयोग करके प्राप्त नहीं किया जा सकता है। उदाहरण के लिए, एक सरणी और विनाशकारी अद्यतन का उपयोग करने वाली एक डेटा संरचना को एक समान डेटा संरचना द्वारा प्रतिस्थापित किया जा सकता है जहां सरणी को एक मानचित्र, एक यादृच्छिक पहुंच सूची या एक संतुलित वृक्ष द्वारा प्रतिस्थापित किया जाता है, जो विशुद्ध रूप से कार्यात्मक कार्यान्वयन को स्वीकार करता है। लेकिन अभिगम लागत स्थिर समय से लघुगणक समय तक बढ़ सकती है। यह सुनिश्चित करना कि एक डेटा संरचना विशुद्ध रूप से कार्यात्मक है एक डेटा संरचना कभी भी स्वाभाविक रूप से कार्यात्मक नहीं होती है। उदाहरण के लिए, एक स्टैक को एकल-लिंक्ड सूची के रूप में लागू किया जा सकता है। यह कार्यान्वयन विशुद्ध रूप से तब तक कार्यात्मक है जब तक कि स्टैक पर एकमात्र संचालन पुराने स्टैक को बदले बिना एक नया स्टैक वापस करता है। हालाँकि, यदि भाषा विशुद्ध रूप से कार्यात्मक नहीं है, तो रन-टाइम प्रणाली अपरिवर्तनीयता की गारंटी देने में असमर्थ हो सकती है। यह ओकासाकी द्वारा सचित्र है, जहाँ वह दिखाता है कि दो एकल-जुड़ी सूचियों का संयोजन अभी भी एक अनिवार्य सेटिंग का उपयोग करके किया जा सकता है। यह सुनिश्चित करने के लिए कि एक डेटा संरचना का उपयोग विशुद्ध रूप से कार्यात्मक तरीके से एक अशुद्ध कार्यात्मक भाषा में किया जाता है, मॉड्यूल या वर्गों का उपयोग केवल अधिकृत कार्यों के माध्यम से हेरफेर सुनिश्चित करने के लिए किया जा सकता है। विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करना विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए मौजूदा कोड को अनुकूलित करने में केंद्रीय चुनौतियों में से एक इस तथ्य में निहित है कि परिवर्तनीय डेटा संरचनाएं उन कार्यों के लिए "छिपे हुए आउटपुट" प्रदान करती हैं जो उनका उपयोग करते हैं। विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं का उपयोग करने के लिए इन कार्यों को फिर से लिखने के लिए इन डेटा संरचनाओं को स्पष्ट आउटपुट के रूप में जोड़ने की आवश्यकता होती है। उदाहरण के लिए, एक ऐसे फ़ंक्शन पर विचार करें जो एक परिवर्तनशील सूची को स्वीकार करता है, सूची से पहले तत्व को हटा देता है, और उस तत्व को वापस कर देता है। विशुद्ध रूप से कार्यात्मक सेटिंग में, सूची से एक तत्व को हटाने से एक नई और छोटी सूची बनती है, लेकिन मूल सूची को अद्यतन नहीं किया जाता है। उपयोगी होने के लिए, इसलिए, इस फ़ंक्शन के एक विशुद्ध रूप से कार्यात्मक संस्करण को हटाए गए तत्व के साथ नई सूची को वापस करने की संभावना है। सबसे सामान्य मामले में, इस तरह से परिवर्तित एक प्रोग्राम को प्रत्येक फ़ंक्शन कॉल से अतिरिक्त परिणाम के रूप में प्रोग्राम के "स्टेट" या "स्टोर" को वापस करना होगा। कहा जाता है कि इस तरह के कार्यक्रम को स्टोर-पासिंग शैली में लिखा जाता है। विशुद्ध रूप से कार्यात्मक कार्यान्वयन के साथ अमूर्त डेटा संरचनाओं की सूची यहां दी गई हैः एकल रूप से जुड़ी सूची के रूप में कार्यान्वित स्टैक (पहले, अंत में), कतार, वास्तविक समय में कतार के रूप में कार्यान्वित, दोहरे अंत वाली कतार, वास्तविक समय में दोहरे अंत वाली कतार के रूप में कार्यान्वित, (बहु) क्रमबद्ध तत्वों का समूह और आदेशित कुंजियों द्वारा अनुक्रमित मानचित्र, लाल-काले पेड़ के रूप में कार्यान्वित, या अधिक आम तौर पर एक खोज पेड़ द्वारा, प्राथमिकता कतार, एक ब्रोडल कतार यादृच्छिक उपयोग सूची के रूप में कार्यान्वित, एक तिरछी-द्विआधारी यादृच्छिक उपयोग सूची के रूप में कार्यान्वित हैश कॉन्सिग ज़िपर (डेटा संरचना) डिजाइन और कार्यान्वयन अपनी पुस्तक विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं में, कंप्यूटर वैज्ञानिक क्रिस ओकासाकी विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं को डिजाइन और कार्यान्वित करने के लिए उपयोग की जाने वाली तकनीकों का वर्णन करते हैं। आलसी मूल्यांकन विशुद्ध रूप से कार्यात्मक भाषा में विशेष रूप से दिलचस्प है क्योंकि मूल्यांकन का क्रम कभी भी किसी कार्य के परिणाम को नहीं बदलता है। इसलिए, आलसी मूल्यांकन स्वाभाविक रूप से विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं के निर्माण का एक महत्वपूर्ण हिस्सा बन जाता है। यह एक गणना को केवल तभी करने की अनुमति देता है जब इसका परिणाम वास्तव में आवश्यक हो। इसलिए, विशुद्ध रूप से कार्यात्मक डेटा संरचना का कोड, दक्षता के नुकसान के बिना, उसी तरह के डेटा पर विचार कर सकता है जिसका प्रभावी रूप से उपयोग किया जाएगा और डेटा जिसे अनदेखा किया जाएगा। एकमात्र गणना की आवश्यकता पहले प्रकार के डेटा के लिए है; यही वह है जो वास्तव में किया जाएगा। कुशल, विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं के निर्माण में प्रमुख उपकरणों में से एक ज्ञापन है। जब गणना की जाती है, तो इसे सहेजा जाता है और इसे दूसरी बार करने की आवश्यकता नहीं होती है। आलसी कार्यान्वयन में यह विशेष रूप से महत्वपूर्ण है; अतिरिक्त मूल्यांकन के लिए समान परिणाम की आवश्यकता हो सकती है, लेकिन यह जानना असंभव है कि किस मूल्यांकन के लिए पहले इसकी आवश्यकता होगी। कुछ डेटा संरचनाएँ, यहां तक कि वे जो विशुद्ध रूप से कार्यात्मक नहीं हैं जैसे कि गतिशील सरणी, ऐसे संचालन को स्वीकार करते हैं जो अधिकांश समय कुशल होते हैं (जैसे, गतिशील सरणी के लिए निरंतर समय), और शायद ही कभी अक्षम (जैसे, गतिशील सरणी के लिए रैखिक समय)। परिशोधन का उपयोग तब यह साबित करने के लिए किया जा सकता है कि संचालन का औसत चलने का समय कुशल है। कहने का मतलब है, कुछ अक्षम संचालन काफी दुर्लभ हैं, और संचालन के एक क्रम पर विचार करने पर समय जटिलता के स्पर्शोन्मुख विकास को नहीं बदलते हैं। सामान्य तौर पर, लगातार डेटा संरचनाओं के लिए अक्षम संचालन स्वीकार्य नहीं है, क्योंकि इसी संचालन को कई बार कहा जा सकता है। यह वास्तविक समय या अनिवार्य प्रणालियों के लिए स्वीकार्य नहीं है, जहां उपयोगकर्ता को संचालन द्वारा लिए गए समय को अनुमानित होने की आवश्यकता हो सकती है। इसके अलावा, यह अप्रत्याशितता समानांतरता के उपयोग को जटिल बनाती है। उन समस्याओं से बचने के लिए, कुछ डेटा संरचनाएँ अक्षम संचालन को स्थगित करने की अनुमति देती हैं-इसे शेड्यूलिंग कहा जाता है। एकमात्र आवश्यकता यह है कि अक्षम संचालन की गणना इसके परिणाम की वास्तव में आवश्यकता होने से पहले समाप्त हो जानी चाहिए। अक्षम संचालन का एक निरंतर हिस्सा एक कुशल संचालन के लिए निम्नलिखित कॉल के साथ एक साथ किया जाता है, ताकि अक्षम संचालन पहले से ही पूरी तरह से किया जा सके जब इसकी आवश्यकता हो, और प्रत्येक व्यक्तिगत संचालन कुशल बना रहे। उदाहरण के लिएः कतार परिशोधन कतारें दो एकल-जुड़ी सूचियों से बनी होती हैंः सामने और पीछे की ओर। तत्वों को पिछली सूची में जोड़ा जाता है और उन्हें पहली सूची से हटा दिया जाता है। इसके अलावा, जब भी आगे की कतार खाली होती है, तो पीछे की कतार उलट जाती है और आगे की कतार बन जाती है, जबकि पीछे की कतार खाली हो जाती है। प्रत्येक ऑपरेशन की परिशोधन समय जटिलता स्थिर रहती है। सूची के प्रत्येक कक्ष को अधिक से अधिक एक बार जोड़ा जाता है, उलट दिया जाता है और हटा दिया जाता है। एक अक्षम संचालन से बचने के लिए जहां पीछे की सूची को उलट दिया जाता है, वास्तविक समय की कतारें इस प्रतिबंध को जोड़ती हैं कि पीछे की सूची केवल सामने की सूची जितनी लंबी होती है। यह सुनिश्चित करने के लिए कि पीछे की सूची सामने की सूची से लंबी हो जाए, सामने की सूची को पीछे की सूची में जोड़ा जाता है और उलट दिया जाता है। चूँकि यह ऑपरेशन अक्षम है, इसलिए इसे तुरंत नहीं किया जाता है। इसके बजाय, यह बाद के कार्यों में फैला हुआ है। इस प्रकार, प्रत्येक कक्ष की गणना आवश्यकता से पहले की जाती है, और एक नए अक्षम संचालन को बुलाने की आवश्यकता से पहले नई अग्रिम सूची की पूरी तरह से गणना की जाती है। निरंतर डेटा संरचना भी देखें क्रिस ओकासाकी द्वारा बाहरी लिंक विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं थीसिस (पीडीएफ प्रारूप) जेम्स आर. ड्रिस्कॉल, नील सारनाक, डैनियल डी. स्लेटर, रॉबर्ट ई. टार्जन (पीडीएफ) द्वारा डेटा-संरचनाओं को निरंतर बनाना जेम्स आर. ड्रिस्कॉल, डैनियल डी. स्लेटर, रॉबर्ट ई. टार्जन (पीडीएफ) द्वारा कैटेनेशन के साथ पूरी तरह से निरंतर सूची एमआईटी ओपनकोर्सवेयर पाठ्यक्रम से निरंतर डेटा संरचनाएं उन्नत एल्गोरिदम ओकासाकी के बाद से विशुद्ध रूप से कार्यात्मक डेटा संरचनाओं में क्या नया है? सैद्धांतिक कंप्यूटर विज्ञान स्टैक एक्सचेंज कार्यात्मक डेटा संरचना कार्यात्मक प्रोग्रामिंग पर