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

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

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

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

उदाहरण

See also: Recursion (computer science) § Recursive data structures (structural recursion)

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

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

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

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

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

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

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

Further information: Mutual recursion § Data types

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

च: [t[1], ..., t[k
टी: वी एफ

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

इस परस्पर पुनरावर्ती परिभाषा को वन की परिभाषा को रेखांकित करके एकल पुनरावर्ती परिभाषा में परिवर्तित किया जा सकता है:

टी: वी [टी[1], ..., टी[के

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

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

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 होता है जहां प्रकार चर α प्रकार टी में प्रकट हो सकता है और पूरे प्रकार के लिए खड़ा होता है।

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

data Nat = Zero | Succ Nat

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

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

Isorecursive प्रकार

समद्विबाहु प्रकार के साथ, पुनरावर्ती प्रकार $\mu \alpha .T$ और इसका विस्तार (या अनोलिंग) $T[\mu \alpha .T/\alpha ]$ (जहां अंकन $X[Y/Z]$ इंगित करता है कि Z के सभी उदाहरणों को Y के साथ X में बदल दिया गया है) विशेष शब्द निर्माण के साथ अलग (और अलग) प्रकार हैं, जिन्हें आमतौर पर रोल और अनरोल कहा जाता है, जो उनके बीच एक समरूपता बनाते हैं। सटीक होना: $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 ]$ समान हैं - अर्थात, उन दो प्रकार के भावों को एक ही प्रकार को दर्शाने के लिए समझा जाता है। वास्तव में, समतुल्य प्रकार के अधिकांश सिद्धांत आगे बढ़ते हैं और अनिवार्य रूप से निर्दिष्ट करते हैं कि एक ही अनंत विस्तार वाले दो प्रकार के भाव समकक्ष हैं। इन नियमों के परिणामस्वरूप, समरूप प्रकार के प्रकार एक प्रकार की प्रणाली में आइसोरेकर्सिव प्रकार की तुलना में काफी अधिक जटिलता का योगदान करते हैं। एल्गोरिथम समस्याएं जैसे टाइप चेकिंग और अनुमान टाइप करें इक्वेरिकर्सिव टाइप्स के लिए भी अधिक कठिन हैं। चूंकि प्रत्यक्ष तुलना एक समवर्ती प्रकार पर समझ में नहीं आती है, इसलिए उन्हें ओ (एन लॉग एन) समय में एक कैननिकल रूप में परिवर्तित किया जा सकता है, जिसे आसानी से तुलना की जा सकती है। Isorecursive प्रकार स्व-संदर्भित (या पारस्परिक रूप से संदर्भित) प्रकार की परिभाषाओं को नाममात्र वस्तु-उन्मुख प्रोग्रामिंग भाषाओं में देखा जाता है, और वस्तुओं और वर्ग (कंप्यूटर विज्ञान) के टाइप-सैद्धांतिक शब्दार्थ में भी उत्पन्न होता है। कार्यात्मक प्रोग्रामिंग भाषाओं में, आइसोरेकर्सिव प्रकार (डेटाटाइप की आड़ में) भी आम हैं।

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

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

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

हालांकि, मिरांडा प्रोग्रामिंग भाषा, OCaml (जब तक -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)) → ... .

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

यह भी देखें

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