कोरकर्शन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Type of algorithm in computer science}}
{{Short description|Type of algorithm in computer science}}
{{distinguish|Mutual recursion}}
{{distinguish| म्यूच्यूअल रेकरसन }}
[[कंप्यूटर विज्ञान]] में, कोरकर्सन प्रकार का ऑपरेशन है जो दोहरी (श्रेणी सिद्धांत) से [[रिकर्सन (कंप्यूटर विज्ञान)]] है। जबकि रिकर्सन विश्लेषणात्मक रूप से काम करता है, बेस केस से आगे डेटा पर शुरू होता है और इसे छोटे डेटा में तोड़ता है और जब तक कोई बेस केस तक नहीं पहुंच जाता तब तक दोहराता रहता है, कोरकर्शन सिंथेटिक रूप से काम करता है, बेस केस से शुरू होता है और इसे बनाता है, बेस केस से हटाए गए डेटा को पुनरावृत्त रूप से उत्पन्न करता है। सीधे शब्दों में कहें तो, कोरकर्सिव एल्गोरिदम उस डेटा का उपयोग करते हैं जो वे स्वयं उत्पन्न करते हैं, जैसे ही वे उपलब्ध होते हैं, और आवश्यकता होती है, डेटा के और बिट्स का उत्पादन करने के लिए थोड़ा-थोड़ा करके। समान लेकिन विशिष्ट अवधारणा ''जेनरेटिव रिकर्सन#स्ट्रक्चरल बनाम जेनरेटिव रिकर्सन'' है, जिसमें कोरकर्सन और रिकर्सन में निहित निश्चित दिशा का अभाव हो सकता है।
[[कंप्यूटर विज्ञान]] में, '''कोरकर्शन''' एक प्रकार का ऑपरेशन है जो की डयूअल (श्रेणी सिद्धांत) से [[रिकर्सन (कंप्यूटर विज्ञान)]] है। जबकि रिकर्सन विश्लेषणात्मक रूप से कार्य करता है, बेस केस से आगे डेटा पर प्रारंभ होता है और इसे छोटे डेटा में तोड़ता है और जब तक कोई बेस केस तक नहीं पहुंच जाता है, तब तक यह इसे दोहराता रहता है, अतः कोरकर्शन सिंथेटिक रूप से कार्य करता है, जो की बेस केस से प्रारंभ  होता है और इसे बनाता है, बेस केस से हटाए गए डेटा को पुनरावृत्त रूप से उत्पन्न करता है। बेस केस सीधे शब्दों में कहें तो, कोरकर्सिव एल्गोरिदम उस डेटा का उपयोग करते हैं जो वे स्वयं उत्पन्न करते हैं, जैसे ही वे उपलब्ध होते हैं, चूंकि डेटा के और बिट्स का उत्पादन करने के लिए थोड़ा-थोड़ा करके आवश्यकता होते है, समान किन्तु  विशिष्ट अवधारणा ''जेनरेटिव रिकर्सन या स्ट्रक्चरल बनाम जेनरेटिव रिकर्सन'' है, जिसमें कोरकर्शन और रिकर्सन में निहित निश्चित दिशा का अभाव हो सकता है।


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


Corecursion परिणाम के रूप में [[परिमित सेट]] और अनंत सेट डेटा संरचनाओं दोनों का उत्पादन कर सकता है, और स्व-संदर्भ|स्व-संदर्भित डेटा संरचनाओं को नियोजित कर सकता है। संभावित अनंत संरचना का केवल सीमित उपसमुच्चय उत्पन्न करने के लिए, कोरकर्सियन का उपयोग अक्सर [[आलसी मूल्यांकन]] के साथ किया जाता है (एक बार में संपूर्ण अनंत संरचना का उत्पादन करने की कोशिश करने के बजाय)। कोरकर्सियन [[कार्यात्मक प्रोग्रामिंग]] में विशेष रूप से महत्वपूर्ण अवधारणा है, जहां कोरकर्सन और [[कोडाटा (कंप्यूटर विज्ञान)]] [[कुल भाषा]]ओं को अनंत डेटा संरचनाओं के साथ काम करने की अनुमति देते हैं।
इस प्रकार से कोरकर्शन परिणाम के रूप में [[परिमित सेट]] और अनंत सेट डेटा सट्रक्चर दोनों का उत्पादन कर सकता है, और सेल्फ-रेफरेंस  डेटा सट्रक्चर को नियोजित कर सकता है। और संभावित अनंत सट्रक्चर का केवल सीमित उपसमुच्चय उत्पन्न करने के लिए, किन्तु कोरकर्शन  का उपयोग प्रायः  [[आलसी मूल्यांकन|लेजी मूल्यांकन]] के साथ (पुनः संपूर्ण अनंत सट्रक्चर का उत्पादन करने की प्रयास करने के अतिरिक्त) किया जाता है। और कोरकर्शन  [[कार्यात्मक प्रोग्रामिंग|फंक्शनल  प्रोग्रामिंग]] में विशेष रूप से महत्वपूर्ण अवधारणा है, जहां कोरकर्शन और [[कोडाटा (कंप्यूटर विज्ञान)]] [[कुल भाषा|कुल लैंग्वेज]]   को अनंत डेटा सट्रक्चर के साथ कार्य करने की अनुमति देते हैं।


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


=== भाज्य ===
=== फ़ैक्टोरियल ===
पुनरावर्ती का उत्कृष्ट उदाहरण [[ कारख़ाने का |कारख़ाने का]] की गणना करना है, जिसे 0 द्वारा पुनरावर्ती रूप से परिभाषित किया गया है! := 1 और एन! := n × (n - 1)!
इस प्रकार से पुनरावर्ती का उत्कृष्ट उदाहरण [[ कारख़ाने का |फ़ैक्टोरियल]] की गणना करना है, जिसे 0 द्वारा पुनरावर्ती रूप से परिभाषित किया गया है! := 1 और एन! := n × (n - 1)!


किसी दिए गए इनपुट पर इसके परिणाम की पुनरावर्ती गणना करने के लिए, पुनरावर्ती फ़ंक्शन अलग (किसी तरह से छोटे) इनपुट के साथ स्वयं को कॉल करता है (किसी तरह से छोटा) और इस कॉल के परिणाम का उपयोग अपना परिणाम बनाने के लिए करता है। पुनरावर्ती कॉल वही करती है, जब तक कि आधार मामले तक नहीं पहुंच गया हो। इस प्रकार प्रक्रिया में [[कॉल स्टैक]] विकसित होता है। उदाहरण के लिए, fac(3) की गणना करने के लिए, यह पुनरावर्ती रूप से fac(2), fac(1), fac(0) (स्टैक को समाप्त करता है) को कॉल करता है, जिस बिंदु पर पुनरावर्तन fac(0) = 1 के साथ समाप्त होता है, और फिर स्टैक रिवर्स ऑर्डर में खुलता है और परिणामों की गणना कॉल स्टैक के साथ प्रारंभिक कॉल फ्रेम fac(3) पर वापस की जाती है जो अंतिम परिणाम की गणना करने के लिए 3 × 2 = 3 × के रूप में fac(2) = 2 के परिणाम का उपयोग करता है। fac(2) =: fac(3) और अंततः fac(3) = 6 लौटाता है। इस उदाहरण में फ़ंक्शन एकल मान लौटाता है।
चूंकि किसी दिए गए इनपुट पर इसके परिणाम की पुनरावर्ती गणना करने के लिए, पुनरावर्ती फ़ंक्शन अलग (किसी तरह से छोटे) इनपुट के साथ स्वयं को कॉल करता है (किसी तरह से छोटा) और इस कॉल के परिणाम का उपयोग अपना परिणाम बनाने के लिए करता है। पुनरावर्ती कॉल वही करती है, जब तक कि आधार स्तिथि  तक नहीं पहुंच गया हो। इस प्रकार प्रक्रिया में [[कॉल स्टैक]] विकसित होता है। उदाहरण के लिए, fac(3) की गणना करने के लिए, यह पुनरावर्ती रूप से fac(2), fac(1), fac(0) (स्टैक को समाप्त करता है) को कॉल करता है, जिस बिंदु पर पुनरावर्तन fac(0) = 1 के साथ समाप्त होता है, और फिर स्टैक रिवर्स ऑर्डर में ओपन होता  है और परिणामों की गणना कॉल स्टैक के साथ प्रारंभिक कॉल फ्रेम fac(3) पर वापस की जाती है जो अंतिम परिणाम की गणना करने के लिए 3 × 2 = 3 × के रूप में fac(2) = 2 के परिणाम का उपयोग करता है। fac(2) =: fac(3) और अंततः fac(3) = 6 लौटाता है। इस उदाहरण में फ़ंक्शन सिंगल मान लौटाता है।


इस स्टैक अनवाइंडिंग को पुनरावर्तक के रूप में फैक्टोरियल कोरकर्सिव रूप से परिभाषित करते हुए समझा जा सकता है, जहां कोई मामले से शुरू होता है <math>1 =: 0!</math>, फिर इस आरंभिक मान से संख्या 1, 2, 3... को बढ़ाने के लिए भाज्य मानों का निर्माण करता है, जैसा कि उपरोक्त पुनरावर्ती परिभाषा में समय तीर के साथ उलटा है, जैसा कि यह था, इसे पीछे की ओर पढ़कर {{nobreak|<math>n! \times (n+1) =: (n+1)!</math>.}} इस प्रकार परिभाषित कोरकर्सिव एल्गोरिदम सभी फैक्टोरियल की धारा उत्पन्न करता है। इसे जेनरेटर (कंप्यूटर प्रोग्रामिंग) के रूप में ठोस रूप से लागू किया जा सकता है। प्रतीकात्मक रूप से, यह ध्यान में रखते हुए कि अगले भाज्य मान की गणना के लिए n और f (पिछले भाज्य मान) दोनों का ट्रैक रखने की आवश्यकता होती है, इसे इस प्रकार दर्शाया जा सकता है:
इस स्टैक अनवाइंडिंग को पुनरावर्तक के रूप में फैक्टोरियल कोरकर्सिव रूप से परिभाषित करते हुए समझा जा सकता है, जहां कोई स्तिथि  से प्रारंभ  होता है <math>1 =: 0!</math>, फिर इस आरंभिक मान से संख्या 1, 2, 3... को बढ़ाने के लिए फ़ैक्टोरियल मानों का निर्माण करता है, जैसा कि उपरोक्त पुनरावर्ती परिभाषा में टाइम एररो  के साथ रिवर्स होता है, जैसा कि यह था, इसे पीछे की ओर पढ़कर {{nobreak|<math>n! \times (n+1) =: (n+1)!</math>.}} इस प्रकार परिभाषित कोरकर्सिव एल्गोरिदम सभी फैक्टोरियल की धारा उत्पन्न करता है। इसे जेनरेटर (कंप्यूटर प्रोग्रामिंग) के रूप में ठोस रूप से प्रयुक्त  किया जा सकता है। प्रतीकात्मक रूप से, यह ध्यान में रखते हुए कि अगले फ़ैक्टोरियल मान की गणना के लिए n और f (पिछले फ़ैक्टोरियल मान) दोनों का ट्रैक रखने की आवश्यकता होती है, इसे इस प्रकार दर्शाया जा सकता है:
:<math>n, f = (0, 1) : (n + 1, f \times (n+1))</math>
:<math>n, f = (0, 1) : (n + 1, f \times (n+1))</math>
या [[हास्केल (प्रोग्रामिंग भाषा)]] में,
या [[हास्केल (प्रोग्रामिंग भाषा)|हास्केल (प्रोग्रामिंग  लैंग्वेज )]] में,
<syntaxhighlight lang=haskell>
<syntaxhighlight lang=haskell>
   (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)
   (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)
</syntaxhighlight>
</syntaxhighlight>
मतलब, से शुरू <math>n, f = 0, 1</math>, प्रत्येक चरण पर अगले मानों की गणना इस प्रकार की जाती है <math>n+1, f \times (n+1)</math>. यह गणितीय रूप से समतुल्य है और लगभग पुनरावर्ती परिभाषा के समान है, लेकिन <math>+1</math> इस बात पर जोर दिया गया है कि तथ्यात्मक मूल्यों का निर्माण, शुरुआती मामले से आगे की ओर बढ़ते हुए किया जा रहा है, न कि पहले पीछे की ओर जाने के बाद, आधार मामले तक, गणना की जा रही है। <math>-1</math> कमी. कोरकर्सिव फ़ंक्शन के प्रत्यक्ष आउटपुट में केवल फैक्टोरियल शामिल नहीं होता है <math>n!</math> मान, लेकिन अनुक्रम में प्रत्येक मान के लिए उसके सूचकांक n का सहायक डेटा भी शामिल है, ताकि आवश्यकता पड़ने पर उन सभी में से किसी विशिष्ट परिणाम का चयन किया जा सके।


[[सांकेतिक शब्दार्थ]] के साथ संबंध है, जहां पुनरावर्ती कार्यक्रमों के डिनोटेशनल सिमेंटिक्स # मीनिंग को इस तरह से कोरकर्सिव रूप से बनाया जाता है।
 
इसका अर्थ है, कि "प्रत्येक चरण पर <math>n, f = 0, 1</math> से प्रारंभ  करके अगले मानों की गणना <math>n+1, f \times (n+1)</math> के रूप में की जाती है। यह गणितीय रूप से समतुल्य है और लगभग पुनरावर्ती परिभाषा के समान है, किन्तु  <math>+1</math> इस बात पर जोर देता है कि फैक्टोरियल मान बनाए जा रहे हैं, इसके अतिरिक्त  प्रारंभिक  स्तिथि  से आगे बढ़ते हुए। पहले पीछे की ओर जाने के पश्चात, बेस केस के नीचे, <math>-1</math> कमी के साथ गणना की जा रही है। कोरकर्सिव फ़ंक्शन के प्रत्यक्ष आउटपुट में केवल फैक्टोरियल <math>n!</math> मान सम्मिलित  नहीं होते हैं, किन्तु प्रत्येक मान के लिए अनुक्रम में इसके सूचकांक n का सहायक डेटा भी सम्मिलित  होता है।जिससे  आवश्यकता पड़ने पर उन सभी में से किसी एक विशिष्ट परिणाम का चयन किया जा सकता है।
 
 
[[सांकेतिक शब्दार्थ|डिनोटेशनल सिमेंटिक्स]] के साथ संबंध है, जहां पुनरावर्ती फ़ंक्शनों या मीनिंग को इस तरह से कोरकर्सिव रूप से बनाया जाता है।


पायथन में, पुनरावर्ती फैक्टोरियल फ़ंक्शन को इस प्रकार परिभाषित किया जा सकता है:{{efn|Not validating input data.}}
पायथन में, पुनरावर्ती फैक्टोरियल फ़ंक्शन को इस प्रकार परिभाषित किया जा सकता है:{{efn|Not validating input data.}}
Line 34: Line 37:
         return n * factorial(n - 1)
         return n * factorial(n - 1)
</syntaxhighlight>
</syntaxhighlight>
इसे उदाहरण के लिए इस प्रकार कहा जा सकता है <code>factorial(5)</code> 5 की गणना करने के लिए!
इसे उदाहरण के लिए 5! की गणना करने के लिए <code>factorial(5)</code> इस प्रकार कहा जा सकता है:


एक संगत कोरकर्सिव जेनरेटर को इस प्रकार परिभाषित किया जा सकता है:
एक संगत कोरकर्सिव जेनरेटर को इस प्रकार परिभाषित किया जा सकता है:
Line 53: Line 56:
         k, f = k + 1, f * (k + 1)
         k, f = k + 1, f * (k + 1)
</syntaxhighlight>
</syntaxhighlight>
इसके बाद इसे 5 तक फैक्टोरियल तैयार करने के लिए कहा जा सकता है! के जरिए:
इसके पश्चात इसे 5 तक फैक्टोरियल तैयार करने के लिए कहा जा सकता है! के लिए:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
for f in n_factorials(5):
for f in n_factorials(5):
Line 66: Line 69:
     return f
     return f
</syntaxhighlight>
</syntaxhighlight>
जैसा कि यहां आसानी से देखा जा सकता है, यह व्यावहारिक रूप से समतुल्य है (केवल प्रतिस्थापित करके)। <code>return</code> केवल के लिए <code>yield</code> वहां) [[ पूंछ कॉल |पूंछ कॉल]] के लिए संचायक तर्क तकनीक को स्पष्ट लूप में खोलें। इस प्रकार यह कहा जा सकता है कि कोरकर्सियन की अवधारणा, जहां लागू हो, पुनरावर्ती परिभाषाओं द्वारा पुनरावृत्त गणना प्रक्रियाओं के अवतार की व्याख्या है।
 
 
जैसा कि यहां सरलता  से देखा जा सकता है, यह व्यावहारिक रूप से [[ पूंछ कॉल |टेल रिकर्सन]] के लिए संचायक लॉजिक  तकनीक के समान  है (सिर्फ वहां एकमात्र <code>yield</code>के लिए <code>return</code> को प्रतिस्थापित करके), एक स्पष्ट लूप में अन्वौंड कर दिया है। इस प्रकार यह कहा जा सकता है कि कोरकर्शन की अवधारणा, जहां प्रयुक्त हो, पुनरावर्ती परिभाषाओं द्वारा पुनरावृत्त गणना प्रक्रियाओं के एम्बोड़ीमेंट की व्याख्या है।


=== फाइबोनैचि अनुक्रम ===
=== फाइबोनैचि अनुक्रम ===
उसी तरह, फाइबोनैचि अनुक्रम को इस प्रकार दर्शाया जा सकता है:
इस प्रकार से, फाइबोनैचि अनुक्रम को इस प्रकार दर्शाया जा सकता है:
:<math>a, b = (0, 1) : (b, a+b)</math>
:<math>a, b = (0, 1) : (b, a+b)</math>
क्योंकि फाइबोनैचि अनुक्रम क्रम 2 का पुनरावृत्ति संबंध है, कोरकर्सिव संबंध को दो लगातार शब्दों को ट्रैक करना होगा, <math>(b, -)</math> कदम आगे बढ़ने के अनुरूप, और <math>(-, a+b)</math> अगले पद की गणना के अनुरूप। इसके बाद इसे निम्नानुसार लागू किया जा सकता है ([[समानांतर असाइनमेंट]] का उपयोग करके):
क्योंकि फाइबोनैचि अनुक्रम क्रम 2 का पुनरावृत्ति संबंध है, कोरकर्सिव संबंध को दो लगातार शब्दों को ट्रैक करना होगा, <math>(b, -)</math> कदम आगे बढ़ने के अनुरूप, और <math>(-, a+b)</math> अगले पद की गणना के अनुरूप। इसके बाद इसे निम्नानुसार लागू किया जा सकता है ([[समानांतर असाइनमेंट]] का उपयोग करके):
क्योंकि फाइबोनैचि अनुक्रम क्रम 2 का पुनरावृत्ति संबंध है, इसलिए कोरकर्सिव संबंध को दो क्रमिक शब्दों को ट्रैक करना चाहिए, जिसमें <math>(b, -)</math> एक कदम आगे बढ़ने के लिए है, और <math>(-, a+b)</math> अगले पद की गणना करने के लिए है। इसके पश्चात  इसे निम्नानुसार लागू किया जा सकता है ([[समानांतर असाइनमेंट|पैरेलल असाइनमेंट]] का उपयोग करके):
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
def fibonacci_sequence():
def fibonacci_sequence():
Line 81: Line 88:
हास्केल में, <syntaxhighlight lang=haskell> map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )</syntaxhighlight>
हास्केल में, <syntaxhighlight lang=haskell> map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )</syntaxhighlight>


=== [[वृक्ष परिभ्रमण|ट्री ट्रेवर्सल]] ===
[[गहराई-प्रथम|डेप्थ-फर्स्ट]]  दृष्टिकोण के माध्यम से ट्री  ट्रैवर्सल रिकर्सन का उत्कृष्ट उदाहरण है। दोहरी, ब्रेअड्थ-फर्स्ट ट्रैवर्सल को स्वाभाविक रूप से कोरकर्शन के माध्यम से कार्यान्वित किया जा सकता है।


=== [[वृक्ष परिभ्रमण]] ===
पुनरावृत्तीय रूप से, कोई किसी ट्री के रूट नोड को डेटा सट्रक्चर में रखकर उसे पार कर सकता है, फिर उस डेटा सट्रक्चर के साथ पुनरावृत्ति कर सकता है जबकि वह नॉन-एम्प्टी  है, प्रत्येक चरण पर उसमें से पहले नोड को हटा सकता है और हटाए गए नोड के चाइल्ड नोड्स को उस डेटा सट्रक्चर में वापस रख सकता है। यदि डेटा सट्रक्चर स्टैक (अमूर्त डेटा प्रकार) (एलआईएफओ  ) है, तो इससे डेप्थ-फर्स्ट  ट्रैवर्सल प्राप्त होता है, और यदि डेटा सट्रक्चर [[कतार (सार डेटा प्रकार)|स्टैक (सार डेटा प्रकार)]] (FIFO) है, तो इससे ब्रेअड्थ-फर्स्ट ट्रैवर्सल प्राप्त होता है:
[[गहराई-प्रथम]] दृष्टिकोण के माध्यम से वृक्ष ट्रैवर्सल रिकर्सन का उत्कृष्ट उदाहरण है। दोहरी, चौड़ाई-प्रथम ट्रैवर्सल को स्वाभाविक रूप से कोरकर्सियन के माध्यम से कार्यान्वित किया जा सकता है।
 
पुनरावृत्तीय रूप से, कोई किसी पेड़ के रूट नोड को डेटा संरचना में रखकर उसे पार कर सकता है, फिर उस डेटा संरचना के साथ पुनरावृत्ति कर सकता है जबकि वह गैर-रिक्त है, प्रत्येक चरण पर उसमें से पहले नोड को हटा सकता है और हटाए गए नोड के चाइल्ड नोड्स को उस डेटा संरचना में वापस रख सकता है। यदि डेटा संरचना स्टैक (अमूर्त डेटा प्रकार) (LIFO) है, तो इससे गहराई-प्रथम ट्रैवर्सल प्राप्त होता है, और यदि डेटा संरचना [[कतार (सार डेटा प्रकार)]] (FIFO) है, तो इससे चौड़ाई-प्रथम ट्रैवर्सल प्राप्त होता है:
:<math>trav_{nn}(t) = aux_{nn}([t])</math>
:<math>trav_{nn}(t) = aux_{nn}([t])</math>
:<math>aux_{df}([t,\ ...ts]) = val(t) ;\ aux_{df}([\ ...children(t),\ ...ts\ ])</math>
:<math>aux_{df}([t,\ ...ts]) = val(t) ;\ aux_{df}([\ ...children(t),\ ...ts\ ])</math>
:<math>aux_{bf}([t,\ ...ts]) = val(t) ;\ aux_{bf}([\ ...ts,\ ...children(t)\ ])</math>
:<math>aux_{bf}([t,\ ...ts]) = val(t) ;\ aux_{bf}([\ ...ts,\ ...children(t)\ ])</math>
रिकर्सन का उपयोग करते हुए, पेड़ की गहराई-पहली ट्रैवर्सल को रूट नोड के प्रत्येक चाइल्ड नोड्स को बारी-बारी से पुनरावर्ती रूप से ट्रैवर्स करने के रूप में कार्यान्वित किया जाता है। इस प्रकार दूसरे चाइल्ड सबट्री को तब तक संसाधित नहीं किया जाता जब तक कि पहला चाइल्ड सबट्री समाप्त हो जाए। रूट नोड के मूल्य को अलग से नियंत्रित किया जाता है, चाहे पहले बच्चे को ट्रैवर्स करने से पहले (परिणामस्वरूप प्री-ऑर्डर ट्रैवर्सल), पहले के समाप्त होने के बाद और दूसरे (इन-ऑर्डर) से पहले, या दूसरे चाइल्ड नोड के समाप्त होने के बाद (पोस्ट-ऑर्डर) - यह मानते हुए कि पेड़ द्विआधारी है, अभिव्यक्ति की सरलता के लिए। कॉल स्टैक (पुनरावर्ती ट्रैवर्सल फ़ंक्शन इनवोकेशन का) उस स्टैक से मेल खाता है जिसे ऊपर उल्लिखित स्पष्ट LIFO संरचना हेरफेर के साथ पुनरावृत्त किया जाएगा। प्रतीकात्मक रूप से,
रिकर्सन का उपयोग करते हुए, ट्री की गहराई-पहली ट्रैवर्सल को रूट नोड के प्रत्येक चाइल्ड नोड्स को बारी-बारी से पुनरावर्ती रूप से ट्रैवर्स करने के रूप में कार्यान्वित किया जाता है। इस प्रकार दूसरे चाइल्ड सबट्री को तब तक संसाधित नहीं किया जाता जब तक कि प्रथम चाइल्ड सबट्री समाप्त नहीं हो जाता है। रूट नोड के मूल्य को अलग से नियंत्रित किया जाता है, चाहे प्रथम चाइल्ड को ट्रैवर्स करने से पुनः (परिणामस्वरूप प्री-ऑर्डर ट्रैवर्सल), पूर्व के समाप्त होने के पश्चातऔर दूसरे (इन-ऑर्डर) से पुनः , या द्वतीय चाइल्ड नोड के समाप्त होने के पश्चात (पोस्ट-ऑर्डर) - यह मानते हुए कि ट्री द्विआधारी है, अभिव्यक्ति की सिंपल ता के लिए। इस प्रकार से कॉल स्टैक (पुनरावर्ती ट्रैवर्सल फ़ंक्शन इनवोकेशन का) उस स्टैक से मेल खाता है जिसे ऊपर उल्लिखित स्पष्ट एलआईएफओ  सट्रक्चर परिवर्तन  के साथ प्रतीकात्मक रूप से, पुनरावृत्त किया जाता है।
:<math>df_{in}(t) = [\ ...df_{in}(left(t)),\ val(t),\ ...df_{in}(right(t))\ ]</math>
:<math>df_{in}(t) = [\ ...df_{in}(left(t)),\ val(t),\ ...df_{in}(right(t))\ ]</math>
<!--
<!--
Line 96: Line 102:
:<math>df_{pre}(t) = [\ val(t),\ ...df_{pre}(left(t)),\ ...df_{pre}(right(t))\ ]</math>
:<math>df_{pre}(t) = [\ val(t),\ ...df_{pre}(left(t)),\ ...df_{pre}(right(t))\ ]</math>
:<math>df_{post}(t) = [\ ...df_{post}(left(t)),\ ...df_{post}(right(t)),\ val(t)\ ]</math>
:<math>df_{post}(t) = [\ ...df_{post}(left(t)),\ ...df_{post}(right(t)),\ val(t)\ ]</math>
यहाँ प्रत्यावर्तन के दो अर्थ हैं। सबसे पहले, ट्री ट्रैवर्सल फ़ंक्शंस का पुनरावर्ती आह्वान <math>df_{xyz}</math>. अधिक प्रासंगिक रूप से, हमें इस बात पर विचार करने की आवश्यकता है कि मूल्यों की परिणामी सूची यहां कैसे बनाई जाती है। पुनरावर्ती, बॉटम-अप आउटपुट निर्माण के परिणामस्वरूप दाएं से बाएं ट्री ट्रैवर्सल होगा। इसे वास्तव में बाएँ से दाएँ क्रम में निष्पादित करने के लिए अनुक्रमण को कुछ बाहरी माध्यमों से लागू करने की आवश्यकता होगी, या यदि आउटपुट को ऊपर से नीचे फैशन में बनाया जाना था, यानी कोरकर्सिव तरीके से, तो यह स्वचालित रूप से प्राप्त किया जाएगा।
जहाँ प्रत्यावर्तन के दो अर्थ हैं। सर्वप्रथम, ट्री ट्रैवर्सल फ़ंक्शंस <math>df_{xyz}</math> का पुनरावर्ती आह्वान. अधिक प्रासंगिक रूप से, हमें इस तथ्य पर विचार करने की आवश्यकता है कि मूल्यों की परिणामी सूची यहां कैसे बनाई जाती है। पुनरावर्ती, बॉटम-अप आउटपुट निर्माण के परिणामस्वरूप दाएं से बाएं ट्री ट्रैवर्सल होगा। इसे वास्तव में बाएँ से दाएँ क्रम में निष्पादित करने के लिए अनुक्रमण को कुछ बाहरी माध्यमों से प्रयुक्त  करने की आवश्यकता होगी, या यदि आउटपुट को ऊपर से नीचे फैशन में बनाया जाना था, अर्थात  कोरकर्सिव विधि  से, तो यह स्वचालित रूप से प्राप्त किया जाएगा।


एक चौड़ाई-प्रथम ट्रैवर्सल, जो ऊपर से नीचे के क्रम में अपना आउटपुट बनाता है, कोरकर्सिव रूप से, रूट नोड से शुरू करके, इसके मूल्य को आउटपुट करके भी कार्यान्वित किया जा सकता है,{{efn|Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.}} फिर चौड़ाई-पहले उप-वृक्षों को पार करना - यानी, उप-वृक्षों की पूरी सूची को अगले चरण पर भेजना (एक भी उप-वृक्ष नहीं, जैसा कि पुनरावर्ती दृष्टिकोण में होता है) - अगले चरण में उनके सभी रूट नोड्स के मूल्यों को आउटपुट करना, फिर उनके बच्चे उप-वृक्षों को पार करना, आदि।{{efn|Technically, one may define a breadth-first traversal on an ordered, disconnected set of trees – first the root node of each tree, then the children of each tree in turn, then the grandchildren in turn, etc.}} इस मामले में जनरेटर फ़ंक्शन, वास्तव में आउटपुट अनुक्रम ही, कतार के रूप में कार्य करता है। जैसा कि उपरोक्त तथ्यात्मक उदाहरण में है, जहां सूचकांक की सहायक जानकारी (जो चरण पर था, एन) को एन के वास्तविक आउटपुट के अलावा आगे बढ़ाया गया था, इस मामले में वास्तविक आउटपुट के अलावा, शेष उपवृक्षों की सहायक जानकारी को आगे बढ़ाया गया है। प्रतीकात्मक रूप से,
एक ब्रेअड्थ-फर्स्ट ट्रैवर्सल, जो ऊपर से नीचे के क्रम में अपना आउटपुट बनाता है, कोरकर्सिव रूप से, रूट नोड से प्रारंभ  करके, इसके मूल्य को आउटपुट करके भी कार्यान्वित किया जा सकता है,{{efn|Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.}} फिर चौड़ाई-पहले सब-ट्री  को पार करना - अर्थात , सब-ट्री की पूर्ण सूची को अगले चरण पर भेजना (एक भी सब-ट्री  नहीं, जैसा कि पुनरावर्ती दृष्टिकोण में होता है) - अगले चरण में उनके सभी रूट नोड्स के मूल्यों को आउटपुट करना, फिर उनके चाइल्ड  सब-ट्री  को पास करना आदि।{{efn|Technically, one may define a breadth-first traversal on an ordered, disconnected set of trees – first the root node of each tree, then the children of each tree in turn, then the grandchildren in turn, etc.}} इस स्तिथि  में जनरेटर फ़ंक्शन, वास्तव में आउटपुट अनुक्रम ही, क्रम  के रूप में कार्य करता है। जैसा कि उपरोक्त तथ्यात्मक उदाहरण में है, जहां सूचकांक की सहायक जानकारी (जो चरण पर था, n) को ''n''! के वास्तविक आउटपुट के अतिरिक्त  आगे बढ़ाया गया था, इस स्तिथि में प्रतीकात्मक रूप से वास्तविक आउटपुट के अतिरिक्त, शेष सब-ट्री की सहायक जानकारी को आगे बढ़ाया गया है।  
:<math>v, ts = ([], [FullTree]) : (RootValues(ts), ChildTrees(ts))</math>
 
इसका मतलब है कि प्रत्येक चरण में, इस स्तर के नोड्स में मानों की सूची आउटपुट होती है, फिर अगले स्तर के नोड्स पर आगे बढ़ती है। इस अनुक्रम से केवल नोड मान उत्पन्न करने के लिए सहायक चाइल्ड ट्री डेटा को त्यागने की आवश्यकता होती है, फिर सूचियों की सूची को समतल करना (मानों को शुरू में स्तर (गहराई) द्वारा समूहीकृत किया जाता है; समतल करना (अनग्रुपिंग) सपाट रैखिक सूची उत्पन्न करता है)। यह विस्तारतः के समतुल्य है <math>aux_{bf}</math> उपरोक्त विशिष्टता. हास्केल में,
<math>v, ts = ([], [FullTree]) : (RootValues(ts), ChildTrees(ts))</math>
 
इसका अर्थ है कि प्रत्येक चरण में, इस स्तर के नोड्स में मानों की सूची आउटपुट होती है, फिर अगले स्तर के नोड्स पर आगे बढ़ती है। इस अनुक्रम से केवल नोड मान उत्पन्न करने के लिए सहायक चाइल्ड ट्री डेटा को त्यागने की आवश्यकता होती है, फिर सूचियों की सूची को समतल करना (मानों को प्रारंभ  में स्तर (डेप्थ) द्वारा समूहीकृत किया जाता है; समतल करना (अनग्रुपिंग) सपाट रैखिक सूची उत्पन्न करता है)। यह विस्तृत रूप से उपरोक्त <math>aux_{bf}</math> विनिर्देशन के समतुल्य है। हास्केल में
<syntaxhighlight lang=haskell> concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )</syntaxhighlight>
<syntaxhighlight lang=haskell> concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )</syntaxhighlight>
उल्लेखनीय रूप से, अनंत वृक्ष दिया गया है,{{efn|Assume fixed [[branching factor]] (e.g., binary), or at least bounded, and balanced (infinite in every direction).}} कोरकर्सिव चौड़ाई-प्रथम ट्रैवर्सल सभी नोड्स को पार करेगा, जैसे कि सीमित पेड़ के लिए, जबकि पुनरावर्ती गहराई-पहला ट्रैवर्सल शाखा से नीचे जाएगा और सभी नोड्स को पार नहीं करेगा, और वास्तव में यदि पोस्ट-ऑर्डर को ट्रैवर्स करता है, जैसा कि इस उदाहरण (या इन-ऑर्डर) में है, तो यह बिल्कुल भी नोड्स पर नहीं जाएगा, क्योंकि यह कभी भी पत्ते तक नहीं पहुंचता है। यह अनंत डेटा संरचनाओं से निपटने के लिए रिकर्सन के बजाय कोरकर्सन की उपयोगिता को दर्शाता है। अनंत शाखा कारक वाले पेड़ों के लिए चेतावनी अभी भी बनी हुई है, जिन्हें अंतरिक्ष को बेहतर ढंग से तलाशने के लिए अधिक सावधानीपूर्वक इंटरलेसिंग की आवश्यकता है। डोवेटेलिंग (कंप्यूटर विज्ञान) देखें।
इस प्रकार से उल्लेखनीय रूप से, अनंत ट्री  दिया गया है,{{efn|Assume fixed [[branching factor]] (e.g., binary), or at least bounded, and balanced (infinite in every direction).}} कोरकर्सिव ब्रेअड्थ-फर्स्ट ट्रैवर्सल सभी नोड्स को पार करेगा, जैसे कि सीमित ट्री के लिए, जबकि पुनरावर्ती डेप्थ-फर्स्ट ट्रैवर्सल शाखा से नीचे जाएगा और सभी नोड्स को पार नहीं करेगा, और वास्तव में यदि पोस्ट-ऑर्डर को ट्रैवर्स करता है, जैसा कि इस उदाहरण (या इन-ऑर्डर) में है, तो यह बिल्कुल भी नोड्स पर नहीं जाएगा, क्योंकि यह कभी भी पत्ते तक नहीं पहुंचता है। यह अनंत डेटा सट्रक्चर से निपटने के लिए रिकर्सन के अतिरिक्त  कोरकर्शन की उपयोगिता को दर्शाता है। अनंत शाखा कारक वाले ट्री के लिए चेतावनी अभी भी बनी हुई है, जिन्हें अंतरिक्ष को उत्तम रूप से खोजने के लिए अधिक सावधानीपूर्वक इंटरलेसिंग की आवश्यकता है। डोवेटेलिंग (कंप्यूटर विज्ञान) देखें।


पायथन में, इसे निम्नानुसार कार्यान्वित किया जा सकता है।{{efn|First defining a tree class, say via:
अतः पायथन में, इसे निम्नानुसार कार्यान्वित किया जा सकता है।{{efn|First defining a tree class, say via:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
class Tree:
class Tree:
Line 125: Line 133:
}}
}}


सामान्य पोस्ट-ऑर्डर गहराई-प्रथम ट्रैवर्सल को इस प्रकार परिभाषित किया जा सकता है:{{efn|Intuitively, the function iterates over subtrees (possibly empty), then once these are finished, all that is left is the node itself, whose value is then returned; this corresponds to treating a leaf node as basic.}}
सामान्य पोस्ट-ऑर्डर डेप्थ-फर्स्ट  ट्रैवर्सल को इस प्रकार परिभाषित किया जा सकता है:{{efn|Intuitively, the function iterates over subtrees (possibly empty), then once these are finished, all that is left is the node itself, whose value is then returned; this corresponds to treating a leaf node as basic.}}
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
def df(node):
def df(node):
Line 134: Line 142:
         print(node.value)
         print(node.value)
</syntaxhighlight>
</syntaxhighlight>
इसके बाद इसे कॉल किया जा सकता है <code>df(t)</code> ट्री के नोड्स के मानों को पोस्ट-ऑर्डर गहराई-प्रथम क्रम में मुद्रित करने के लिए।
इसके पश्चात इसे पोस्ट-ऑर्डर  डेप्थ-फर्स्ट क्रम में ट्री  के नोड्स के मानों को मुद्रित करने के लिए <code>df(t)</code> द्वारा कॉल किया जा सकता है।


चौड़ाई-प्रथम कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता है:{{efn|1=Here the argument (and loop variable) is considered as a whole, possible infinite tree, represented by (identified with) its root node (tree = root node), rather than as a potential leaf node, hence the choice of variable name.}}
ब्रेअड्थ-फर्स्ट कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता है:{{efn|1=Here the argument (and loop variable) is considered as a whole, possible infinite tree, represented by (identified with) its root node (tree = root node), rather than as a potential leaf node, hence the choice of variable name.}}
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
def bf(tree):
def bf(tree):
Line 150: Line 158:
         tree_list = new_tree_list
         tree_list = new_tree_list
</syntaxhighlight>
</syntaxhighlight>
इसके बाद इसे पेड़ के नोड्स के मानों को चौड़ाई-पहले क्रम में मुद्रित करने के लिए कहा जा सकता है:
इसके पश्चात इसे ट्री के नोड्स के मानों को ब्रेअड्थ-फर्स्ट क्रम में मुद्रित करने के लिए कहा जा सकता है:
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
for i in bf(t):
for i in bf(t):
Line 158: Line 166:


==परिभाषा==
==परिभाषा==
प्रारंभिक और टर्मिनल वस्तुओं को कुछ प्रकार के समीकरण के सबसे [[कम से कम निर्धारण बिंदु]] ([[ समाकृतिकता | समाकृतिकता]] तक) के रूप में परिभाषित किया जा सकता है; समरूपता तब [[प्रारंभिक बीजगणित]] द्वारा दी जाती है। दोहरी रूप से, अंतिम (या टर्मिनल) डेटा प्रकारों को प्रकार के समीकरण के सबसे बड़े निर्धारण बिंदु के रूप में परिभाषित किया जा सकता है; फिर समरूपता को अंतिम [[ कोलजेब्रा में |कोलजेब्रा में]] द्वारा दिया जाता है।
प्रारंभिक और टर्मिनल वस्तुओं को कुछ प्रकार के समीकरण के अधिक  [[कम से कम निर्धारण बिंदु|लीस्ट फिक्सपॉइंट]] ([[ समाकृतिकता | आइसोमोर्फिज्म]] तक) के रूप में परिभाषित किया जा सकता है; आइसोमोर्फिज्म तब [[प्रारंभिक बीजगणित]] द्वारा दी जाती है। दोहरी रूप से, अंतिम (या टर्मिनल) डेटा प्रकारों को प्रकार के समीकरण के अधिक उच्च निर्धारण बिंदु के रूप में परिभाषित किया जा सकता है; फिर समरूपता को अंतिम [[ कोलजेब्रा में |कोलजेब्रा में]] द्वारा दिया जाता है।
 
यदि प्रवचन का क्षेत्र सेट और कुल कार्यों की श्रेणी है, तो अंतिम डेटा प्रकारों में अनंत, [[गैर-अच्छी तरह से स्थापित सेट सिद्धांत|नॉन-वेलफाउंडेड  मूल्य]]  सम्मिलित  हो सकते हैं, जबकि प्रारंभिक प्रकारों में ऐसा नहीं होता है।<ref>Barwise and Moss 1996.</ref><ref>Moss and Danner 1997.</ref> दूसरी ओर, यदि प्रवचन का क्षेत्र [[पूर्ण आंशिक आदेश|कॉम्पलेट पार्शियल ऑर्डर्स]]  और [[स्कॉट निरंतरता]] की श्रेणी है, सामान्य रूप से हास्केल (प्रोग्रामिंग लैंग्वेज ) प्रोग्रामिंग लैंग्वेज से मेल खाती है, तो अंतिम प्रकार प्रारंभिक प्रकारों के साथ मेल खाते हैं, और संबंधित अंतिम कोलजेब्रा और प्रारंभिक बीजगणित आइसोमोर्फिज्म बनाते हैं।<ref>Smyth and Plotkin 1982.</ref>


यदि प्रवचन का क्षेत्र सेट और कुल कार्यों की श्रेणी है, तो अंतिम डेटा प्रकारों में अनंत, [[गैर-अच्छी तरह से स्थापित सेट सिद्धांत]] | गैर-अच्छी तरह से स्थापित मूल्य शामिल हो सकते हैं, जबकि प्रारंभिक प्रकारों में ऐसा नहीं होता है।<ref>Barwise and Moss 1996.</ref><ref>Moss and Danner 1997.</ref> दूसरी ओर, यदि प्रवचन का क्षेत्र [[पूर्ण आंशिक आदेश]] और [[स्कॉट निरंतरता]] की श्रेणी है, जो मोटे तौर पर हास्केल (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा से मेल खाती है, तो अंतिम प्रकार प्रारंभिक प्रकारों के साथ मेल खाते हैं, और संबंधित अंतिम कोलजेब्रा और प्रारंभिक बीजगणित आइसोमोर्फिज्म बनाते हैं।<ref>Smyth and Plotkin 1982.</ref>
कोरकर्शन  उन कार्यों को पुनरावर्ती रूप से परिभाषित करने की तकनीक है जिनकी सीमा (कोडोमेन) अंतिम डेटा प्रकार है, जिस प्रकार से सामान्य पुनरावर्ती उन कार्यों को पुनरावर्ती रूप से परिभाषित करता है जिनका डोमेन प्रारंभिक डेटा प्रकार है।<ref>Gibbons and Hutton 2005.</ref>


कोरकर्सियन उन कार्यों को पुनरावर्ती रूप से परिभाषित करने की तकनीक है जिनकी सीमा (कोडोमेन) अंतिम डेटा प्रकार है, जिस तरह से सामान्य पुनरावर्ती उन कार्यों को पुनरावर्ती रूप से परिभाषित करता है जिनका डोमेन प्रारंभिक डेटा प्रकार है।<ref>Gibbons and Hutton 2005.</ref>
नीचे दी गई डिस्कशन  हास्केल में अनेक  उदाहरण प्रदान करती है जो कोरकर्शन  को अलग करती है। सामान्य रूप से कहें तो, यदि कोई इन परिलैंग्वेज  को सेट की श्रेणी में पोर्ट कर दे, तो भी वे कोरकर्सिव होंगी। यह अनौपचारिक उपयोग हास्केल के बारे में उपस्तिथ  पाठ्यपुस्तकों के अनुरूप है।<ref>Doets and van Eijck 2004.</ref> इस आलेख में उपयोग किए गए उदाहरण कोरकर्शन को परिभाषित करने और यह क्या है, यह समझाने के प्रयासों से पूर्व के हैं।
नीचे दी गई चर्चा हास्केल में कई उदाहरण प्रदान करती है जो कोरकर्सियन को अलग करती है। मोटे तौर पर कहें तो, अगर कोई इन परिभाषाओं को सेट की श्रेणी में पोर्ट कर दे, तो भी वे कोरकर्सिव होंगी। यह अनौपचारिक उपयोग हास्केल के बारे में मौजूदा पाठ्यपुस्तकों के अनुरूप है।<ref>Doets and van Eijck 2004.</ref> इस आलेख में उपयोग किए गए उदाहरण कोरकर्शन को परिभाषित करने और यह क्या है, यह समझाने के प्रयासों से पहले के हैं।


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


कॉक में स्ट्रीम के साथ प्रोग्रामिंग में: केस स्टडी: एराटोस्थनीज की छलनी<ref>Leclerc and Paulin-Mohring, 1994</ref> हम देखतें है
कॉक में स्ट्रीम के साथ प्रोग्रामिंग में: केस स्टडी: एराटोस्थनीज की सीव <ref>Leclerc and Paulin-Mohring, 1994</ref> हम देखतें है
<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
hd (conc a s) = a               
hd (conc a s) = a               
Line 179: Line 188:
tl (primes s) = primes (sieve (hd s) (tl s))
tl (primes s) = primes (sieve (hd s) (tl s))
</syntaxhighlight>
</syntaxhighlight>
जहां प्राइम्स ऑपरेशन को स्ट्रीम (एनु 2) पर लागू करके प्राइम प्राप्त किए जाते हैं। उपर्युक्त नोटेशन के बाद, अभाज्य संख्याओं का अनुक्रम (इसके साथ 0 उपसर्ग लगाया गया है) और संख्या धाराओं को उत्तरोत्तर छाना जा सकता है, इसे इस प्रकार दर्शाया जा सकता है
जहां प्राइम्स ऑपरेशन को स्ट्रीम (Enu 2) पर प्रयुक्त  करके प्राइम प्राप्त किए जाते हैं। उपर्युक्त नोटेशन के पश्चात , अफ़ैक्टोरियल संख्याओं का अनुक्रम (इसके साथ 0 उपसर्ग लगाया गया है) और संख्या धाराओं को उत्तरोत्तर छाना जा सकता है, इसे इस प्रकार दर्शाया जा सकता है
:<math>p, s = (0, [2..]) : (hd(s), sieve(hd(s),tl(s)))</math>
:<math>p, s = (0, [2..]) : (hd(s), sieve(hd(s),tl(s)))</math>
या हास्केल में,
या हास्केल में,
Line 185: Line 194:
(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])
(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])
</syntaxhighlight>
</syntaxhighlight>
लेखक चर्चा करते हैं कि इसकी परिभाषा कैसी है <code>sieve</code> हमेशा उत्पादक होने की गारंटी नहीं है, और अटक सकता है उदाहरण के लिए। अगर साथ बुलाया जाए <code>[5,10..]</code> प्रारंभिक धारा के रूप में.


यहाँ हास्केल में और उदाहरण है। निम्नलिखित परिभाषा रैखिक समय में फाइबोनैचि संख्याओं की सूची तैयार करती है:
 
लेखक इस संवाद पर डिस्कशन करते हैं कि कैसे <code>sieve</code> की परिभाषा सदैव  उत्पादक होने का प्रमाण नहीं देती है, और स्टुक सकती है, उदाहरण के लिए यदि प्रारंभिक स्ट्रीम के रूप में <code>[5,10..]</code>  के साथ कॉल किया जाता है।
 
जहाँ हास्केल में और उदाहरण है। निम्नलिखित परिभाषा रैखिक समय में फाइबोनैचि संख्याओं की सूची तैयार करती है:
<syntaxhighlight lang=haskell>
<syntaxhighlight lang=haskell>
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
</syntaxhighlight>
</syntaxhighlight>
यह अनंत सूची आलसी मूल्यांकन पर निर्भर करती है; तत्वों की गणना आवश्यकतानुसार की जाती है, और केवल परिमित उपसर्गों को ही स्मृति में स्पष्ट रूप से दर्शाया जाता है। यह सुविधा कोडाटा के कुछ हिस्सों पर एल्गोरिदम को समाप्त करने की अनुमति देती है; ऐसी तकनीकें हास्केल प्रोग्रामिंग का महत्वपूर्ण हिस्सा हैं।
यह अनंत सूची लेजी  मूल्यांकन पर निर्भर करती है; तत्वों की गणना आवश्यकतानुसार की जाती है, और केवल परिमित उपसर्गों को ही मेमोरी  में स्पष्ट रूप से दर्शाया जाता है। यह सुविधा कोडाटा के कुछ हिस्सों पर एल्गोरिदम को समाप्त करने की अनुमति देती है; ऐसी तकनीकें हास्केल प्रोग्रामिंग का महत्वपूर्ण भाग हैं।


इसे पायथन में भी किया जा सकता है:<ref>Hettinger 2009.</ref>
इसे पायथन में भी किया जा सकता है:<ref>Hettinger 2009.</ref>
Line 212: Line 223:
     print(i)
     print(i)
</syntaxhighlight>
</syntaxhighlight>
की परिभाषा <code>zipWith</code> इनलाइन किया जा सकता है, जिससे यह हो सकता है:
 
 
<code>zipWith</code> की परिभाषा को रेखांकित किया जा सकता है, जिससे यह हो सकता है:


<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
Line 219: Line 232:
     next (a: t@(b:_)) = (a+b):next t
     next (a: t@(b:_)) = (a+b):next t
</syntaxhighlight>
</syntaxhighlight>
यह उदाहरण स्व-संदर्भित डेटा संरचना को नियोजित करता है। साधारण रिकर्सन स्व-संदर्भित कार्यों का उपयोग करता है, लेकिन स्व-संदर्भित डेटा को समायोजित नहीं करता है। हालाँकि, यह फाइबोनैचि उदाहरण के लिए आवश्यक नहीं है। इसे इस प्रकार पुनः लिखा जा सकता है:
यह उदाहरण सेल्फ-रेफरेंस  डेटा सट्रक्चर को नियोजित करता है। साधारण रिकर्सन सेल्फ-रेफरेंस  कार्यों का उपयोग करता है, किन्तु  सेल्फ-रेफरेंस  डेटा को समायोजित नहीं करता है। चूंकि , यह फाइबोनैचि उदाहरण के लिए आवश्यक नहीं है। इसे इस प्रकार पुनः लिखा जा सकता है:


<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
Line 225: Line 238:
fibgen (x,y) = x : fibgen (y,x+y)  
fibgen (x,y) = x : fibgen (y,x+y)  
</syntaxhighlight>
</syntaxhighlight>
यह परिणाम तैयार करने के लिए केवल स्व-संदर्भित फ़ंक्शन का उपयोग करता है। यदि इसका उपयोग सख्त सूची कंस्ट्रक्टर के साथ किया जाता तो यह भगोड़ा रिकर्सन का उदाहरण होता, लेकिन आलसी मूल्यांकन | गैर-सख्त सूची कंस्ट्रक्टर के साथ यह संरक्षित रिकर्सन धीरे-धीरे अनिश्चित काल तक परिभाषित सूची तैयार करता है।
यह परिणाम तैयार करने के लिए केवल सेल्फ-रेफरेंस  फ़ंक्शन का उपयोग करता है। यदि इसका उपयोग स्ट्रीक सूची कंस्ट्रक्टर के साथ किया जाता तो यह रनवे  रिकर्सन का उदाहरण होता, किन्तु  नान-स्ट्रीक सूची कंस्ट्रक्टर के साथ यह संरक्षित रिकर्सन धीरे-धीरे अनिश्चित काल तक परिभाषित सूची तैयार करता है।


Corecursion को अनंत वस्तु उत्पन्न करने की आवश्यकता नहीं है; कोरकर्सिव कतार<ref>Allison 1989; Smith 2009.</ref> इस घटना का विशेष रूप से अच्छा उदाहरण है। निम्नलिखित परिभाषा बाइनरी ट्री की चौड़ाई-पहली खोज|चौड़ाई-पहली ट्रैवर्सल को रैखिक समय में ऊपर से नीचे के तरीके से उत्पन्न करती है (पहले से ही उल्लेखित फ़्लैटनिंग #ट्री ट्रैवर्सल को शामिल करते हुए):
कोरकर्शन को अनंत वस्तु उत्पन्न करने की आवश्यकता नहीं है; कोरकर्सिव क्रम <ref>Allison 1989; Smith 2009.</ref> इस घटना का विशेष रूप से सही उदाहरण है। निम्नलिखित परिभाषा बाइनरी ट्री की ब्रेअड्थ-फर्स्ट  ट्रैवर्सल को रैखिक समय में ऊपर से नीचे के विधि  से उत्पन्न करती है (पहले से ही उल्लेखित फ़्लैटनिंग या ट्री ट्रैवर्सल को सम्मिलित  करते हुए):


<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
Line 245: Line 258:
-- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]
-- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]
</syntaxhighlight>
</syntaxhighlight>
यह परिभाषा पेड़ लेती है और उसके उप-पेड़ों (नोड्स और पत्तियों) की सूची तैयार करती है। यह सूची इनपुट कतार और परिणाम दोनों के रूप में दोहरे उद्देश्य को पूरा करती है (<small>''<code>gen len p</code>''</small> अपना आउटपुट उत्पन्न करता है <small>''<code>len</code>''</small> इसके इनपुट बैक-पॉइंटर के बाद नॉच, <small>''<code>p</code>''</small>, साथ <small>''<code>queue</code>''</small>). यह तभी सीमित है जब प्रारंभिक वृक्ष सीमित हो। समाप्ति सुनिश्चित करने के लिए कतार की लंबाई को स्पष्ट रूप से ट्रैक किया जाना चाहिए; यदि यह परिभाषा केवल अनंत पेड़ों पर लागू होती है तो इसे सुरक्षित रूप से समाप्त किया जा सकता है। यह हास्केल कोड स्व-संदर्भित डेटा संरचना का उपयोग करता है, लेकिन अनिवार्य रूप से आलसी मूल्यांकन पर निर्भर नहीं करता है। इसका सीधा अनुवाद उदाहरणार्थ किया जा सकता है। प्रोलॉग जो आलसी भाषा नहीं है. जो आवश्यक है वह ऊपर से नीचे तरीके से सूची (कतार के रूप में प्रयुक्त) बनाने की क्षमता है। उसके लिए, प्रोलॉग में टेल कॉल#टेल रिकर्सन मॉड्यूलो कॉन्स (यानी ओपन एंडेड सूचियां) हैं। जो स्कीम, सी, आदि में भी अनुकरणीय है:
यह परिभाषा ट्री लेती है और उसके सब-ट्रीों (नोड्स और पत्तियों) की सूची तैयार करती है। यह सूची इनपुट क्रम  और परिणाम दोनों के रूप में दोहरे उद्देश्य को पूरा करती है (<small>''<code>gen len p</code>''</small> अपना आउटपुट उत्पन्न करता है <small>''<code>len</code>''</small> इसके इनपुट बैक-पॉइंटर के पश्चात  नॉच, <small>''<code>p</code>''</small>, साथ <small>''<code>queue</code>''</small>). यह तभी सीमित है जब प्रारंभिक ट्री  सीमित हो। समाप्ति सुनिश्चित करने के लिए क्रम  की लंबाई को स्पष्ट रूप से ट्रैक किया जाना चाहिए; यदि यह परिभाषा केवल अनंत ट्रीों पर प्रयुक्त  होती है तो इसे सुरक्षित रूप से समाप्त किया जा सकता है। यह हास्केल कोड सेल्फ-रेफरेंस  डेटा सट्रक्चर का उपयोग करता है, किन्तु  अनिवार्य रूप से लेजी  मूल्यांकन पर निर्भर नहीं करता है। इसका सीधा अनुवाद उदाहरणार्थ किया जा सकता है। प्रोलॉग जो लेजी  लैंग्वेज नहीं है. जो आवश्यक है वह ऊपर से नीचे विधि  से सूची (क्रम  के रूप में प्रयुक्त) बनाने की क्षमता है। उसके लिए, प्रोलॉग में टेल कॉल या टेल रिकर्सन मॉड्यूलो कॉन्स (अर्थात  ओपन एंडेड सूचियां) हैं। जो स्कीम, सी, आदि में भी अनुकरणीय है:


<syntaxhighlight lang="prolog">
<syntaxhighlight lang="prolog">
Line 254: Line 267:
%%        ----read----    --write-ahead--
%%        ----read----    --write-ahead--
</syntaxhighlight>
</syntaxhighlight>
एक अन्य विशेष उदाहरण चौड़ाई-प्रथम लेबलिंग की समस्या का समाधान देता है।<ref>Jones and Gibbons 1992.</ref> कार्यक्रम <code>label</code> बाइनरी ट्री में प्रत्येक नोड पर पहले चौड़ाई में जाता है, और प्रत्येक लेबल को पूर्णांक से बदल देता है, प्रत्येक बाद वाला पूर्णांक पिछले पूर्णांक से बड़ा होता है। यह समाधान स्व-संदर्भित डेटा संरचना को नियोजित करता है, और बाइनरी ट्री परिमित या अनंत हो सकता है।
एक अन्य विशेष उदाहरण ब्रेअड्थ-फर्स्ट लेबलिंग की समस्या का समाधान देता है।<ref>Jones and Gibbons 1992.</ref> फ़ंक्शन <code>label</code> बाइनरी ट्री में प्रत्येक नोड पर पूर्व ब्रेअड्थ में जाता है, और प्रत्येक लेबल को पूर्णांक से परिवर्तन कर देता है, प्रत्येक के पश्चात  पूर्णांक पिछले पूर्णांक से उच्च होता है। यह समाधान सेल्फ-रेफरेंस  डेटा सट्रक्चर को नियोजित करता है, और बाइनरी ट्री परिमित या अनंत हो सकता है।


<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
Line 277: Line 290:
   label(R,B,Rn,C).
   label(R,B,Rn,C).
</syntaxhighlight>
</syntaxhighlight>
एक [[अपोमोर्फिज्म]] (जैसे [[ एनामोर्फिज्म |एनामोर्फिज्म]] , जैसे अनफोल्ड (उच्च-क्रम फ़ंक्शन)) उसी तरह से कोरकर्सियन का रूप है जैसे कि [[ सर्वाकृतिवाद |सर्वाकृतिवाद]] (जैसे कि [[ कैटामोर्फिज्म |कैटामोर्फिज्म]] , जैसे फोल्ड (उच्च-ऑर्डर फ़ंक्शन)) रिकर्सन का रूप है।
एक [[अपोमोर्फिज्म]] (जैसे [[ एनामोर्फिज्म |एनामोर्फिज्म]] , जैसे अनफोल्ड (उच्च-क्रम फ़ंक्शन)) उसी प्रकार से कोरकर्शन  का रूप है जैसे कि [[ सर्वाकृतिवाद |सर्वाकृतिवाद]] (जैसे कि [[ कैटामोर्फिज्म |कैटामोर्फिज्म]] , जैसे फोल्ड (उच्च-ऑर्डर फ़ंक्शन)) रिकर्सन का रूप है।


[[Coq]] प्रूफ सहायक CoFixpoint कमांड का उपयोग करके कोरकर्सियन और [[संयोग]] का समर्थन करता है।
[[Coq|कॉक]] प्रूफ सहायक सहफिक्सपॉइंट कमांड का उपयोग करके कोरकर्शन  और [[संयोग|कॉइनडक्शन]] का समर्थन करता है।


== इतिहास ==
== इतिहास ==
कोरकर्सियन, जिसे सर्कुलर प्रोग्रामिंग कहा जाता है, कम से कम दिनांकित है {{Harv|Bird|1984}}, जो [[जॉन ह्यूजेस (कंप्यूटर वैज्ञानिक)]] और [[फिलिप वाडलर]] को श्रेय देते हैं; में अधिक सामान्य रूप विकसित किये गये {{Harv|Allison|1989}}. मूल प्रेरणाओं में अधिक कुशल एल्गोरिदम का उत्पादन करना (कुछ मामलों में एकाधिक पास की आवश्यकता के बजाय डेटा पर 1 पास की अनुमति देना) और कार्यात्मक भाषाओं में शास्त्रीय डेटा संरचनाओं, जैसे दोगुनी लिंक की गई सूचियों और कतारों को लागू करना शामिल था।
कोरकर्शन , जिसे सर्कुलर प्रोग्रामिंग कहा जाता है, कम से कम दिनांकित है {{Harv|बर्ड |1984}}, जो [[जॉन ह्यूजेस (कंप्यूटर वैज्ञानिक)]] और [[फिलिप वाडलर]] को श्रेय देते हैं; में अधिक सामान्य रूप विकसित किये गये {{Harv|एलीसन|1989}}. मूल प्रेरणाओं में अधिक कुशल एल्गोरिदम का उत्पादन करना (कुछ स्तिथियों  में एकाधिक समीप की आवश्यकता के अतिरिक्त  डेटा पर 1 पास की अनुमति देना) और फंक्शनल लैंग्वेज  में क्लासिकल  डेटा सट्रक्चरओं, जैसे दोगुनी लिंक की गई सूचियों और क्रम को प्रयुक्त  करना सम्मिलित था।


== यह भी देखें ==
== यह भी देखें ==
* [[द्विसिमुलेशन]]
* [[द्विसिमुलेशन|बीसीमुलेशन]]
*संयोजन
*कॉइनडक्सन
* प्रत्यावर्तन
* रिकरसन
* एनामोर्फिज्म
* एनामोर्फिज्म



Revision as of 12:16, 3 August 2023

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

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

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

उदाहरण

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

फ़ैक्टोरियल

इस प्रकार से पुनरावर्ती का उत्कृष्ट उदाहरण फ़ैक्टोरियल की गणना करना है, जिसे 0 द्वारा पुनरावर्ती रूप से परिभाषित किया गया है! := 1 और एन! := n × (n - 1)!

चूंकि किसी दिए गए इनपुट पर इसके परिणाम की पुनरावर्ती गणना करने के लिए, पुनरावर्ती फ़ंक्शन अलग (किसी तरह से छोटे) इनपुट के साथ स्वयं को कॉल करता है (किसी तरह से छोटा) और इस कॉल के परिणाम का उपयोग अपना परिणाम बनाने के लिए करता है। पुनरावर्ती कॉल वही करती है, जब तक कि आधार स्तिथि तक नहीं पहुंच गया हो। इस प्रकार प्रक्रिया में कॉल स्टैक विकसित होता है। उदाहरण के लिए, fac(3) की गणना करने के लिए, यह पुनरावर्ती रूप से fac(2), fac(1), fac(0) (स्टैक को समाप्त करता है) को कॉल करता है, जिस बिंदु पर पुनरावर्तन fac(0) = 1 के साथ समाप्त होता है, और फिर स्टैक रिवर्स ऑर्डर में ओपन होता है और परिणामों की गणना कॉल स्टैक के साथ प्रारंभिक कॉल फ्रेम fac(3) पर वापस की जाती है जो अंतिम परिणाम की गणना करने के लिए 3 × 2 = 3 × के रूप में fac(2) = 2 के परिणाम का उपयोग करता है। fac(2) =: fac(3) और अंततः fac(3) = 6 लौटाता है। इस उदाहरण में फ़ंक्शन सिंगल मान लौटाता है।

इस स्टैक अनवाइंडिंग को पुनरावर्तक के रूप में फैक्टोरियल कोरकर्सिव रूप से परिभाषित करते हुए समझा जा सकता है, जहां कोई स्तिथि से प्रारंभ होता है , फिर इस आरंभिक मान से संख्या 1, 2, 3... को बढ़ाने के लिए फ़ैक्टोरियल मानों का निर्माण करता है, जैसा कि उपरोक्त पुनरावर्ती परिभाषा में टाइम एररो के साथ रिवर्स होता है, जैसा कि यह था, इसे पीछे की ओर पढ़कर . इस प्रकार परिभाषित कोरकर्सिव एल्गोरिदम सभी फैक्टोरियल की धारा उत्पन्न करता है। इसे जेनरेटर (कंप्यूटर प्रोग्रामिंग) के रूप में ठोस रूप से प्रयुक्त किया जा सकता है। प्रतीकात्मक रूप से, यह ध्यान में रखते हुए कि अगले फ़ैक्टोरियल मान की गणना के लिए n और f (पिछले फ़ैक्टोरियल मान) दोनों का ट्रैक रखने की आवश्यकता होती है, इसे इस प्रकार दर्शाया जा सकता है:

या हास्केल (प्रोग्रामिंग लैंग्वेज ) में,

  (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)


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


डिनोटेशनल सिमेंटिक्स के साथ संबंध है, जहां पुनरावर्ती फ़ंक्शनों या मीनिंग को इस तरह से कोरकर्सिव रूप से बनाया जाता है।

पायथन में, पुनरावर्ती फैक्टोरियल फ़ंक्शन को इस प्रकार परिभाषित किया जा सकता है:[lower-alpha 1]

def factorial(n: int) -> int:
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

इसे उदाहरण के लिए 5! की गणना करने के लिए factorial(5) इस प्रकार कहा जा सकता है:

एक संगत कोरकर्सिव जेनरेटर को इस प्रकार परिभाषित किया जा सकता है:

def factorials():
    """Corecursive generator."""
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)

यह क्रम में फैक्टोरियल की अनंत धारा उत्पन्न करता है; इसका सीमित भाग निम्न द्वारा उत्पादित किया जा सकता है:

def n_factorials(n: int):
    k, f = 0, 1
    while k <= n:
        yield f
        k, f = k + 1, f * (k + 1)

इसके पश्चात इसे 5 तक फैक्टोरियल तैयार करने के लिए कहा जा सकता है! के लिए:

for f in n_factorials(5):
    print(f)

यदि हम केवल निश्चित फैक्टोरियल में रुचि रखते हैं, तो केवल अंतिम मूल्य लिया जा सकता है, या हम उत्पादन और पहुंच को फ़ंक्शन में जोड़ सकते हैं,

def nth_factorial(n: int):
    k, f = 0, 1
    while k < n:
        k, f = k + 1, f * (k + 1)
    return f


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

फाइबोनैचि अनुक्रम

इस प्रकार से, फाइबोनैचि अनुक्रम को इस प्रकार दर्शाया जा सकता है:

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

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

def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

हास्केल में,

 map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )

ट्री ट्रेवर्सल

डेप्थ-फर्स्ट दृष्टिकोण के माध्यम से ट्री ट्रैवर्सल रिकर्सन का उत्कृष्ट उदाहरण है। दोहरी, ब्रेअड्थ-फर्स्ट ट्रैवर्सल को स्वाभाविक रूप से कोरकर्शन के माध्यम से कार्यान्वित किया जा सकता है।

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

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

जहाँ प्रत्यावर्तन के दो अर्थ हैं। सर्वप्रथम, ट्री ट्रैवर्सल फ़ंक्शंस का पुनरावर्ती आह्वान. अधिक प्रासंगिक रूप से, हमें इस तथ्य पर विचार करने की आवश्यकता है कि मूल्यों की परिणामी सूची यहां कैसे बनाई जाती है। पुनरावर्ती, बॉटम-अप आउटपुट निर्माण के परिणामस्वरूप दाएं से बाएं ट्री ट्रैवर्सल होगा। इसे वास्तव में बाएँ से दाएँ क्रम में निष्पादित करने के लिए अनुक्रमण को कुछ बाहरी माध्यमों से प्रयुक्त करने की आवश्यकता होगी, या यदि आउटपुट को ऊपर से नीचे फैशन में बनाया जाना था, अर्थात कोरकर्सिव विधि से, तो यह स्वचालित रूप से प्राप्त किया जाएगा।

एक ब्रेअड्थ-फर्स्ट ट्रैवर्सल, जो ऊपर से नीचे के क्रम में अपना आउटपुट बनाता है, कोरकर्सिव रूप से, रूट नोड से प्रारंभ करके, इसके मूल्य को आउटपुट करके भी कार्यान्वित किया जा सकता है,[lower-alpha 2] फिर चौड़ाई-पहले सब-ट्री को पार करना - अर्थात , सब-ट्री की पूर्ण सूची को अगले चरण पर भेजना (एक भी सब-ट्री नहीं, जैसा कि पुनरावर्ती दृष्टिकोण में होता है) - अगले चरण में उनके सभी रूट नोड्स के मूल्यों को आउटपुट करना, फिर उनके चाइल्ड सब-ट्री को पास करना आदि।[lower-alpha 3] इस स्तिथि में जनरेटर फ़ंक्शन, वास्तव में आउटपुट अनुक्रम ही, क्रम के रूप में कार्य करता है। जैसा कि उपरोक्त तथ्यात्मक उदाहरण में है, जहां सूचकांक की सहायक जानकारी (जो चरण पर था, n) को n! के वास्तविक आउटपुट के अतिरिक्त आगे बढ़ाया गया था, इस स्तिथि में प्रतीकात्मक रूप से वास्तविक आउटपुट के अतिरिक्त, शेष सब-ट्री की सहायक जानकारी को आगे बढ़ाया गया है।

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

 concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )

इस प्रकार से उल्लेखनीय रूप से, अनंत ट्री दिया गया है,[lower-alpha 4] कोरकर्सिव ब्रेअड्थ-फर्स्ट ट्रैवर्सल सभी नोड्स को पार करेगा, जैसे कि सीमित ट्री के लिए, जबकि पुनरावर्ती डेप्थ-फर्स्ट ट्रैवर्सल शाखा से नीचे जाएगा और सभी नोड्स को पार नहीं करेगा, और वास्तव में यदि पोस्ट-ऑर्डर को ट्रैवर्स करता है, जैसा कि इस उदाहरण (या इन-ऑर्डर) में है, तो यह बिल्कुल भी नोड्स पर नहीं जाएगा, क्योंकि यह कभी भी पत्ते तक नहीं पहुंचता है। यह अनंत डेटा सट्रक्चर से निपटने के लिए रिकर्सन के अतिरिक्त कोरकर्शन की उपयोगिता को दर्शाता है। अनंत शाखा कारक वाले ट्री के लिए चेतावनी अभी भी बनी हुई है, जिन्हें अंतरिक्ष को उत्तम रूप से खोजने के लिए अधिक सावधानीपूर्वक इंटरलेसिंग की आवश्यकता है। डोवेटेलिंग (कंप्यूटर विज्ञान) देखें।

अतः पायथन में, इसे निम्नानुसार कार्यान्वित किया जा सकता है।[lower-alpha 5]

सामान्य पोस्ट-ऑर्डर डेप्थ-फर्स्ट ट्रैवर्सल को इस प्रकार परिभाषित किया जा सकता है:[lower-alpha 6]

def df(node):
    """Post-order depth-first traversal."""
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)

इसके पश्चात इसे पोस्ट-ऑर्डर डेप्थ-फर्स्ट क्रम में ट्री के नोड्स के मानों को मुद्रित करने के लिए df(t) द्वारा कॉल किया जा सकता है।

ब्रेअड्थ-फर्स्ट कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता है:[lower-alpha 7]

def bf(tree):
    """Breadth-first corecursive generator."""
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

इसके पश्चात इसे ट्री के नोड्स के मानों को ब्रेअड्थ-फर्स्ट क्रम में मुद्रित करने के लिए कहा जा सकता है:

for i in bf(t):
    print(i)


परिभाषा

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

यदि प्रवचन का क्षेत्र सेट और कुल कार्यों की श्रेणी है, तो अंतिम डेटा प्रकारों में अनंत, नॉन-वेलफाउंडेड मूल्य सम्मिलित हो सकते हैं, जबकि प्रारंभिक प्रकारों में ऐसा नहीं होता है।[1][2] दूसरी ओर, यदि प्रवचन का क्षेत्र कॉम्पलेट पार्शियल ऑर्डर्स और स्कॉट निरंतरता की श्रेणी है, सामान्य रूप से हास्केल (प्रोग्रामिंग लैंग्वेज ) प्रोग्रामिंग लैंग्वेज से मेल खाती है, तो अंतिम प्रकार प्रारंभिक प्रकारों के साथ मेल खाते हैं, और संबंधित अंतिम कोलजेब्रा और प्रारंभिक बीजगणित आइसोमोर्फिज्म बनाते हैं।[3]

कोरकर्शन उन कार्यों को पुनरावर्ती रूप से परिभाषित करने की तकनीक है जिनकी सीमा (कोडोमेन) अंतिम डेटा प्रकार है, जिस प्रकार से सामान्य पुनरावर्ती उन कार्यों को पुनरावर्ती रूप से परिभाषित करता है जिनका डोमेन प्रारंभिक डेटा प्रकार है।[4]

नीचे दी गई डिस्कशन हास्केल में अनेक उदाहरण प्रदान करती है जो कोरकर्शन को अलग करती है। सामान्य रूप से कहें तो, यदि कोई इन परिलैंग्वेज को सेट की श्रेणी में पोर्ट कर दे, तो भी वे कोरकर्सिव होंगी। यह अनौपचारिक उपयोग हास्केल के बारे में उपस्तिथ पाठ्यपुस्तकों के अनुरूप है।[5] इस आलेख में उपयोग किए गए उदाहरण कोरकर्शन को परिभाषित करने और यह क्या है, यह समझाने के प्रयासों से पूर्व के हैं।

डिस्कशन

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

कॉक में स्ट्रीम के साथ प्रोग्रामिंग में: केस स्टडी: एराटोस्थनीज की सीव [6] हम देखतें है

hd (conc a s) = a               
tl (conc a s) = s

(sieve p s) = if div p (hd s) then sieve p (tl s)
              else conc (hd s) (sieve p (tl s))

hd (primes s) = (hd s)          
tl (primes s) = primes (sieve (hd s) (tl s))

जहां प्राइम्स ऑपरेशन को स्ट्रीम (Enu 2) पर प्रयुक्त करके प्राइम प्राप्त किए जाते हैं। उपर्युक्त नोटेशन के पश्चात , अफ़ैक्टोरियल संख्याओं का अनुक्रम (इसके साथ 0 उपसर्ग लगाया गया है) और संख्या धाराओं को उत्तरोत्तर छाना जा सकता है, इसे इस प्रकार दर्शाया जा सकता है

या हास्केल में,

(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])


लेखक इस संवाद पर डिस्कशन करते हैं कि कैसे sieve की परिभाषा सदैव उत्पादक होने का प्रमाण नहीं देती है, और स्टुक सकती है, उदाहरण के लिए यदि प्रारंभिक स्ट्रीम के रूप में [5,10..] के साथ कॉल किया जाता है।

जहाँ हास्केल में और उदाहरण है। निम्नलिखित परिभाषा रैखिक समय में फाइबोनैचि संख्याओं की सूची तैयार करती है:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

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

इसे पायथन में भी किया जा सकता है:[7]

from itertools import tee, chain, islice, imap

def add(x, y):
    return x + y

def fibonacci():
    def deferred_output():
        for i in output:
            yield i
    result, c1, c2 = tee(deferred_output(), 3)
    paired = imap(add, c1, islice(c2, 1, None))
    output = chain([0, 1], paired)
    return result

for i in islice(fibonacci(), 20):
    print(i)


zipWith की परिभाषा को रेखांकित किया जा सकता है, जिससे यह हो सकता है:

fibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b):next t

यह उदाहरण सेल्फ-रेफरेंस डेटा सट्रक्चर को नियोजित करता है। साधारण रिकर्सन सेल्फ-रेफरेंस कार्यों का उपयोग करता है, किन्तु सेल्फ-रेफरेंस डेटा को समायोजित नहीं करता है। चूंकि , यह फाइबोनैचि उदाहरण के लिए आवश्यक नहीं है। इसे इस प्रकार पुनः लिखा जा सकता है:

fibs = fibgen (0,1)
fibgen (x,y) = x : fibgen (y,x+y)

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

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

data Tree a b = Leaf a
              | Branch b (Tree a b) (Tree a b)

bftrav :: Tree a b -> [Tree a b]
bftrav tree = queue
  where
  queue = tree : gen 1 queue

  gen  0   p                 =         []           
  gen len (Leaf   _     : s) =         gen (len-1) s 
  gen len (Branch _ l r : s) = l : r : gen (len+1) s 
    --        ----read----     ----write-ahead---

-- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]

यह परिभाषा ट्री लेती है और उसके सब-ट्रीों (नोड्स और पत्तियों) की सूची तैयार करती है। यह सूची इनपुट क्रम और परिणाम दोनों के रूप में दोहरे उद्देश्य को पूरा करती है (gen len p अपना आउटपुट उत्पन्न करता है len इसके इनपुट बैक-पॉइंटर के पश्चात नॉच, p, साथ queue). यह तभी सीमित है जब प्रारंभिक ट्री सीमित हो। समाप्ति सुनिश्चित करने के लिए क्रम की लंबाई को स्पष्ट रूप से ट्रैक किया जाना चाहिए; यदि यह परिभाषा केवल अनंत ट्रीों पर प्रयुक्त होती है तो इसे सुरक्षित रूप से समाप्त किया जा सकता है। यह हास्केल कोड सेल्फ-रेफरेंस डेटा सट्रक्चर का उपयोग करता है, किन्तु अनिवार्य रूप से लेजी मूल्यांकन पर निर्भर नहीं करता है। इसका सीधा अनुवाद उदाहरणार्थ किया जा सकता है। प्रोलॉग जो लेजी लैंग्वेज नहीं है. जो आवश्यक है वह ऊपर से नीचे विधि से सूची (क्रम के रूप में प्रयुक्त) बनाने की क्षमता है। उसके लिए, प्रोलॉग में टेल कॉल या टेल रिकर्सन मॉड्यूलो कॉन्स (अर्थात ओपन एंडेड सूचियां) हैं। जो स्कीम, सी, आदि में भी अनुकरणीय है:

bftrav(Tree,Q):- Q=[Tree|R], bfgen(1,Q,R).
bfgen(0,_,[]):- !.  % 0 entries in the queue -- stop and close the list
bfgen(N,[leaf(_)        |P], R       ):- N2 is N-1, bfgen(N2,P,R).
bfgen(N,[branch(_,Lt,Rt)|P],[Lt,Rt|R]):- N2 is N+1, bfgen(N2,P,R).
%%        ----read----    --write-ahead--

एक अन्य विशेष उदाहरण ब्रेअड्थ-फर्स्ट लेबलिंग की समस्या का समाधान देता है।[9] फ़ंक्शन label बाइनरी ट्री में प्रत्येक नोड पर पूर्व ब्रेअड्थ में जाता है, और प्रत्येक लेबल को पूर्णांक से परिवर्तन कर देता है, प्रत्येक के पश्चात पूर्णांक पिछले पूर्णांक से उच्च होता है। यह समाधान सेल्फ-रेफरेंस डेटा सट्रक्चर को नियोजित करता है, और बाइनरी ट्री परिमित या अनंत हो सकता है।

label :: Tree a b -> Tree Int Int 
label t = tn
  where
  (tn, ns) = go t (1:ns)

  go :: Tree a b -> [Int] ->  (Tree Int Int, [Int])
  go (Leaf   _    ) (i:a) = (Leaf   i      , i+1:a)
  go (Branch _ l r) (i:a) = (Branch i ln rn, i+1:c)
       where
       (ln, b) = go l a
       (rn, c) = go r b

या प्रोलॉग में, तुलना के लिए,

label(Tree,Tn):- label(Tree,[1|Ns],Tn,Ns).
label(leaf(_),      [I|A],leaf(  I),      [I+1|A]).
label(branch(_,L,R),[I|A],branch(I,Ln,Rn),[I+1|C]):-
  label(L,A,Ln,B),  
  label(R,B,Rn,C).

एक अपोमोर्फिज्म (जैसे एनामोर्फिज्म , जैसे अनफोल्ड (उच्च-क्रम फ़ंक्शन)) उसी प्रकार से कोरकर्शन का रूप है जैसे कि सर्वाकृतिवाद (जैसे कि कैटामोर्फिज्म , जैसे फोल्ड (उच्च-ऑर्डर फ़ंक्शन)) रिकर्सन का रूप है।

कॉक प्रूफ सहायक सहफिक्सपॉइंट कमांड का उपयोग करके कोरकर्शन और कॉइनडक्शन का समर्थन करता है।

इतिहास

कोरकर्शन , जिसे सर्कुलर प्रोग्रामिंग कहा जाता है, कम से कम दिनांकित है (बर्ड 1984), जो जॉन ह्यूजेस (कंप्यूटर वैज्ञानिक) और फिलिप वाडलर को श्रेय देते हैं; में अधिक सामान्य रूप विकसित किये गये (एलीसन 1989). मूल प्रेरणाओं में अधिक कुशल एल्गोरिदम का उत्पादन करना (कुछ स्तिथियों में एकाधिक समीप की आवश्यकता के अतिरिक्त डेटा पर 1 पास की अनुमति देना) और फंक्शनल लैंग्वेज में क्लासिकल डेटा सट्रक्चरओं, जैसे दोगुनी लिंक की गई सूचियों और क्रम को प्रयुक्त करना सम्मिलित था।

यह भी देखें

टिप्पणियाँ

  1. Not validating input data.
  2. Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.
  3. Technically, one may define a breadth-first traversal on an ordered, disconnected set of trees – first the root node of each tree, then the children of each tree in turn, then the grandchildren in turn, etc.
  4. Assume fixed branching factor (e.g., binary), or at least bounded, and balanced (infinite in every direction).
  5. First defining a tree class, say via:
    class Tree:
        def __init__(self, value, left=None, right=None):
            self.value = value
            self.left  = left
            self.right = right
    
        def __str__(self):
            return str(self.value)
    

    and initializing a tree, say via:

    t = Tree(1, Tree(2, Tree(4), Tree(5)), Tree(3, Tree(6), Tree(7)))
    

    In this example nodes are labeled in breadth-first order:

        1
     2     3
    4 5   6 7
    
  6. Intuitively, the function iterates over subtrees (possibly empty), then once these are finished, all that is left is the node itself, whose value is then returned; this corresponds to treating a leaf node as basic.
  7. Here the argument (and loop variable) is considered as a whole, possible infinite tree, represented by (identified with) its root node (tree = root node), rather than as a potential leaf node, hence the choice of variable name.

संदर्भ

  1. Barwise and Moss 1996.
  2. Moss and Danner 1997.
  3. Smyth and Plotkin 1982.
  4. Gibbons and Hutton 2005.
  5. Doets and van Eijck 2004.
  6. Leclerc and Paulin-Mohring, 1994
  7. Hettinger 2009.
  8. Allison 1989; Smith 2009.
  9. Jones and Gibbons 1992.