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

Revision as of 07:33, 8 August 2023

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

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

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

उदाहरण

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

फ़ैक्टोरियल

इस प्रकार से पुनरावर्ती का उत्कृष्ट उदाहरण फ़ैक्टोरियल की गणना करना है, जिसे 0 द्वारा पुनरावर्ती रूप से परिभाषित किया गया है !:= 1 और n!:= 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 का सहायक डेटा भी सम्मिलित होता है।जिससे आवश्यकता पड़ने पर उन सभी में से किसी एक विशिष्ट परिणाम का चयन किया जा सकता है।

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

पायथन में, पुनरावर्ती फैक्टोरियल फ़ंक्शन को इस प्रकार परिभाषित किया जा सकता है:^{[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 को प्रतिस्थापित करके), एक स्पष्ट लूप में अन्वौंड कर दिया है। इस प्रकार यह कहा जा सकता है कि कोरकर्शन की अवधारणा, जहां प्रयुक्त हो, पुनरावर्ती परिभाषाओं द्वारा पुनरावृत्त गणना प्रक्रियाओं के एम्बोड़ीमेंट की व्याख्या है।

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

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

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

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

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

पुनरावृत्तीय रूप से, कोई किसी ट्री के रूट नोड को डेटा सट्रक्चर में रखकर उसे पार कर सकता है, फिर उस डेटा सट्रक्चर के साथ पुनरावृत्ति कर सकता है जबकि वह नॉन-एम्प्टी है, प्रत्येक फेज पर उसमें से पहले नोड को हटा सकता है और हटाए गए नोड के चाइल्ड नोड्स को उस डेटा सट्रक्चर में वापस रख सकता है। यदि डेटा सट्रक्चर स्टैक (अमूर्त डेटा प्रकार) (एलआईएफओ ) है, तो इससे डेप्थ-फर्स्ट ट्रैवर्सल प्राप्त होता है, और यदि डेटा सट्रक्चर स्टैक (सार डेटा प्रकार) (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)\ ])

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

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

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

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

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

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

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

इसे पायथन में भी किया जा सकता है:^[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 पास की अनुमति देना) और फंक्शनल लैंग्वेज में क्लासिकल डेटा सट्रक्चरओं, जैसे दोगुनी लिंक की गई सूचियों और क्रम को प्रयुक्त करना सम्मिलित था।

यह भी देखें

बीसीमुलेशन
कॉइनडक्सन
रेकरसन
एनामोर्फिज्म

↑ Not validating input data.
↑ Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.
↑ 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.
↑ Assume fixed branching factor (e.g., binary), or at least bounded, and balanced (infinite in every direction).

↑ 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

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

संदर्भ

↑ Barwise and Moss 1996.
↑ Moss and Danner 1997.
↑ Smyth and Plotkin 1982.
↑ Gibbons and Hutton 2005.
↑ Doets and van Eijck 2004.
↑ Leclerc and Paulin-Mohring, 1994
↑ Hettinger 2009.
↑ Allison 1989; Smith 2009.
↑ Jones and Gibbons 1992.

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.

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

[8] Barwise and Moss 1996.

[9] Moss and Danner 1997.

[10] Smyth and Plotkin 1982.

[11] Gibbons and Hutton 2005.

[12] Doets and van Eijck 2004.

[13] Leclerc and Paulin-Mohring, 1994

[14] Hettinger 2009.

[15] Allison 1989; Smith 2009.

[16] Jones and Gibbons 1992.

[lower-alpha 1]

[lower-alpha 2]

[lower-alpha 3]

[lower-alpha 4]

[lower-alpha 5]

[lower-alpha 6]

[lower-alpha 7]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 07:33, 8 August 2023

Contents

उदाहरण

फ़ैक्टोरियल

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

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

परिभाषा

डिस्कशन

इतिहास

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Revision as of 15:45, 7 August 2023 (view source) alpha>Neeraja m (added Category:Vigyan Ready using HotCat) ← Older edit	Revision as of 07:33, 8 August 2023 (view source) Indicwiki (talk \| contribs) m (6 revisions imported from alpha:कोरकर्शन) Newer edit →
(No difference)

Anonymous

Search

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

Revision as of 07:33, 8 August 2023

उदाहरण

फ़ैक्टोरियल

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

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

परिभाषा

डिस्कशन

इतिहास

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories