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

Question

यह कार्यात्मक प्रोग्रामिंग के बारे में एक सामान्य सवाल है, लेकिन मुझे यह भी रूचि है कि विशिष्ट भाषाओं में इसका क्या जवाब है।

मेरे पास केवल कार्यात्मक भाषाओं के बारे में शुरुआती ज्ञान है, इसलिए मेरे साथ भालू।

यह मेरी समझ है कि कार्यात्मक भाषाएं अनिवार्य भाषाओं की तुलना में विभिन्न डेटा संरचनाओं पर ध्यान केंद्रित करती हैं, क्योंकि वे अपरिवर्तनीयता पसंद करते हैं: लगातार डेटा संरचनाएं।

उदाहरण के लिए, वे सब एक अपरिवर्तनीय सूची अवधारणा है जहाँ आप एक नई सूचियों x :: l और y :: l किसी मौजूदा सूची l और दो नए x और y कॉपी किया जा करने की जरूरत के l के सभी तत्वों के बिना आइटम से फार्म कर सकते हैं। यह संभावित रूप से पुराने सूची को पूंछ के रूप में इंगित करने वाली नई सूची वस्तु द्वारा कार्यान्वित किया जाता है।

अनिवार्य भाषाओं में, ऐसी डेटा संरचना का शायद ही कभी उपयोग किया जाता है, क्योंकि वे सी-स्टाइल सरणी के रूप में संदर्भ के अच्छे इलाके के रूप में प्रदान नहीं करते हैं।

सामान्य रूप से, कार्यात्मक शैली का समर्थन करने वाले डेटा संरचनाओं को ढूंढना अपने आप का एक प्रयास है, इसलिए यह बहुत अच्छा होगा अगर किसी को हमेशा ऐसा नहीं करना पड़ेगा।

अब यहां एक विचार है कि यदि कोई इसके लिए सही भाषा समर्थन है तो कोई कार्यात्मक प्रोग्रामिंग में सभी शास्त्रीय डेटा संरचनाओं का उपयोग कैसे कर सकता है।

सामान्य तौर पर, एक अनिवार्य भाषा में एक डेटा संरचना है आपरेशनों उस पर परिभाषित (छद्म कोड में) को संशोधित:

data.modify(someArgument) 

इस लेखन के कार्यात्मक तरीका है

newData = modified(data, someArgument) 

सामान्य

समस्या यह है कि इसे सामान्य रूप से डेटा संरचना की प्रतिलिपि बनाने की आवश्यकता होती है - सिवाय इसके कि अगर भाषा को पता चल सके कि data वास्तव में किसी और चीज द्वारा उपयोग नहीं किया जाएगा: फिर, संशोधन को मूल रूप से म्यूट करने के रूप में किया जा सकता है और कोई भी अलग नहीं बता सकता सम्मेलन।

ऐसे मामले भाषा के "कहीं और इस्तेमाल कभी नहीं" है कि संपत्ति का अनुमान लगा सकता है का एक बड़ा वर्ग है: जब modified को पहले तर्क, एक अबाध मूल्य है इस उदाहरण में है:

newData = modified(modified(data, someArgument)) 

यहाँ, data कहीं और इस्तेमाल किया जा सकता है, लेकिन modified(data, someArgument) स्पष्ट रूप से नहीं है।

सी ++ में यह "रेवल्यू" कहा जाता है, और सी ++ के नवीनतम अवतार में, जो विडंबनात्मक रूप से अन्यथा कार्यात्मक नहीं है, कोई भी ऐसे राक्षसों पर अधिभारित कर सकता है।

उदाहरण के लिए, एक लिख सकते हैं:

Data modified(Data const& data) { // returns a modified copy } 
Data modified(Data && data) { // returns the modified original } 

इसका मतलब है कि सी ++ में, एक वास्तव में किसी भी परिवर्तनशील कुशल डेटा संरचना लेने के लिए और यह एक अपरिवर्तनीय एपीआई है कि एक पूरी तरह कार्यात्मक में इस्तेमाल किया जा सकता करने के लिए परिवर्तित कर सकते हैं अनिवार्य रूप से अनिवार्य रूप से आवश्यक संस्करण के रूप में रास्ता होगा।

(यह चेतावनी है कि सी ++ में कभी-कभी कास्टिंग ओवरलोड को मजबूर करने के लिए कभी-कभी कास्टिंग आवश्यक होता है। और इस तरह के डेटा संरचनाओं को लागू करने पर निश्चित रूप से देखभाल की आवश्यकता होती है, यानी रावल्यू ओवरलोड का उपयोग करते समय। यह शायद बेहतर हो सकता है हालांकि पर)

अब मेरे सवाल:।

क्या वास्तविक कार्यात्मक भाषाओं के लिए एक समान तंत्र है? या यह किसी अन्य कारण के लिए जरूरी नहीं है?

)

Answer 1

मैं बहुत यकीन है कि उर्फ ​​विश्लेषण की तरह एक सुविधा (पता चल सके कि डेटा को कहीं और प्रयोग किया जाता है) (हास्केल और Clojure जैसे अन्य एफपी भाषाओं के और न ही भाग) स्काला संकलक का हिस्सा नहीं है हूँ। स्कैला में संग्रह API (उदाहरण के लिए) स्पष्ट रूप से immutable और mutable पैकेजों में विभाजित है। immutable डेटा संरचनाओं की प्रतिलिपि बनाने की आवश्यकता को अस्वीकार करने के लिए संरचनात्मक साझाकरण की अवधारणा का उपयोग करें और इसलिए अपरिवर्तनीय संरचनाओं के साथ काम करने के लिए ओवरहेड (अस्थायी डेटा की मात्रा के मामले में) को कम करें।

जैसा कि आपने पहले ही बताया है, :: जैसी विधियां एक नई अपरिवर्तनीय संरचना बनाती हैं, जो हुड के तहत किसी भी मौजूदा अपरिवर्तनीय डेटा (इसकी प्रतिलिपि बनाने के बजाय) का संदर्भ देती है। (उदाहरण के लिए स्काला में) mutable और immutable प्रकार mutable डेटा (आमतौर पर एक आलसी फैशन में) की एक प्रतिलिपि बनाने, बल्कि इस तरह के देखना हो mutable संरचना कहीं और करने के लिए भेजा नहीं है, क्योंकि किसी भी तंत्र का उपयोग करने से और के बीच

रूपांतरण इसे उत्परिवर्तित करने की इजाजत दी गई है।

जब मैं पहली बार जावा से स्कैला में स्थानांतरित हो गया था, मैंने शुरू में सोचा था कि (अक्सर) अस्थायी संरचनाओं के साथ काम करते समय बनाए जाने वाले अस्थायी डेटा का एक बड़ा सौदा प्रदर्शन प्रदर्शन बाधा हो सकता है और वास्तव में उत्परिवर्तन की अनुमति देने के लिए कुछ चालाक तकनीकें शामिल हो सकती हैं ऐसा करना सुरक्षित था लेकिन ऐसा इसलिए नहीं है क्योंकि विचार यह है कि अपरिवर्तनीय डेटा कभी भी युवा मूल्यों को इंगित नहीं करता है। चूंकि युवा मूल्य उस समय मौजूद नहीं होते हैं जब एक पुराना मूल्य बनाया जाता है, इसे सृजन के समय इंगित नहीं किया जा सकता है, और चूंकि मान कभी संशोधित नहीं होते हैं, न ही बाद में इसकी ओर इशारा किया जा सकता है। नतीजा यह है कि स्कैला/हास्केल जैसी एफपी भाषाएं इस अस्थायी डेटा को उत्पन्न करने में सक्षम हैं क्योंकि कचरा कलेक्टर इसे बहुत ही कम समय में हटाने में सक्षम हैं।

संक्षेप में, स्कैला/हास्केल (मुझे एफ # के बारे में निश्चित नहीं है) अपरिवर्तनीय संरचनाओं के उत्परिवर्तन की अनुमति नहीं देता है क्योंकि मौजूदा जेवीएम जैसे रनटाइम वातावरण की स्थिति बहुत ही कुशल कचरा संग्रह है और इसलिए अस्थायी डेटा को हटाया जा सकता है जल्दी जल्दी। बेशक, जैसा कि मुझे यकीन है कि आप जानते हैं, म्यूचुअल तत्व युक्त एक अपरिवर्तनीय संरचना स्काला जैसे एफपी भाषाओं में पूरी तरह से संभव है लेकिन यद्यपि उत्परिवर्तनीय तत्वों को बदला जा सकता है, अपरिवर्तनीय कंटेनर यानी नहीं हो सकता है। तत्वों को न तो जोड़ा/हटाया जा सकता है।

Answer 2

1 कार्यात्मक प्रोग्रामिंग भाषाओं का समर्थन लगातार डाटा संरचनाओं (मैं कुछ विशिष्ट भाषाओं मैं विशेष रूप से में दिलचस्पी रखता हूँ। टैग किया गया)। जब डेटा संरचना को दूसरे में परिवर्तित किया जाता है या डेटा संरचना पर कोई भी ऑपरेशन किया जाता है जो एक नई डेटा संरचना उत्पन्न करता है, तो डेटा संरचना के अपरिवर्तित हिस्सों को विशेष रूप से सूचियों के मामले में जोड़कर पुन: उपयोग किया जाता है।

कंप्यूटिंग में, एक सतत डेटा संरचना एक डेटा संरचना है जो हमेशा संशोधित होने पर अपने पिछले संस्करण को सुरक्षित रखती है। इस तरह के डेटा संरचना प्रभावी रूप से अपरिवर्तनीय हैं, क्योंकि उनके परिचालन संरचना (दृश्यमान रूप से) संरचना को अद्यतन नहीं करते हैं, बल्कि इसके बजाय हमेशा एक नई अद्यतन संरचना उत्पन्न करते हैं।

2) विशुद्ध रूप से आलसी कार्यात्मक भाषाओं में गणना टाल जाता है और जब अभिव्यक्ति के परिणाम अंतिम मूल्य/परिणाम के लिए प्रयोग किया जाता है मूल्यांकन केवल किया जाता है। यह तंत्र अनावश्यक गणना से बचने में मदद करेगा।

Answer 3

यह सच है कि लगातार डाटा संरचनाओं उनके परिवर्तनशील समकक्षों की तुलना में कम होती है। इसके बारे में कोई विवाद नहीं है। कभी-कभी अंतर नगण्य होता है (एक सरणी बनाम एक लिंक्ड सूची पर पुनरावृत्ति), दूसरी बार यह बड़ा हो सकता है (रिवर्स में पुनरावृत्त), लेकिन यह बात नहीं है। अपरिवर्तनीय डेटा का उपयोग करने का विकल्प एक जागरूक है (या होना चाहिए): हम स्थिरता के लिए प्रदर्शन कर रहे हैं।

इस बिंदु पर विचार करें: अधिकांश (सभी नहीं) आधुनिक कार्यक्रमों के लिए, स्थानीय प्रदर्शन चिंता नहीं है। आज के कार्यक्रमों के लिए, असली प्रदर्शन बाधा समानांतरता में है - दोनों स्थानीय मशीनों पर साझा स्मृति के साथ-साथ विभिन्न मशीनों में भी। डेटा की मात्रा के साथ हम इन दिनों प्रसंस्करण कर रहे हैं, स्मृति क्षेत्र और शाखा भविष्यवाणी से हर आखिरी बिट को निचोड़ने से यह कटौती नहीं होगी। हमें पैमाने की जरूरत है। और समांतर कार्यक्रमों में बग का नंबर एक स्रोत अनुमान लगाएं? यह सही है - उत्परिवर्तन।

आधुनिक कार्यक्रमों के लिए एक और बड़ी चिंता स्थिरता है। लंबे समय तक चले गए जब एक कार्यक्रम आप पर दुर्घटनाग्रस्त हो सकता था, और आपने बस इसे पुनरारंभ किया और काम करना जारी रखा। आज के कार्यक्रमों को महीनों या वर्षों के लिए मानव हस्तक्षेप के बिना, हेडलेस सर्वर पर काम करने की आवश्यकता है। आज का कार्यक्रम सिर्फ अपनी डिजिटल बाहों को फेंक नहीं सकता है और एक इंसान को यह पता लगाने की उम्मीद है कि क्या गलत हुआ। इस सेटिंग में, स्थानीय प्रदर्शन स्थिरता और समानांतरता से बहुत कम महत्वपूर्ण है: हर समय और फिर कार्यक्रम को पुनरारंभ करने के लिए मानव को किराए पर लेने के बजाय अन्य दस सर्वरों को खरीदने (या किराए पर लेना) बहुत सस्ता है।

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

और फिर, यहाँ कुछ परिप्रेक्ष्य है: हम पहले से ही वहाँ गया है। आप अपने कोड में कितनी बार goto निर्देश का उपयोग करते हैं? क्या आपने सोचा है कि ऐसा क्यों है? आप goto के साथ सभी प्रकार की स्वच्छ प्रदर्शन चालें कर सकते हैं, और फिर भी हम नहीं चुनते हैं। प्रोग्रामिंग इतिहास में किसी बिंदु पर, हमने फैसला किया है कि goto इसके लायक होने की तुलना में अधिक परेशानी थी। कच्चे पॉइंटर्स के साथ भी यही बात हुई: कई भाषाओं में उन्हें बिल्कुल नहीं मिला है, अन्य लोगों ने उन्हें बारीकी से संरक्षित किया है, और यहां तक ​​कि उन भाषाओं में जिनके पास कच्चे पॉइंटर्स तक अप्रतिबंधित पहुंच है, अब उन्हें उपयोग करने के लिए एक खराब रूप माना जाता है। आज, हम अगले चरण के मध्य में हैं: पहले हमने goto छोड़ दिया, फिर हमने कच्चे पॉइंटर्स को छोड़ दिया, अब हम धीरे-धीरे उत्परिवर्तन छोड़ रहे हैं।

हालांकि, क्या तुम सच में लगता है अपने आप को किसी वैध कारण के लिए स्थानीय प्रदर्शन का लिफाफा धक्का, और आप निर्धारित किया है कि अपरिवर्तनीय डेटा वास्तव में अड़चन है अगर (याद रखें: पहले उपाय, फिर अनुकूलित), तो सबसे कार्यात्मक भाषाओं (हास्केल और एल्म को छोड़कर) आपको अनिच्छा से यद्यपि दूर करने के लिए दूर जाने देगा। सी # में कच्चे पॉइंटर्स की तरह, आप उत्परिवर्तन कर सकते हैं, आपको इसके बारे में स्पष्ट (और सावधान) होना चाहिए। एफ # में, उदाहरण के लिए, आप परिवर्तनीय चर, कच्चे सरणी, उत्परिवर्ती रिकॉर्ड, कक्षाएं, इंटरफेस इत्यादि कर सकते हैं। यह संभव है, बस अनुशंसित नहीं है। और आम सहमति अब तक है कि जब तक यह स्थानीयकरण (यानी बाहर नहीं निकलता है) उत्परिवर्तन को नियोजित करना ठीक है, और आप वास्तव में जानते हैं कि आप क्या कर रहे हैं, और आपने इसे दस्तावेज किया है, और इसे मृत्यु के लिए परीक्षण किया है ।

इसके लिए एक सामान्य मामला "मूल्य निर्माण" है, जहां आपके पास एक ऐसा कार्य है जो अंततः एक अपरिवर्तनीय मूल्य उत्पन्न करता है, लेकिन यह करने के दौरान सभी प्रकार की गन्दा चीजें करता है। एक उदाहरण यह है कि एफ # कोर लाइब्रेरी List.map लागू करती है: आम तौर पर, क्योंकि सूचियों को फ्रंट-टू-बैक पुनरावर्तित किया जाता है, लेकिन बैक-टू-फ्रंट का निर्माण किया जाता है, किसी को पहले पुनर्नवीनीकरण सूची को पुनरावृत्त करके बनाना होगा, और फिर इसे उलट दें। तो एफ # कंपाइलर यहां धोखा देती है और सूची को बदल देती है क्योंकि इसे अतिरिक्त उलटा होने से बचाने के लिए बनाया जा रहा है।

और "इलाके" चिंता पर एक और नोट। याद रखें कि मैंने कैसे बताया कि आप goto के साथ सभी प्रकार की सुन्दर प्रदर्शन चालें कर सकते हैं? खैर, यह अब और सच नहीं है। चूंकि प्रोग्रामर ने goto के बिना प्रोग्राम लिखना शुरू कर दिया है, इसलिए बाइनरी कोड अधिक अनुमानित हो गया है, क्योंकि अब कूदने वाले कंपाइलर्स द्वारा उत्पन्न किए जाते हैं, न कि मनुष्यों द्वारा कोडित। इससे सीपीयू के लिए यह संभव हो गया, अच्छी तरह से, भविष्यवाणी करें, और इन भविष्यवाणियों के आधार पर प्रसंस्करण अनुकूलित करें। अंत परिणाम यह है कि अब आपको खराबgoto के अपरिचित उपयोग द्वारा लूप जैसे स्वीकृत उच्च-स्तरीय टूल का उपयोग करके संभवतः प्राप्त होने की संभावना है। दिन में, सीपीयू उस स्मार्ट होने का जोखिम नहीं उठा सकते थे, ताकि goto का उपयोग न करने का विकल्प पूरी तरह स्थिरता उपाय था। लेकिन अब यह वास्तव में प्रदर्शन के साथ सहायक साबित हुआ, जो सोचा होगा?

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

Answer 4

ST (राज्य धागा) हास्केल में मोनैड यह सुनिश्चित करने का एक तरीका है कि कुछ क्रिया अनुक्रम में बुलाए जाते हैं (उस अनुक्रम के बाहर कोई संशोधन संभव नहीं है)। ST में आप हास्केल के भीतर अनिवार्य, परिवर्तनीय डेटा संरचनाओं का उपयोग कर सकते हैं। ध्यान दें कि हास्केल को कुछ विशुद्ध रूप से कार्यात्मक भाषाओं में से एक माना जाता है।