कोरकर्शन

Not to be confused with Mutual recursion.

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

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

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

उदाहरण

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

भाज्य

पुनरावर्ती का उत्कृष्ट उदाहरण कारख़ाने का की गणना करना है, जिसे 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=:0!$, फिर इस आरंभिक मान से संख्या 1, 2, 3... को बढ़ाने के लिए भाज्य मानों का निर्माण करता है, जैसा कि उपरोक्त पुनरावर्ती परिभाषा में समय तीर के साथ उलटा है, जैसा कि यह था, इसे पीछे की ओर पढ़कर $n!\times (n+1)=:(n+1)!$. इस प्रकार परिभाषित कोरकर्सिव एल्गोरिदम सभी फैक्टोरियल की धारा उत्पन्न करता है। इसे जेनरेटर (कंप्यूटर प्रोग्रामिंग) के रूप में ठोस रूप से लागू किया जा सकता है। प्रतीकात्मक रूप से, यह ध्यान में रखते हुए कि अगले भाज्य मान की गणना के लिए n और f (पिछले भाज्य मान) दोनों का ट्रैक रखने की आवश्यकता होती है, इसे इस प्रकार दर्शाया जा सकता है:

$n,f=(0,1):(n+1,f\times (n+1))$

या हास्केल (प्रोग्रामिंग भाषा) में,

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

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

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

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

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

इसे उदाहरण के लिए इस प्रकार कहा जा सकता है factorial(5) 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

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

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

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

$a,b=(0,1):(b,a+b)$

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

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) )

वृक्ष परिभ्रमण

गहराई-प्रथम दृष्टिकोण के माध्यम से वृक्ष ट्रैवर्सल रिकर्सन का उत्कृष्ट उदाहरण है। दोहरी, चौड़ाई-प्रथम ट्रैवर्सल को स्वाभाविक रूप से कोरकर्सियन के माध्यम से कार्यान्वित किया जा सकता है।

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

$trav_{nn}(t)=aux_{nn}([t])$

$aux_{df}([t,\ ...ts])=val(t);\ aux_{df}([\ ...children(t),\ ...ts\ ])$

$aux_{bf}([t,\ ...ts])=val(t);\ aux_{bf}([\ ...ts,\ ...children(t)\ ])$

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

$df_{in}(t)=[\ ...df_{in}(left(t)),\ val(t),\ ...df_{in}(right(t))\ ]$

$df_{pre}(t)=[\ val(t),\ ...df_{pre}(left(t)),\ ...df_{pre}(right(t))\ ]$

$df_{post}(t)=[\ ...df_{post}(left(t)),\ ...df_{post}(right(t)),\ val(t)\ ]$

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

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

$v,ts=([],[FullTree]):(RootValues(ts),ChildTrees(ts))$

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

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

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

पायथन में, इसे निम्नानुसार कार्यान्वित किया जा सकता है।

सामान्य पोस्ट-ऑर्डर गहराई-प्रथम ट्रैवर्सल को इस प्रकार परिभाषित किया जा सकता है:

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

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

चौड़ाई-प्रथम कोरकर्सिव जनरेटर को इस प्रकार परिभाषित किया जा सकता है:

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)

परिभाषा

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

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

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

चर्चा

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

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

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))

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

$p,s=(0,[2..]):(hd(s),sieve(hd(s),tl(s)))$

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

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

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

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

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

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

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

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)

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

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

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--

एक अन्य विशेष उदाहरण चौड़ाई-प्रथम लेबलिंग की समस्या का समाधान देता है। कार्यक्रम 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).

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

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

इतिहास

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

यह भी देखें

• द्विसिमुलेशन
• संयोजन
• प्रत्यावर्तन
• एनामोर्फिज्म

संदर्भ

• Bird, Richard Simpson (1984). "Using circular programs to eliminate multiple traversals of data". Acta Informatica. 21 (3): 239–250. doi:10.1007/BF00264249. S2CID 27392591.
• Allison, Lloyd (April 1989). "Circular Programs and Self-Referential Structures". Software: Practice and Experience. 19 (2): 99–109. doi:10.1002/spe.4380190202. S2CID 21298473.
• Geraint Jones and Jeremy Gibbons (1992). Linear-time breadth-first tree algorithms: An exercise in the arithmetic of folds and zips (Technical report). Dept of Computer Science, University of Auckland.
• Jon Barwise; Lawrence S Moss (June 1996). Vicious Circles. Center for the Study of Language and Information. ISBN 978-1-57586-009-1. Archived from the original on 2010-06-21. Retrieved 2011-01-24.
• Lawrence S Moss; Norman Danner (1997). "On the Foundations of Corecursion". Logic Journal of the IGPL. 5 (2): 231–257. CiteSeerX 10.1.1.40.4243. doi:10.1093/jigpal/5.2.231.
• Kees Doets; Jan van Eijck (May 2004). The Haskell Road to Logic, Maths, and Programming. King's College Publications. ISBN 978-0-9543006-9-2.
• David Turner (2004-07-28). "Total Functional Programming". Journal of Universal Computer Science. 10 (7): 751–768. doi:10.3217/jucs-010-07-0751.
• Jeremy Gibbons; Graham Hutton (April 2005). "Proof methods for corecursive programs". Fundamenta Informaticae. 66 (4): 353–366.
• Leon P Smith (2009-07-29), "Lloyd Allison's Corecursive Queues: Why Continuations Matter", The Monad Reader (14): 37–68
• Raymond Hettinger (2009-11-19). "Recipe 576961: Technique for cyclical iteration".
• M. B. Smyth and G. D. Plotkin (1982). "The Category-Theoretic Solution of Recursive Domain Equations" (PDF). SIAM Journal on Computing. 11 (4): 761–783. doi:10.1137/0211062. S2CID 8517995.
• Leclerc, Francois; Paulin-Mohring, Christine (1993). Programming with Streams in Coq: A Case Study: the Sieve of Eratosthenes. Types for Proofs and Programs: International Workshop TYPES '93. Springer-Verlag New York, Inc. pp. 191–212. ISBN 978-3-540-58085-0.