Corecursion
कंप्यूटर विज्ञान में, कोरकर्शन एक प्रकार का ऑपरेशन है जो पुनरावृत्ति के लिए दोहरा है। जबकि पुनरावृत्ति विश्लेषणात्मक रूप से काम करती है, एक आधार मामले से आगे के डेटा पर शुरू होती है और इसे छोटे डेटा में तोड़ती है और तब तक दोहराती है जब तक कि कोई एक आधार मामले तक नहीं पहुंच जाता है, कोरक्रशन कृत्रिम रूप से काम करता है, एक आधार मामले से शुरू होता है और इसे बनाता है, पुनरावृत्त रूप से एक आधार मामले से आगे हटाए गए डेटा का उत्पादन करता है। सीधे शब्दों में कहें तो, कोरकर्सिव एल्गोरिदम उन डेटा का उपयोग करते हैं जो वे स्वयं पैदा करते हैं, बिट दर बिट, जैसे-जैसे वे उपलब्ध होते हैं, और आवश्यकता होती है, डेटा के आगे के बिट्स का उत्पादन करने के लिए। एक समान लेकिन विशिष्ट अवधारणा जनरेटिव रिकर्शन है जिसमें कोरक्रशन और रिकर्शन में निहित एक निश्चित "दिशा" का अभाव हो सकता है। जहाँ पुनरावृत्ति कार्यक्रमों को मनमाने ढंग से जटिल डेटा पर काम करने की अनुमति देती है, जब तक कि उन्हें सरल डेटा (आधार मामले) तक कम किया जा सकता है, कोरक्रशन कार्यक्रमों को मनमाने ढंग से जटिल और संभावित रूप से अनंत डेटा संरचनाओं का उत्पादन करने की अनुमति देता है, जैसे कि धाराएँ, जब तक कि इसे सरल डेटा (आधार मामले) से सीमित चरणों के अनुक्रम में उत्पादित किया जा सकता है। जहाँ पुनरावृत्ति समाप्त नहीं हो सकती है, कभी भी एक आधार अवस्था तक नहीं पहुँचती है, कोरक्रशन एक आधार अवस्था से शुरू होता है, और इस प्रकार निर्धारक रूप से बाद के चरणों का उत्पादन करता है, हालांकि यह अनिश्चित काल तक आगे बढ़ सकता है (और इस प्रकार सख्त मूल्यांकन के तहत समाप्त नहीं हो सकता है), या यह उत्पादन से अधिक उपभोग कर सकता है और इस प्रकार गैर-उत्पादक हो जाता है। कई कार्य जिनका पारंपरिक रूप से पुनरावर्ती के रूप में विश्लेषण किया जाता है, वैकल्पिक रूप से, और यकीनन अधिक स्वाभाविक रूप से, कोरकर्सिव कार्यों के रूप में व्याख्या की जा सकती है जो किसी दिए गए चरण में समाप्त हो जाते हैं, उदाहरण के लिए पुनरावृत्ति संबंध जैसे फैक्टोरियल। कोरक्रर्शन परिणाम के रूप में सीमित और अनंत दोनों डेटा संरचनाओं का उत्पादन कर सकता है, और आत्म-संदर्भित डेटा संरचनाओं को नियोजित कर सकता है। कोरक्रशन का उपयोग अक्सर आलसी मूल्यांकन के संयोजन में किया जाता है, एक संभावित अनंत संरचना के केवल एक सीमित उपसमुच्चय का उत्पादन करने के लिए (एक बार में एक पूरी अनंत संरचना का उत्पादन करने की कोशिश करने के बजाय)। कोरक्रशन कार्यात्मक प्रोग्रामिंग में एक विशेष रूप से महत्वपूर्ण अवधारणा है, जहां कोरक्रशन और कोडाटा कुल भाषाओं को अनंत डेटा संरचनाओं के साथ काम करने की अनुमति देते हैं। उदाहरण कोरक्रशन को पुनरावृत्ति के विपरीत समझा जा सकता है, जो अधिक परिचित है। जबकि कोरक्रशन मुख्य रूप से कार्यात्मक प्रोग्रामिंग में रुचि रखता है, इसे अनिवार्य प्रोग्रामिंग का उपयोग करके चित्रित किया जा सकता है, जो पायथन में जनरेटर सुविधा का उपयोग करके नीचे किया गया है। इन उदाहरणों में स्थानीय चर का उपयोग किया जाता है, और अनिवार्य रूप से (विनाशकारी रूप से) मान निर्धारित किए जाते हैं, हालांकि ये शुद्ध कार्यात्मक प्रोग्रामिंग में कोरक्रशन में आवश्यक नहीं हैं। शुद्ध कार्यात्मक प्रोग्रामिंग में, स्थानीय चरों को निर्दिष्ट करने के बजाय, ये संगणित मान एक अपरिवर्तनीय अनुक्रम बनाते हैं, और पूर्व मूल्यों को स्व-संदर्भ द्वारा प्राप्त किया जाता है (अनुक्रम में बाद के मान गणना किए जाने वाले अनुक्रम में पहले के मूल्यों को संदर्भित करते हैं)। असाइनमेंट बस इसे अनिवार्य प्रतिमान में व्यक्त करते हैं और स्पष्ट रूप से निर्दिष्ट करते हैं कि गणनाएँ कहाँ होती हैं, जो प्रदर्शनी को स्पष्ट करने का काम करती है। फैक्टोरियल रिकर्शन का एक उत्कृष्ट उदाहरण फैक्टोरियल की गणना करना है, जिसे 0 द्वारा पुनरावर्ती रूप से परिभाषित किया जाता है! : = 1 और n! : = n × (n-1)! किसी दिए गए इनपुट पर अपने परिणाम की पुनरावर्ती गणना करने के लिए, एक पुनरावर्ती कार्य एक अलग (किसी तरह से "छोटा") इनपुट के साथ खुद को (की एक प्रति) कॉल करता है और अपने परिणाम का निर्माण करने के लिए इस कॉल के परिणाम का उपयोग करता है। पुनरावर्ती कॉल वही करता है, जब तक कि आधार मामले तक नहीं पहुँच गया हो। इस प्रकार इस प्रक्रिया में एक कॉल स्टैक विकसित होता है। उदाहरण के लिए, फ़ेस (3) की गणना करने के लिए, यह पुनरावर्ती रूप से फ़ेस (2), फ़ेस (1), फ़ेस (0) (स्टैक को "बंद करना") में कॉल करता है, जिस बिंदु पर पुनरावृत्ति फ़ेस (0) = 1 के साथ समाप्त होती है, और फिर स्टैक विपरीत क्रम में खुल जाता है और परिणामों की गणना कॉल स्टैक के साथ प्रारंभिक कॉल फ्रेम फ़ेस (3) में वापस जाते समय की जाती है जो फ़ेस (2) = 2 के परिणाम का उपयोग करके अंतिम परिणाम की गणना 3 × 2 = 3 × फ़ेस (2) =: फ़ेस (3) के रूप में करता है और अंत में फ़ेस (3) = 6 लौटाता है। इस उदाहरण में एक फलन एक ही मान देता है। इस स्टैक अनवाइंडिंग को स्पष्ट किया जा सकता है, फैक्टोरियल कोरकर्सिवली को परिभाषित करते हुए, एक इटरेटर के रूप में, जहां कोई मामले के साथ शुरू होता है, फिर इस प्रारंभिक मान से बढ़ती संख्या 1,2,3 के लिए फैक्टोरियल मानों का निर्माण होता है. जैसा कि उपरोक्त पुनरावर्ती परिभाषा में "समय तीर" के साथ उल्टा होता है, जैसा कि था, इसे पीछे की ओर पढ़कर कोरकर्सिव एल्गोरिथ्म इस प्रकार परिभाषित किया गया है जो सभी फैक्टोरियल की एक धारा उत्पन्न करता है। इसे जनरेटर के रूप में ठोस रूप से लागू किया जा सकता है। प्रतीकात्मक रूप से, यह देखते हुए कि अगले भाज्य मान की गणना के लिए n और f (एक पिछला भाज्य मान) दोनों का ध्यान रखने की आवश्यकता होती है, इसे इस प्रकार दर्शाया जा सकता हैः या हास्केल में, (\(n, f)-> (n + 1, f * (n + 1)) 'पुनरावृत्ति' (0,1) जिसका अर्थ है, "प्रत्येक चरण से शुरू करते हुए, अगले मानों की गणना इस प्रकार की जाती है"। यह गणितीय रूप से समतुल्य है और पुनरावर्ती परिभाषा के लगभग समान है, लेकिन इस बात पर जोर देता है कि भाज्य मानों का निर्माण किया जा रहा है, प्रारंभिक मामले से आगे जा रहा है, बजाय इसके कि पहले पीछे जाने के बाद गणना की जा रही है, आधार मामले में नीचे, एक कमी के साथ। कोरकर्सिव फलन के प्रत्यक्ष उत्पादन में केवल भाज्य मान नहीं होते हैं, बल्कि प्रत्येक मूल्य के लिए अनुक्रम में इसके सूचकांक एन का सहायक डेटा भी शामिल होता है, ताकि आवश्यकता पड़ने पर उन सभी में से किसी एक विशिष्ट परिणाम का चयन किया जा सके। डिनोटेशनल शब्दार्थ के साथ एक संबंध है, जहां पुनरावर्ती कार्यक्रमों के संकेत इस तरह से मूल रूप से बनाए जाते हैं। पायथन में, एक पुनरावर्ती भाज्य फलन को इस प्रकार परिभाषित किया जा सकता हैः डेफ भाज्य (n: int)-> int: "पुनरावर्ती भाज्य फलन"। यदि n = = 0:1 लौटाता है अन्यथाः n * भाज्य (n-1) लौटाता है तो इसे उदाहरण के लिए 5 की गणना करने के लिए भाज्य (5) कहा जा सकता है! एक संबंधित कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता हैः डेफ फैक्टोरियल्स (): "कोरकर्सिव जनरेटर"। n, f = 0,1 जबकि सहीः उपज f n, f = n + 1, f * (n + 1) यह क्रम में भाज्यों की एक अनंत धारा उत्पन्न करता है; इसका एक सीमित हिस्सा निम्न द्वारा उत्पादित किया जा सकता हैः डेफ n _ फैक्टोरियल्स (n: int): k, f = 0,1 जबकि k <= n: उपज f k, f = k + 1, f * (k + 1) इसे तब 5 तक भाज्यों का उत्पादन करने के लिए कहा जा सकता है! के माध्यम सेः f के लिए n _ फैक्टोरियल्स में (5): प्रिंट (f) यदि हम केवल एक निश्चित फैक्टोरियल में रुचि रखते हैं, तो केवल अंतिम मान लिया जा सकता है, या हम उत्पादन और पहुंच को एक फ़ंक्शन में फ्यूज कर सकते हैं, डेफ nth _ फैक्टोरियल (n: int): k, f = 0,1 जबकि k <n: k, f = k + 1, f * (k + 1) रिटर्न f जैसा कि यहाँ आसानी से देखा जा सकता है, यह व्यावहारिक रूप से पूंछ पुनरावृत्ति के लिए संचायक तर्क तकनीक के बराबर है (केवल वहाँ केवल उपज के लिए वापसी को प्रतिस्थापित करके), एक स्पष्ट लूप में खुला। इस प्रकार यह कहा जा सकता है कि कोरक्रशन की अवधारणा पुनरावृत्ति परिभाषाओं द्वारा पुनरावृत्ति गणना प्रक्रियाओं के अवतार का एक स्पष्टीकरण है, जहां लागू हो। उसी तरह, फिबोनाची अनुक्रम को इस प्रकार दर्शाया जा सकता हैः क्योंकि फिबोनाची अनुक्रम क्रम 2 का एक पुनरावृत्ति संबंध है, कोरकर्सिव संबंध को दो क्रमिक शब्दों को ट्रैक करना चाहिए, जिसमें एक कदम से आगे बढ़ने के लिए, और अगले पद की गणना के लिए। इसके बाद इसे निम्नानुसार लागू किया जा सकता है (समानांतर कार्य का उपयोग करते हुए): डेफ फाइबोनैचि अनुक्रम (): a, b = 0,1 जबकि सत्यः उपज a a, b = b, a + b हास्केल में, मानचित्र fst ((\(a, b)-> (b, a + b)) 'पुनरावृत्ति' (0,1)) गहराई-प्रथम दृष्टिकोण के माध्यम से ट्री ट्रैवर्सल ट्री ट्रैवर्सल पुनरावृत्ति का एक उत्कृष्ट उदाहरण है। दोगुना रूप से, चौड़ाई-प्रथम पारगमन को कोरक्रशन के माध्यम से बहुत स्वाभाविक रूप से लागू किया जा सकता है। पुनरावृत्त रूप से, कोई व्यक्ति एक वृक्ष को उसके मूल नोड को एक डेटा संरचना में रखकर पार कर सकता है, फिर उस डेटा संरचना के साथ पुनरावृत्ति कर सकता है, जबकि वह खाली नहीं है, प्रत्येक चरण पर उसमें से पहले नोड को हटा सकता है और हटाए गए नोड के चाइल्ड नोड को उस डेटा संरचना में वापस रख सकता है। यदि डेटा संरचना एक स्टैक (एल. आई. एफ. ओ.) है, तो यह डेप्थ-फर्स्ट ट्रैवर्सल देता है, और यदि डेटा संरचना एक कतार (एफ. आई. एफ. ओ.) है, तो यह चौड़ाई-फर्स्ट ट्रैवर्सल देता हैः रिकर्शन का उपयोग करते हुए, एक ट्री का डेप्थ-फर्स्ट ट्रैवर्सल बस रूट नोड के चाइल्ड नोड्स में से प्रत्येक को बारी-बारी से पार करने के रूप में लागू किया जाता है। इस प्रकार दूसरा चाइल्ड सबट्री तब तक संसाधित नहीं किया जाता है जब तक कि पहला चाइल्ड सबट्री समाप्त नहीं हो जाता। रूट नोड के मूल्य को अलग से संभाला जाता है, चाहे पहले चाइल्ड को पार करने से पहले (जिसके परिणामस्वरूप प्री-ऑर्डर ट्रेवर्सल होता है), पहले के समाप्त होने के बाद और दूसरे (इन-ऑर्डर) से पहले, या दूसरे चाइल्ड नोड के समाप्त होने के बाद (पोस्ट-ऑर्डर)-- यह मानते हुए कि ट्री द्विआधारी है, प्रदर्शनी की सरलता के लिए। कॉल स्टैक (पुनरावर्ती पारगमन कार्य आह्वान का) उस स्टैक से मेल खाता है जिसे ऊपर उल्लिखित स्पष्ट एल. आई. एफ. ओ. संरचना हेरफेर के साथ दोहराया जाएगा। प्रतीकात्मक रूप से, "पुनरावृत्ति" के यहाँ दो अर्थ हैं। सबसे पहले, ट्री ट्रेवर्सल फ़ंक्शंस के पुनरावर्ती आह्वान। अधिक विशेष रूप से, हमें इस बात से संघर्ष करने की आवश्यकता है कि यहाँ मूल्यों की परिणामी सूची कैसे बनाई गई है। पुनरावर्ती, बॉटम-अप आउटपुट निर्माण के परिणामस्वरूप दाएँ से बाएँ ट्री ट्रैवर्सल होगा। इसे वास्तव में इच्छित बाएँ-से-दाएँ क्रम में करने के लिए अनुक्रमण को कुछ बाहरी साधनों द्वारा लागू करने की आवश्यकता होगी, या यह स्वचालित रूप से प्राप्त हो जाएगा यदि आउटपुट को ऊपर-नीचे फैशन में बनाया जाना था, अर्थात। मूल रूप से। ऊपर से नीचे के क्रम में अपने उत्पादन का निर्माण करने वाले एक चौड़ाई-पहले ट्रैवर्सल को मूल नोड से शुरू करके, इसके मूल्य का उत्पादन करके, फिर चौड़ाई-पहले सबट्री को पार करके-यानी, सबट्री की पूरी सूची को अगले चरण में पारित करके (एक भी सबट्री नहीं, जैसा कि पुनरावर्ती दृष्टिकोण में)-अगले चरण में उनके सभी मूल नोड्स के मूल्यों का उत्पादन करके, फिर उनके चाइल्ड सबट्री आदि को पारित करके भी लागू किया जा सकता है। इस मामले में जनरेटर फ़ंक्शन, वास्तव में आउटपुट अनुक्रम स्वयं, कतार के रूप में कार्य करता है। जैसा कि ऊपर के भाज्य उदाहरण में, जहां सूचकांक की सहायक जानकारी (कौन सा चरण एक पर था, एन) को आगे बढ़ाया गया था, n! के वास्तविक उत्पादन के अलावा, इस मामले में वास्तविक उत्पादन के अलावा शेष उप-पेड़ों की सहायक जानकारी को आगे बढ़ाया जाता है। प्रतीकात्मक रूप से, जिसका अर्थ है कि प्रत्येक चरण में, इस स्तर के नोड्स में मूल्यों की सूची का उत्पादन होता है, फिर अगले स्तर के नोड्स में आगे बढ़ता है। इस अनुक्रम से केवल नोड मानों को उत्पन्न करने के लिए केवल सहायक चाइल्ड ट्री डेटा को त्यागने की आवश्यकता होती है, फिर सूचियों की सूची को चपटा करने की आवश्यकता होती है (मानों को शुरू में स्तर (गहराई) द्वारा समूहीकृत किया जाता है; चपटा करने (अनग्रुपिंग) से एक सपाट रैखिक सूची प्राप्त होती है)। यह विस्तार से उपरोक्त विनिर्देशन के बराबर है। हास्केल में, कॉन्कैटमैप fst (((v, ts)-> (रूटवैल्यूज ts, चाइल्डट्रीज़ ts)) 'इटरेट' ([], [फुलट्री]) विशेष रूप से, एक अनंत ट्री को देखते हुए, कोरकर्सिव ब्रेड्थ-फर्स्ट ट्रैवर्सल सभी नोड्स को पार करेगा, जैसे कि एक सीमित ट्री के लिए, जबकि रिकर्सिव डेप्थ-फर्स्ट ट्रैवर्सल एक शाखा से नीचे जाएगा और सभी नोड्स को पार नहीं करेगा, और वास्तव में यदि पोस्ट-ऑर्डर को पार करता है, जैसा कि इस उदाहरण (या इन-ऑर्डर) में है, तो यह किसी भी नोड्स पर बिल्कुल नहीं जाएगा, क्योंकि यह कभी भी एक पत्ती तक नहीं पहुंचता है। यह अनंत डेटा संरचनाओं से निपटने के लिए पुनरावृत्ति के बजाय कोरक्रशन की उपयोगिता को दर्शाता है। एक चेतावनी अभी भी अनंत शाखा कारक वाले पेड़ों के लिए बनी हुई है, जिन्हें जगह का बेहतर तरीके से पता लगाने के लिए अधिक चौकस इंटरलेसिंग की आवश्यकता है। डॉवटेयलिंग देखें। पायथन में, इसे निम्नानुसार लागू किया जा सकता है। सामान्य पोस्ट-ऑर्डर डेप्थ-फर्स्ट ट्रैवर्सल को इस प्रकार परिभाषित किया जा सकता हैः डेफ डीएफ (नोड): "पोस्ट-ऑर्डर डेप्थ-फर्स्ट ट्रैवर्सल"। यदि नोड कोई नहीं हैः df (node.left) df (node.right) प्रिंट (node.value) फिर इसे डीएफ (टी) द्वारा कॉल किया जा सकता है ताकि पेड़ के नोड्स के मूल्यों को पोस्ट-ऑर्डर डेप्थ-फर्स्ट ऑर्डर में प्रिंट किया जा सके। चौड़ाई-प्रथम कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता हैः डेफ बीएफ (ट्री): "चौड़ाई-प्रथम कोरकर्सिव जनरेटर"। ट्री _ लिस्ट = [ट्री] जबकि ट्री _ लिस्टः न्यू _ ट्री _ लिस्ट = [] ट्री _ लिस्ट में ट्री के लिएः अगर ट्री कोई नहीं हैः उपज tree.value new_tree_list.append (tree.left) new_tree_list.append (tree.right) ट्री _ लिस्ट = न्यू _ ट्री _ लिस्ट इसे तब पेड़ के नोड्स के मूल्यों को चौड़ाई-पहले क्रम में प्रिंट करने के लिए कहा जा सकता हैः bf (t) में i के लिएः प्रिंट (i) परिभाषा प्रारंभिक डेटा प्रकारों को किसी प्रकार के समीकरण के सबसे कम निश्चित बिंदु (समरूपता तक) के रूप में परिभाषित किया जा सकता है; समरूपता को फिर प्रारंभिक बीजगणित द्वारा दिया जाता है। दोहरी रूप से, अंतिम (या अंतिम) डेटा प्रकारों को एक प्रकार के समीकरण के सबसे बड़े निश्चित बिंदु के रूप में परिभाषित किया जा सकता है; समरूपता तब एक अंतिम कोल बीजगणित द्वारा दी जाती है। यदि प्रवचन का क्षेत्र समुच्चयों और कुल कार्यों की श्रेणी है, तो अंतिम डेटा प्रकारों में अनंत, गैर-स्थापित मूल्य हो सकते हैं, जबकि प्रारंभिक प्रकार नहीं होते हैं। दूसरी ओर, यदि प्रवचन का क्षेत्र पूर्ण आंशिक क्रम और निरंतर कार्यों की श्रेणी है, जो मोटे तौर पर हास्केल प्रोग्रामिंग भाषा से मेल खाते हैं, तो अंतिम प्रकार प्रारंभिक प्रकारों के साथ मेल खाते हैं, और संबंधित अंतिम कोलजेब्रा और प्रारंभिक बीजगणित एक समरूपता बनाते हैं। कोरक्रशन तब पुनरावर्ती रूप से कार्यों को परिभाषित करने के लिए एक तकनीक है जिसकी सीमा (कोडोमेन) एक अंतिम डेटा प्रकार है, जो उस तरीके से दोहरी है जो साधारण पुनरावर्ती पुनरावर्ती रूप से कार्यों को परिभाषित करता है जिसका डोमेन एक प्रारंभिक डेटा प्रकार है। नीचे दी गई चर्चा में हास्केल में कई उदाहरण दिए गए हैं जो कोरक्रशन को अलग करते हैं। मोटे तौर पर, यदि कोई इन परिभाषाओं को सेट की श्रेणी में रखता है, तो वे अभी भी कोरकर्सिव होंगे। यह अनौपचारिक उपयोग हास्केल के बारे में मौजूदा पाठ्यपुस्तकों के अनुरूप है। इस लेख में उपयोग किए गए उदाहरण कोरक्रशन को परिभाषित करने और यह समझाने के प्रयासों से पहले के हैं कि यह क्या है। चर्चा कोडाटा पर आदिम कोरक्रर्शन के लिए नियम डेटा पर आदिम पुनरावृत्ति के लिए नियम का दोहरा है। तर्क पर उतरने के बजाय इसके निर्माताओं पर पैटर्न-मिलान करके (जिन्हें पहले, कहीं बुलाया गया था, इसलिए हम एक तैयार-निर्मित डेटम प्राप्त करते हैं और इसके घटक उप-भागों पर पहुँचते हैं, अर्थात। "फील्ड्स"), हम इसके "डिस्ट्रक्टर्स" (या "ऑब्जर्वर्स", जिन्हें बाद में, कहीं बुलाया जाएगा, भरकर परिणाम पर चढ़ते हैं-इसलिए हम वास्तव में एक कंस्ट्रक्टर को बुला रहे हैं, परिणाम का एक और बिट बना रहे हैं जिसे बाद में देखा जाएगा)। इस प्रकार कोरक्रर्शन (संभावित रूप से अनंत) कोडाटा बनाता है, जबकि साधारण रिकर्शन (आवश्यक रूप से सीमित) डेटा का विश्लेषण करता है। सामान्य पुनरावृत्ति कोडाटा पर लागू नहीं हो सकती है क्योंकि यह समाप्त नहीं हो सकती है। इसके विपरीत, कोरक्रशन सख्ती से आवश्यक नहीं है यदि परिणाम प्रकार डेटा है, क्योंकि डेटा सीमित होना चाहिए। "कोक् में धाराओं के साथ प्रोग्रामिंगः एक केस स्टडीः एराटोस्थनीज की छलनी" में हम पाते हैं कि एच. डी. (कॉन्क ए. एस.) = ए. टी. एल. (कॉन्क ए. एस.) = एस. (चलनी पी. एस.) = यदि डिव पी. (एच. डी. एस.) तो चलनी पी. (टी. एल. एस.) अन्यथा कॉन्क (एच. डी. एस.) (चलनी पी. (टी. एल. एस.)) एच. डी. (प्राइम एस.) = (एच. डी. एस.) टी. एल. (प्राइम एस.) = प्राइम (चाळनी (एच. डी. एस.) (टी. एल. एस.) जहां प्राइम "धारा (एन. यू. 2) पर प्राइम ऑपरेशन लागू करके प्राप्त किए जाते हैं। उपरोक्त संकेतन के बाद, अभाज्य संख्याओं के अनुक्रम (जिसमें एक थ्रोअवे 0 पहले जोड़ा जाता है) और संख्या धाराओं को उत्तरोत्तर छानकर हास्केल में दर्शाया जा सकता है, (\(p, s @(h: t)-> (h, चाळनी ht) 'पुनरावृत्ति' (0, [2]) लेखक चर्चा करते हैं कि कैसे छलनी की परिभाषा हमेशा उत्पादक होने की गारंटी नहीं है, और अटक सकती है जैसे। यदि प्रारंभिक धारा के रूप में [5,10.] के साथ बुलाया जाता है। यहाँ हास्केल में एक और उदाहरण है। निम्नलिखित परिभाषा रैखिक समय में फिबोनाची संख्याओं की सूची तैयार करती हैः तंतु = 0:1: ज़िप (+) तंतुओं (पूंछ तंतु) के साथ यह अनंत सूची आलसी मूल्यांकन पर निर्भर करती है; तत्वों की गणना एक आवश्यक आधार पर की जाती है, और स्मृति में केवल सीमित उपसर्गों को स्पष्ट रूप से दर्शाया जाता है। यह विशेषता कोडाटा के कुछ हिस्सों पर एल्गोरिदम को समाप्त करने की अनुमति देती है; ऐसी तकनीकें हास्केल प्रोग्रामिंग का एक महत्वपूर्ण हिस्सा हैं। यह पायथन में भी किया जा सकता हैः इटर्टूल से आयात टी, चेन, आइलिस, आईमैप डेफ ऐड (x, y): रिटर्न x + y डेफ फाइबोनाची (): डेफ डेफर्ड आउटपुट (): आउटपुट में i के लिएः यील्ड i परिणाम, c1, c2 = टी (डेफर्ड आउटपुट (), 3) युग्मित = आईमैप (जोड़ें, c1, आइस्लिस (c2,1, कोई नहीं)) आउटपुट = चेन ([0,1], युग्मित) आइस्लिस में i के लिए रिटर्न परिणाम (फाइबोनाची (), 20): प्रिंट (i) ज़िप की परिभाषा जिसमें इनलाइन किया जा सकता है, फाइबर = 0 सामान्य पुनरावृत्ति स्व-संदर्भित कार्यों का उपयोग करती है, लेकिन स्व-संदर्भित डेटा को समायोजित नहीं करती है। हालाँकि, यह फिबोनाची उदाहरण के लिए आवश्यक नहीं है। इसे निम्नानुसार फिर से लिखा जा सकता हैः फाइब्स = फाइबजेन (0,1) फाइबजेन (x, y) = x: फाइबजेन (y, x + y) यह परिणाम के निर्माण के लिए केवल स्व-संदर्भित कार्य को नियोजित करता है। यदि इसका उपयोग सख्त सूची निर्माता के साथ किया जाता है तो यह भगोड़े पुनरावृत्ति का एक उदाहरण होगा, लेकिन गैर-सख्त सूची निर्माता के साथ यह संरक्षित पुनरावृत्ति धीरे-धीरे एक अनिश्चित काल के लिए परिभाषित सूची का उत्पादन करती है। कोरक्रर्शन को एक अनंत वस्तु का उत्पादन करने की आवश्यकता नहीं है; एक कोरक्रसिव कतार इस घटना का एक विशेष रूप से अच्छा उदाहरण है। निम्नलिखित परिभाषा रैखिक समय में ऊपर-नीचे के तरीके से द्विआधारी पेड़ की चौड़ाई-पहली पारगमन उत्पन्न करती है (पहले से ही ऊपर उल्लिखित चपटेपन को शामिल करते हुए): डेटा ट्री a b = लीफ a। ब्रांच b (ट्री a b) (ट्री a b) bftrav: ट्री a b-> [ट्री a b] bftrav ट्री = ट्रीः ts जहाँ ts = जीन 1 (ट्रीः ts) जीन 0 p = [] जेन लेन (लीफ _: p) = जीन (लेन-1) p जेन लेन (ब्रांच _ l r: p) = l: r: जीन (लेन + 1) p---------------------------------------------------------- यह सूची इनपुट कतार और परिणाम दोनों के रूप में दोहरे उद्देश्य को पूरा करती है (जीन लेन पी सूची के साथ अपने इनपुट बैक-पॉइंटर, पी, से पहले अपने आउटपुट लेन नोच का उत्पादन करता है)। यह सीमित है यदि और केवल तभी जब प्रारंभिक वृक्ष सीमित हो। समाप्ति सुनिश्चित करने के लिए कतार की लंबाई को स्पष्ट रूप से ट्रैक किया जाना चाहिए; अगर यह परिभाषा केवल अनंत पेड़ों पर लागू की जाती है तो इसे सुरक्षित रूप से समाप्त किया जा सकता है। यह हास्केल कोड स्व-संदर्भित डेटा संरचना का उपयोग करता है, लेकिन अनिवार्य रूप से आलसी मूल्यांकन पर निर्भर नहीं करता है। इसका सीधा अनुवाद किया जा सकता है जैसे। प्रोलॉग जो एक आलसी भाषा नहीं है। ऊपर से नीचे की ओर एक सूची (कतार के रूप में उपयोग की जाने वाली) बनाने की क्षमता आवश्यक है। उसके लिए, प्रोलॉग में टेल रिकर्शन मॉड्यूलो कॉन्स (यानी। अंत सूची खोलें)। जो योजना, सी, आदि में भी अनुकरण योग्य है। म्यूटेबल टेल सेंटीनल पॉइंटर के साथ जुड़ी सूचियों का उपयोग करनाः bftrav (ट्री, [Tree|TS]):-bfgen (1, [Tree|TS], TS)। bfgen (0, _, []):-! कतार में% 0 प्रविष्टियाँ-- bfgen (N, [पत्ती (_) |P], TS) सूची को रोकें और बंद करें-- N2, N-1, bfgen (N2, P, TS) है। bfgen (N, [शाखा (_, L, R) |P], [L, R|TS]):-N2, N + 1, bfgen (N2, P, TS) है। %%---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- - फ़ंक्शन लेबल एक द्विआधारी वृक्ष में प्रत्येक नोड पर पहले तरीके से जाता है, प्रत्येक लेबल को एक पूर्णांक के साथ बदल देता है, प्रत्येक बाद का पूर्णांक अंतिम से 1 से बड़ा होता है। यह समाधान एक स्व-संदर्भित डेटा संरचना को नियोजित करता है, और द्विआधारी वृक्ष परिमित या अनंत हो सकता है। लेबलःः ट्री ए बी-> ट्री इंट इंट लेबल टी = टीएन जहाँ (टीएन, एनएस) = गो टी (1: एनएस) जाओःः ट्री ए बी-> [इंट]-> (ट्री इंट इंट, [इंट]) जाओ (लीफ _) (i: ए) = (लीफ आई, आई + 1: ए) जाओ (ब्रांच _ एलआर) (i: ए) = (ब्रांच आई एलएन आरएन, आई + 1: सी) जहाँ (एलएन, बी) = गो एलए (आरएन, सी) = गो आर बी या प्रोलॉग में, तुलना के लिए, लेबल (ट्री, टीएन):-लेबल (ट्री, [1|Ns], टीएन, एनएस लेबल (पत्ती (_), [I|A], पत्ती (I), [I + 1|A])। लेबल (शाखा (_, L, R), [I|A], शाखा (I, Ln, Rn), [I + 1|C]:-लेबल (L, A, Ln, B), लेबल (R, B, Rn, C)। एक एपोमोर्फिज्म (जैसे कि एनामोर्फिज्म, जैसे कि अनफोल्ड) उसी तरह से कोरक्रशन का एक रूप है जैसे कि एक पैरामोर्फिज्म (जैसे कि एक कैटामॉर्फिज्म, जैसे कि फोल्ड) पुनरावृत्ति का एक रूप है। CoQ प्रूफ सहायक कोफिक्सप्वाइंट कमांड का उपयोग करके कोरकर्शन और कॉइनडक्शन का समर्थन करता है। इतिहास कोरकर्शन, जिसे सर्कुलर प्रोग्रामिंग के रूप में संदर्भित किया जाता है, कम से कम जॉन ह्यूजेस और फिलिप वाडलर को श्रेय देता है; अधिक सामान्य रूपों को विकसित किया गया था। मूल प्रेरणाओं में अधिक कुशल एल्गोरिदम का उत्पादन (कई पास की आवश्यकता के बजाय कुछ मामलों में डेटा पर 1 पास की अनुमति देना) और कार्यात्मक भाषाओं में शास्त्रीय डेटा संरचनाओं, जैसे कि दोगुनी जुड़ी सूचियों और कतारों को लागू करना शामिल था। बाइसिम्युलेशन कॉइनडक्शन रिकर्शन एनामोर्फिज्म नोट्स संदर्भ सैद्धांतिक कंप्यूटर विज्ञान स्व-संदर्भ लेख उदाहरण के साथ हास्केल कोड लेख उदाहरण के साथ पायथन (प्रोग्रामिंग भाषा) कोड कार्यात्मक प्रोग्रामिंग श्रेणी सिद्धांत रिकर्शन