पुनरावर्ती डेटा प्रकार

कंप्यूटर प्रोग्रामिंग भाषाओं में एक पुनरावर्ती डेटा प्रकार (जिसे पुनरावर्ती रूप से परिभाषित आगमनात्मक रूप से परिभाषित या आगमनात्मक डेटा प्रकार के रूप में भी जाना जाता है) मानों के लिए एक डेटा प्रकार है जिसमें उसी प्रकार के अन्य मान हो सकते हैं। पुनरावर्ती प्रकार के डेटा को सामान्यतः निर्देशित ग्राफ़ के रूप में देखा जाता है.

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

कभी-कभी आगमनात्मक डेटा प्रकार शब्द का उपयोग बीजगणितीय डेटा प्रकार के लिए किया जाता है जो आवश्यक रूप से पुनरावर्ती नहीं होते हैं।

उदाहरण

See also: पुनरावर्तन (कंप्यूटर विज्ञान) या पुनरावर्ती डेटा संरचनाएं (संरचनात्मक पुनरावर्तन)

हास्केल (प्रोग्रामिंग भाषा) में सूची (कंप्यूटिंग) प्रकार का एक उदाहरण है:

data List a = Nil | Cons a (List a)

यह इंगित करता है कि a की एक सूची या तो एक खाली सूची है या एक 'a' (सूची का प्रमुख) और दूसरी सूची (पूंछ) वाली एक विपक्ष सेल है।

एक अन्य उदाहरण जावा में एक समान रूप से जुड़ा हुआ प्रकार है:

class List<E> {
    E value;
    List<E> next;
}

यह इंगित करता है कि टाइप ई की गैर-खाली सूची में टाइप ई का डेटा सदस्य होता है और शेष सूची के लिए किसी अन्य सूची ऑब्जेक्ट का संदर्भ होता है (या यह इंगित करने के लिए एक शून्य संदर्भ है कि यह सूची का अंत है)।

पारस्परिक रूप से पुनरावर्ती डेटा प्रकार

Further information: पारस्परिक पुनरावर्तन या डेटा प्रकार

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

f: [t[1], ..., t[k]]
t: v f

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

t: v [t[1], ..., t[k]]

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

मानक एमएल में पेड़ और वन डेटा प्रकारों को पारस्परिक रूप से पुनरावर्ती रूप से परिभाषित किया जा सकता है जिससे खाली पेड़ की अनुमति मिलती है:

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

हास्केल में वृक्ष और वन डेटा प्रकारों को समान रूप से परिभाषित किया जा सकता है:

data Tree a = Empty
            | Node (a, Forest a)

data Forest a = Nil
              | Cons (Tree a) (Forest a)

सिद्धांत

प्रकार सिद्धांत में, एक पुनरावर्ती प्रकार का सामान्य रूप μα.T होता है जहां प्रकार चर α प्रकार T में प्रकट हो सकता है और पूरे प्रकार के लिए खड़ा होता है।

उदाहरण के लिए प्राकृतिक संख्या (पीनो अंकगणितीय देखें) को हास्केल डेटाटाइप द्वारा परिभाषित किया जा सकता है:

data Nat = Zero | Succ Nat

टाइप थ्योरी में, हम कहेंगे: $nat=\mu \alpha .1+\alpha$जहां योग प्रकार की दो भुजाएं शून्य और सफल डेटा कंस्ट्रक्टर का प्रतिनिधित्व करती हैं। शून्य कोई तर्क नहीं लेता है (इस प्रकार इकाई प्रकार द्वारा दर्शाया गया है) और सुक एक और नेट (इस प्रकार $nat=\mu \alpha .1+\alpha$ का एक और तत्व) लेता है।

.

पुनरावर्ती प्रकार के दो रूप हैं: तथाकथित आइसोरेकर्सिव प्रकार और समवर्ती प्रकार एक पुनरावर्ती प्रकार की नियमो को कैसे प्रस्तुत किया जाता है और कैसे समाप्त किया जाता है इसके दो रूप अलग-अलग हैं।

इसोरकर्सिव प्रकार

आइसोरेकर्सिव प्रकारों के साथ पुनरावर्ती प्रकार $\mu \alpha .T$ और इसका विस्तार (या अनरोलिंग) $T[\mu \alpha .T/\alpha ]$(जहां अंकन $X[Y/Z]$ इंगित करता है कि Z के सभी उदाहरणों को प्रतिस्थापित किया गया है X में Y के साथ) विशेष शब्द निर्माण के साथ अलग (और अलग) प्रकार हैं जिन्हें सामान्यतः रोल और अनरोल कहा जाता है, जो उनके बीच एक समरूपता बनाते हैं। स्पष्ट होने के लिए: $roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T$ और $unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]$, और ये दोनों प्रतिलोम फलन हैं।

समतुल्य प्रकार

समवर्ती नियमों के तहत, एक पुनरावर्ती प्रकार $\mu \alpha .T$ और इसका अनरोलिंग $T[\mu \alpha .T/\alpha ]$ समान हैं -- अर्थात उन दो प्रकार के व्यंजकों को एक ही प्रकार को दर्शाने के लिए समझा जाता है। वास्तव में समतुल्य प्रकार के अधिकांश सिद्धांत आगे बढ़ते हैं और अनिवार्य रूप से निर्दिष्ट करते हैं कि समान "अनंत विस्तार" वाले दो प्रकार के भाव समकक्ष हैं। इन नियमों के परिणामस्वरूप समरूप प्रकार के प्रकार एक प्रकार की प्रणाली में आइसोरेकर्सिव प्रकार की तुलना में अधिक जटिलता का योगदान करते हैं। एल्गोरिथम समस्याएं जैसे टाइप चेकिंग और टाइप इंट्रेंस इक्वेरिकर्सिव टाइप्स के लिए भी अधिक कठिन हैं। चूंकि सीधी तुलना एक समवर्ती प्रकार पर समझ में नहीं आती है उन्हें ओ (एन लॉग एन) समय में एक कैननिकल रूप में परिवर्तित किया जा सकता है, जिसे आसानी से तुलना की जा सकती है।

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

पुनरावर्ती प्रकार समानार्थक शब्द

टाइपप्रति के प्रकार उपनाम में पुनरावर्तन की अनुमति है। निम्नलिखित उदाहरण की अनुमति है।

type Tree = number | Tree[];
let tree: Tree = [1, [2, 3]];

चूँकि मिरांडा प्रोग्रामिंग भाषा, ओ कैमल (जब तक -rectypes फ्लैग का उपयोग किया जाता है या यह एक अभिलेख या संस्करण है) और हास्केल तो उदाहरण के लिए निम्न हास्केल प्रकार अवैध हैं:

type Bad = (Int, Bad)
type Evil = Bool -> Evil

इसके अतिरिक्त इसे बीजगणितीय डेटा प्रकार के अंदर लपेटा जाना चाहिए (तथापि इसमें केवल एक निर्माणकर्ता हो):

data Good = Pair Int Good
data Fine = Fun (Bool -> Fine)

ऐसा इसलिए है क्योंकि टाइप समानार्थक शब्द, जैसे सी में टाइपपीफ, संकलन समय पर उनकी परिभाषा के साथ बदल दिए जाते हैं। (टाइप पर्यायवाची वास्तविक प्रकार नहीं हैं; वे प्रोग्रामर की सुविधा के लिए केवल उपनाम हैं।) चूँकि यदि यह एक पुनरावर्ती प्रकार के साथ प्रयास किया जाता है, तो यह असीम रूप से लूप करेगा क्योंकि कितनी बार उपनाम को प्रतिस्थापित किया जाता है यह अभी भी खुद को संदर्भित करता है। उदा. बुरा अनिश्चित काल तक बढ़ेगा: Bad → (Int, Bad) → (Int, (Int, Bad)) → ... .

इसे देखने का एक और विधि यह है कि एक स्तर के संकेत (बीजगणितीय डेटा प्रकार) की आवश्यकता होती है जिससे समद्विबाहु प्रकार प्रणाली को यह पता चल सके कि रोल और अनरोल कब करना है।

यह भी देखें

• पुनरावर्ती परिभाषा
• बीजगणितीय डेटा प्रकार
• आगमनात्मक प्रकार
• नोड (कंप्यूटर विज्ञान)