बीजगणितीय डेटा प्रकार चिड़ियाघर

इस लेख में हम बीजगणितीय डेटा प्रकारों की पूरी विविधता पर विचार करने का प्रयास करेंगे।

मुझे कहना होगा, कार्य काफी भारी है, और किसी व्यक्ति को समझने के लिए, यदि उसने पहले बीजीय प्रकार के साथ निपटा नहीं था, तो बहुत सरल नहीं है।
ADTs का उपयोग पहली बार होप भाषा में किया गया था, लेकिन उन्होंने स्टैंडआर्ट ML, OCaml, F #, और हास्केल भाषा जैसी एमएल भाषाओं की बदौलत बड़ी लोकप्रियता हासिल की।
आज ADT अधिक से अधिक भाषाओं में अधिक से अधिक समर्थित हैं: स्काला, रस्ट, नेमारल, रैकेट, ...
ADT एक सार्वभौमिक डेटा प्रकार है। इसका उपयोग करके, आप अधिकांश डेटा प्रकारों की कल्पना कर सकते हैं।
ADTs को बीजगणितीय कहा जाता है, क्योंकि उन्हें इसके घटकों के प्रकार के बीजीय रचना के रूप में दर्शाया जा सकता है। यह ज्ञान इसका लाभ देता है: बीजीय रचना के गुणों को समझना, आप गणना कर सकते हैं कि कुछ डेटा बनाने के लिए किस प्रकार की आवश्यकता है।
हम हास्केल भाषा के आधार पर प्रकारों पर विचार करेंगे, हालांकि, एडीटी के समर्थन के साथ अन्य भाषाओं में थोड़े बदलाव के साथ ही प्राप्त किया जा सकता है।

यह ध्यान दिया जाना चाहिए कि रसेल, चर्च, मार्टिन-लोफ द्वारा बीसवीं शताब्दी में विकसित किए गए प्रकार के सिद्धांतों ने इतनी लोकप्रियता हासिल की कि अब (पहले से ही इक्कीसवीं सदी में) होमोटॉपी टाइप थ्योरी का सिद्धांत दिखाई दिया, जिसने गणित की नींव को समझाने का प्रयास किया।

हमारा काम बीजगणितीय डेटा प्रकारों को देखना है। अक्सर, एडीटी डेटा को बॉक्सिंग या लपेटा जाता है। उनका नाम इसलिए रखा गया है क्योंकि वे एक बॉक्स में पैक किए गए डेटा की तरह दिखते हैं। सबसे दिलचस्प बात यह है कि यहां तक ​​कि कार्यान्वयन का मतलब डेटा भंडारण नहीं है, लेकिन संकेत है। कार्यान्वयन में आसानी के अलावा, यह आलसीपन के प्रभावी तंत्र प्रदान करता है जो हास्केल के पास है।
निष्पक्षता में, मैं ध्यान देता हूं कि हास्केल आपको गैर-आलसी बनाने की अनुमति देता है, जिसमें गैर-लिपटे डेटा भी शामिल है, जो अत्यधिक लोड किए गए संस्करणों को संसाधित करने में मदद करता है।
हास्केल में, data या newtype घोषणाओं का उपयोग करके एडीटी बनाने के 2 तरीके हैं। दोनों के बीच अंतर यह है कि newtype de facto लिपटा नहीं है, जिसका अर्थ है कि यह सस्ता (मशीन संसाधनों द्वारा) है और इसलिए अधिक लाभदायक है, लेकिन इसके साथ आप केवल ADTs के एक संकीर्ण सर्कल को रिकॉर्ड कर सकते हैं, इसलिए यह सामान्य मामले में काम नहीं करता है।

आदिम के माध्यम से लागू डेटा प्रकार

हास्केल में, ऐसे कुछ डेटा हैं, मुख्य रूप से डेटा प्रकार जैसे
Int , Integer, Float , Double , Char , ...
ऐसा नहीं है कि आप इन प्रकारों को वास्तविक (ADT के माध्यम से) नहीं बना सकते, बस कंप्यूटर पहले से ही जानता है कि संख्याओं के साथ कैसे काम करना है, और इसका उपयोग न करना एक पाप है।
मैं इस तथ्य पर ध्यान आकर्षित करना चाहता हूं कि सभी प्रकार एक बड़े अक्षर के साथ लिखे गए हैं, यह इस तथ्य के कारण है कि हास्केल में सभी प्रकार और डेटा निर्माता विशेष रूप से एक बड़े अक्षर के साथ लिखे गए हैं।

शून्य डेटा प्रकार

अधिकांश अनिवार्य भाषाओं को इस तरह से संरचित किया जाता है कि पदानुक्रमित जटिलता में नीचे से ऊपर तक कार्यक्रम बनाना सुविधाजनक होता है।
हास्केल में, ऊपर से नीचे तक कोड लिखना बहुत आसान है। इस संबंध में, खाली डेटा प्रकार (कार्यान्वयन के बिना) होना आवश्यक हो गया, क्योंकि यह ज्ञात है कि यह डेटा प्रकार क्या करेगा, लेकिन यह अभी तक तय नहीं है कि इसे कैसे भरना है। एक एक्सटेंशन दिखाई दिया है जो आपको ऐसा करने की अनुमति देता है।

ये वास्तविक, छद्म नल, खाली डेटा प्रकार नहीं हैं।

 data S data T a data K ab 

वाक्यविन्यास, जैसा कि हम देखते हैं, यह अपमान करने के लिए सरल है।
यहां हमने 3 प्रकार के डेटा बनाए, जिनमें से दूसरा पैरामीट्रिक है। हम देखते हैं कि a लोअरकेस लेटर के साथ लिखा गया है, जिसका अर्थ है कि यह कंस्ट्रक्टर नहीं हो सकता है। आउटपुट एक पैरामीटर है जिसमें आप किसी भी प्रकार को प्रतिस्थापित कर सकते हैं, अर्थात्, आपके पास निम्न प्रकार हो सकते हैं: T Int, T Char , TS , T (T Double) और यहां तक ​​कि T (T ( T String)) ।
हम यह भी देखते हैं कि निर्माणकर्ता प्रकार की शुरुआत में है, और फिर डेटा एक बॉक्स में पैक किया गया है।
आप पूछते हैं कि उनकी आवश्यकता क्यों है?
उदाहरण के लिए, हम निम्नलिखित मान्य फ़ंक्शन कोड लिख सकते हैं:

 doubleT :: T a -> (T a, T a) doubleT t = (t, t) 

बेशक, ज्यादातर मामलों में डेटा के आंतरिक ज्ञान के बिना सभी कार्यों को लिखना असंभव है, लेकिन आप कुछ कार्यों को बाद के लिए छोड़ सकते हैं, अन्य कार्य कर सकते हैं, जैसे कि:

 foo :: S -> Int -> T a foo = undefined nextT :: S -> Int -> (Int, T a) nextT si = (i+1, foo s (i+1)) 

इस कार्यक्रम को संकलित किया जाएगा और त्रुटियों के लिए जाँच की जाएगी, इस तथ्य के बावजूद कि न तो डेटा और न ही कार्यों का हिस्सा परिभाषित किया गया है।

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

यूनिट डेटा प्रकार

एकल डेटा प्रकार कुछ भी नहीं देते हैं लेकिन इसके बारे में ज्ञान है।
उपयोग किए जाने वाले सामान्य डेटा प्रकारों में से

 data () = () --X 

इसके बाद की टिप्पणी

  -- X 

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

 main :: IO () 

क्योंकि प्रोग्राम को कुछ वापस करना होगा। इसलिए () सबसे लोकप्रिय प्रकार है जब आपको कुछ भी वापस करने की आवश्यकता होती है।
या, यहां एक और प्रसिद्ध इकाई प्रकार है:

 data Unit = Unit 

वही, केवल नियमित निर्माणकर्ताओं का उपयोग किया जाता है।
मुझे कहना होगा कि इन प्रकारों में कोई पुनरावृत्ति नहीं है, अर्थात आप लिख सकते हैं:

 data UnitData = Unit 

तथ्य यह है कि टाइप नेमस्पेस टाइप कंस्ट्रक्टर स्पेस के साथ इंटरसेक्ट नहीं होता है, इसलिए कंपाइलर समझता है कि कहां रिकर्सन है और कहां नहीं।

कार्यों के प्रकार

कार्यों के प्रकार नाम दिए गए हैं ताकि उन्हें कई प्रकार के उत्पाद के रूप में प्रस्तुत किया जा सके जो इसे बनाते हैं।
बहुत लोकप्रिय डेटा प्रकार सार्वभौमिक रूप से उपयोग किए जाते हैं।
उनमें से सबसे प्रसिद्ध ट्यूपल या बेवकूफ हैं। हास्केल इसके लिए विशेष संश्लिष्ट चीनी का उपयोग करता है:

 data (,) ab = (,) ab --X (a, b) data (,,) abc = (,,) abc --X (a, b, c) data (,,,,) abcd = (,,,,) abcd --X (a, b, c, d) 

हम साधारण कंस्ट्रक्टरों का उपयोग करके एक ही बात लिख सकते हैं:

 data Pair ab = Pair ab data Triple abc = Triple abc 

जहां भी आपको डेटा में दिए गए एक से अधिक स्टोर करने की आवश्यकता है - यह काम का प्रकार है।

कुल डेटा प्रकार

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

 data Bool = False | True 

एक प्रसिद्ध गणन भी प्रकार Ordering , जिसका उपयोग तुलना में किया जाता है

 data Ordering = LT | EQ | GT 

यदि हम अधिक जटिल ADTs पर जाते हैं, तो हमें शून्य-एबेलियन प्रकार को वापस बुलाना होगा:

 data Maybe a = Nothing | Just a 

वह डेटा जिसमें परिणाम के लिए एक फ़ील्ड होता है जब वह नहीं होता है, इसलिए कई प्रोग्रामिंग भाषाओं से null बोलने के लिए।

 (</>) :: Int -> Int -> Maybe Int _ </> 0 = Nothing a </> b = Just (a `div` b) 

यदि आपको त्रुटि के बारे में अधिक जानने की आवश्यकता है, तो और भी जटिल डेटा प्रकार का उपयोग किया जाता है:

 data Either ab = Left a | Right b 

एक डेटा प्रकार जहां "या तो" परिणाम (त्रुटि या त्रुटि का विवरण) या "सही" परिणाम होता है।
साथ ही इस डेटा प्रकार का उपयोग बाइनरी चयन के लिए किया जाता है।

 type IdPerson = Int type ErrorMsg = String personChecker :: Person -> Either ErrorMsg IdPerson personChecker p = if age p < 0 then Left "this guy is not born yet!" else if null $ first_name p then Left "this guy is unnamed!" else Right $ registeredId p 

आप अधिक विदेशी डेटा प्रकारों की रचना कर सकते हैं, उदाहरण के लिए:

 data Both ab = None | First a | Second b | Both ab 

यहां हमारे पास या तो कोई परिणाम नहीं है, या 1 परिणाम, या 2, या दोनों 1 और 2 है।

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

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

 data [] a = [] | a : [a] --X 

हालाँकि, इसे आसानी से शब्दों के साथ लिखा जा सकता है:

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

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

 data Tree a = Leaf a | Branch (Tree a) (Tree a) data Tree2 a = Empty | Branch2 (Tree2 a) a (Tree2 a) 

या फिर, प्राकृतिक संख्या:

 data Nat = Zero | Succ Nat 

यदि आपने अभी तक एक अशक्त डेटा प्रकार के बारे में कोई स्पॉइलर नहीं खोला है (या खोला है, लेकिन समझ में नहीं आया है) - यह खोलने और पढ़ने और समझने का समय है कि Void प्राथमिक रूप से पुनरावर्ती डेटा प्रकार है।

पावर डेटा प्रकार

ऐसा मत सोचो कि केवल डेटा को एडीटी के लिए लिखा जा सकता है। कार्यों को भी आसानी से एडीटी में लिखा जा सकता है: शक्ति प्रकार (सामान्य प्रकार में एक डेटा की शक्ति को दूसरे की शक्ति तक बढ़ाने की शक्ति होती है):

 data Fun ab = Fun (a -> b) newtype ContT rma = Writer ((a -> mr) -> mr) 

यदि हम कार्यों के ADT का उपयोग करते हैं, जहां डेटा फ़ंक्शन के साथ मिलाया जाएगा, ये रिकॉर्ड्स और वस्तुओं के समान संरचना से अधिक कुछ नहीं हैं।

प्रेत डेटा प्रकार

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

 data Proxy a = Proxy 

जैसा कि आप देख सकते हैं, टाइप हेडर कहता है कि प्रकार पैरामीट्रिक है, लेकिन वास्तव में यह एक डमी है।
इन डेटा प्रकारों को अक्सर सार्वभौमिक gags के रूप में उपयोग किया जाता है, क्योंकि वे आसानी से एक डेटा प्रकार से दूसरे में परिवर्तित हो जाते हैं।

 proxyonverter :: Proxy a -> Proxy b proxyonverter Proxy = Proxy 

रिकॉर्डिंग

इस प्रकार के कार्यों का उपयोग अक्सर किया जाता है कि इसमें एक विशेष संश्लिष्ट शर्करा होता है जो इसे आसान और अधिक सुविधाजनक रूप से (अंतर्निहित गेटर्स और सेटर के साथ) काम करने में मदद करता है। इन प्रकारों को रिकॉर्ड कहा जाता है।
हमारे पास एक प्रकार है

 data Sex = Female | Male data Person = Person String String Int Int Sex (String -> String) 

फिर से लिखना अधिक सुविधाजनक है:

 data Sex = Female | Male data Person = Person { lastName :: String , firstName :: String , age :: Int , socialId :: Int , sex :: Sex , greeting :: String -> String } 

आवेषण या आवरण

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

 newtype Wrapper a = Wrapper { unwrapper :: a } newtype Dollar = Dollar Int 

अस्तित्वगत डेटा प्रकार

अस्तित्व डेटा प्रकारों का नाम इसलिए रखा गया है क्योंकि अस्तित्व मात्रात्मक are है।
विरोधाभास यह है कि हास्केल में ऐसा कोई क्वांटिफायर नहीं है।
लेकिन सार्वभौमिकता की एक मात्रा है ifier। लेकिन इन क्वांटिफायर को आसानी से एक दूसरे में बदला जा सकता है।
सटीक होने के लिए, प्रत्येक अस्तित्वगत रूप से रैंक n+1 परिमाण एक सार्वभौमिक रूप से मात्रा में रैंक n में बदल सकता है।

 data HeteroData = forall a. HeteroData a heteroList :: [HeteroData] heteroList = [HeteroData 3.7, HeteroData "message", HeteroData True] 

जैसा कि आप देख सकते हैं, वे एक विषम सूची बनाने में सक्षम थे, इस तथ्य के बावजूद कि यह सजातीय है।
लेकिन कुछ वस्तु जैसा दिखता है:

 data Counter a = forall self. NewCounter { _this :: self , _inc :: self -> self , _display :: self -> IO () , tag :: a } 

अंडरस्कोर के साथ लिखे गए कार्यों के साथ, हम सीधे काम नहीं कर सकते हैं।
सच है, ऐसी वस्तुओं के साथ काम करना ओओपी के साथ काम करने की तरह बिल्कुल नहीं है:

सामान्य बीजीय डेटा प्रकार (GADTs)

सामान्यीकृत ADTs सामान्य लोगों से भिन्न होते हैं जिसमें वे अंतिम प्रकार को ट्रिम और विशेषज्ञ करते हैं।
हास्केल इस डेटा के "कार्यात्मक" रिकॉर्ड का उपयोग करता है। आइए नए सिंटैक्स में एक साधारण डेटा प्रकार को फिर से लिखें:

 data Maybe a = Nothing | Just a data Maybe a where Nothing :: Maybe a Just :: a -> Maybe a -- -------------------- data List a = Nil | Cons a (List a) data List a where Nil :: List a Cons :: a -> List a -> List a 

हम देखते हैं कि अंतिम डेटा प्रकार सभी के लिए समान है: Maybe a (या List a )। OATD आपको विभिन्न परिणामी डेटा प्रकारों की अनुमति देता है।
अगर हमारे पास एक सार पेड़ है:

  data Term a where Lit :: Int -> Term Int Succ :: Term Int -> Term Int IsZero :: Term Int -> Term Bool If :: Term Bool -> Term a -> Term a -> Term a Pair :: Term a -> Term b -> Term (a,b) 

समान पेड़ की गणना करने के लिए एक फ़ंक्शन बनाना आसान है:

  eval :: Term a -> a eval (Lit i) = i eval (Succ t) = 1 + eval t eval (IsZero t) = eval t == 0 eval (If b e1 e2) = if eval b then eval e1 else eval e2 eval (Pair e1 e2) = (eval e1, eval e2) 

सीमित मापदंडों के साथ पैरामीट्रिक डेटा प्रकार

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

 Just 3 :: (Maybe Int :: *) 

और यहां पैरामीटर पर प्रतिबंध के साथ डेटा है:

 data F (a :: * -> *) where ... 

मूल रूप से, ये प्रकार बहुत उच्च स्तर के अमूर्त के लिए आवश्यक हैं।

निष्कर्ष

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