मुखौटा श्रेणी

प्रविष्टि

इस छोटे लेख में मैं हास्केल प्रकार प्रणाली के संदर्भ में श्रेणी सिद्धांत के बारे में बात करूंगा। कोई ज़मी, कोई चाल नहीं - मैं सब कुछ स्पष्ट रूप से समझाने की कोशिश करूंगा। मैं एक और के माध्यम से, एक के माध्यम से पाठक की जागरूकता को भड़काने के लिए गणित के साथ प्रोग्रामिंग भाषा का घनिष्ठ संबंध दिखाना चाहता हूं।

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

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

श्रेणी क्या है?

उदाहरण

स्पष्टता के लिए, हम पहले सरल श्रेणियों को दर्शाने वाले चित्रों के एक जोड़े पर विचार करते हैं। उनके पास लाल वृत्त और तीर हैं:

लाल वृत्त "वस्तुओं" का प्रतिनिधित्व करते हैं, और तीर "आकारिकी" का प्रतिनिधित्व करते हैं।

मैं वास्तविक जीवन से एक उदाहरण देना चाहता हूं, जो वस्तुओं और आकार की प्रकृति के बारे में कुछ सहज विचार देगा:

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

• ऐसा होता है कि आप एक शहर से दूसरे शहर तक ट्रेन या विमान से नहीं पहुंच सकते हैं - इन शहरों के बीच कोई आकार नहीं हैं।
• अगर हम एक ही शहर के भीतर जाते हैं, तो यह भी एक रूपवाद है - हम शहर से उस तक की यात्रा करते हैं।
• यदि सेंट पीटर्सबर्ग से मास्को के लिए एक ट्रेन है, और मास्को से एम्स्टर्डम के लिए एक उड़ान है, तो हम एक ट्रेन टिकट और एक हवाई जहाज का टिकट खरीद सकते हैं, उन्हें "गठबंधन" कर सकते हैं और इस तरह सेंट पीटर्सबर्ग से एम्स्टर्डम तक पहुंच सकते हैं - अर्थात, आप हमारे उपयोग कर सकते हैं मानचित्र पर, सेंट पीटर्सबर्ग से एम्सटर्डम तक इस संयुक्त आकारिकी का चित्रण करते हुए एक तीर खींचें।

मुझे उम्मीद है कि इस उदाहरण के साथ सब कुछ स्पष्ट है। और अब स्पष्टता के लिए थोड़ी औपचारिकता।

परिभाषा

तो, हम पहले से ही जानते हैं कि एक श्रेणी में वस्तुओं और आकार शामिल हैं:

1. वस्तुओं का एक वर्ग (सेट) है । वस्तुएं किसी भी इकाई हो सकती हैं।
2. किसी भी दो वस्तुओं A और B , आकृति विज्ञान Hom(A,B) के वर्ग Hom(A,B) परिभाषित किया गया है। इस वर्ग से एक आकारिकी f लिए, वस्तु A को एक क्षेत्र कहा जाता है, और B को सह - क्षेत्र कहा जाता है । यह इस तरह लिखा है:
   f ∈ Hom(A,B) या f : A → B
3. किसी भी दो रूपकों के लिए f : A → B और g : B → C , उनकी रचना को परिभाषित किया गया है - रूपवाद h = g ∘ f , में
   h : A → C यह महत्वपूर्ण है कि क्षेत्र g और सह क्षेत्र f संयोग है।
4. रचना साहचर्य है , जो कि किसी भी आकारिकी f : A → B , g : B → C और h : C → D , समानता
   (h ∘ g) ∘ f = h ∘ (g ∘ f)
5. किसी भी वस्तु A एक "इकाई" आकारिकी है, जिसे id A : A → A द्वारा निरूपित किया गया है और यह रचना के संबंध में तटस्थ है, अर्थात, किसी भी रूपवाद के लिए f : A → B , निम्नलिखित रखती है:
   id B ∘ f = f = f ∘ id A

भविष्य में, सूचकांक मुझे परेशान करेगा और मैं सिर्फ id लिखूंगा, क्योंकि इसका क्षेत्र / सह-क्षेत्र संदर्भ से बहाल है।

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

सेल्फ एक्सरसाइज एक्सरसाइज: जांचें कि निम्नलिखित इमेज एक श्रेणी है

मुखौटा श्रेणी

और अब मुख्य उदाहरण, लेख का मुख्य विषय। हस्क श्रेणी में हास्केल भाषा के प्रकार और उनके बीच के कार्य शामिल हैं। अधिक सख्ती से:

1. हस्क ऑब्जेक्ट: ¹ * डेटा प्रकार। उदाहरण के लिए, आदिम प्रकार: Integer , Bool , Char , आदि। "टाइप" Maybe कि एक तरह का * → * , लेकिन Maybe Bool प्रकार में एक प्रकार * और इसलिए हास्क में एक वस्तु हो। किसी भी प्रकार के पैरामीटर के साथ समान, लेकिन बाद में उनके बारे में। पदनाम: a ∷ * ≡ " a प्रकार है * " a " a हैस्क में एक वस्तु है"।
2. हस्क मॉर्फिज्म : कोई भी हास्केल एक वस्तु से दूसरे प्रकार (प्रकार) में कार्य करता है। यदि a, b ∷ * , तो फ़ंक्शन f ∷ a → b क्षेत्र और सह-क्षेत्र b साथ एक रूपवाद है। इस प्रकार, वस्तुओं a और b बीच आकारिकी के वर्ग को a → b प्रकार द्वारा दर्शाया जाता है। गणितीय संकेतन के साथ सादृश्य को पूरा करने के लिए, आप निम्नलिखित पर्यायवाची को दर्ज कर सकते हैं:
   

    type Hom(a,b) = a → b 

   लेकिन मैं इसका उपयोग करना जारी नहीं रखूंगा, क्योंकि तीर, मेरी राय में, स्पष्ट है।
3. रचना: मानक फ़ंक्शन (.) ∷ (b → c) → (a → b) → (a → c) । किसी भी दो कार्यों के लिए f ∷ a → b और g ∷ b → c रचना g . f ∷ a → c g . f ∷ a → c को स्वाभाविक रूप से परिभाषित किया गया है:
   

    g . f = λx → g (fx) 

4. इस परिभाषा से रचना की संबद्धता स्पष्ट है: किसी भी तीन कार्यों के लिए
   f ∷ a → b , g ∷ b → c और h ∷ c → d
   

    (h . g) . f ≡ h . (g . f) ≡ λx → h (g (fx)) 

   प्रत्यक्ष जांच:

     (h . g) . f ≡ λx → (h . g) (fx) ≡ λx → (λy → h (gy)) (fx) ≡ λx → h (g (fx)) h . (g . f) ≡ λx → h ((g . f) x) ≡ λx → h ((λy → g (fy)) x) ≡ λx → h (g (fx)) 

5. किसी भी प्रकार के लिए a ∷ * फंक्शन id ∷ a → a भी स्वाभाविक रूप से परिभाषित है:
   

    id = λx → x 

   इस परिभाषा से, आवश्यक गुणों की पूर्ति स्पष्ट है। आज्ञा देना f ∷ a → b
   

    f . id ≡ λx → f (id x) ≡ λx → fx ≡ f id . f ≡ λx → id (fx) ≡ λx → fx ≡ f 

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

इसलिए, जैसा कि हम देखते हैं, सभी आवश्यक इकाइयां मौजूद हैं, उनके रिश्ते प्रस्तुत किए गए हैं और आवश्यक गुण पूरे किए गए हैं, इसलिए हास्क एक पूर्ण श्रेणी है। ध्यान दें कि कैसे सभी अवधारणाओं और निर्माणों को गणितीय संकेतन से हास्केल में न्यूनतम वाक्यात्मक परिवर्तनों के साथ स्थानांतरित किया जाता है।

आगे मैं इस बारे में बताऊंगा कि फंक्शन्स क्या हैं और उन्हें हास्क श्रेणी में कैसे मूर्त रूप दिया जाता है ।

functors

फंडर्स एक श्रेणी से दूसरी श्रेणी में परिवर्तन कर रहे हैं। चूंकि प्रत्येक श्रेणी में ऑब्जेक्ट्स और मॉर्फिज्म होते हैं, इसलिए फ़नकार को मैपिंग की एक जोड़ी भी होनी चाहिए: पहली श्रेणी में ऑब्जेक्ट्स को दूसरी में मैप करेंगे, और दूसरे में मॉर्फिज़्म को मैप करेंगे - दूसरे में मॉर्फिज़्म।

पहले मैं एक गणितीय परिभाषा दूंगा, और फिर मैं यह प्रदर्शित करूंगा कि हास्केल के मामले में यह कितना सरल है।

गणितीय परिभाषा

दो श्रेणियों C और D पर विचार करें और C से D तक के फंक्टर F D संकेतन के रूप में ही संकेतन है, केवल फ़नकार को एक बड़े अक्षर द्वारा इंगित किया जाता है: F : C → D इस F की दो भूमिकाएँ हैं:

1. श्रेणी C से प्रत्येक ऑब्जेक्ट A श्रेणी D से ऑब्जेक्ट के साथ जुड़ा हुआ है और F(A) द्वारा निरूपित किया गया है।
2. प्रत्येक आकारवाद g : A → B श्रेणी C से g : A → B , श्रेणी D से आकारिकी के साथ जुड़ा हुआ है और F(g) : F(A) → F(B) द्वारा निरूपित किया जाता है।

एक बार फिर, एक फनकार मपिंग्स की एक जोड़ी है:

  A ↦ F(A) g : A → B ↦ F(g) : F(A) → F(B) 

तस्वीर में, पहला प्रदर्शन पीले धराशायी तीर के साथ दिखाया गया है, और दूसरा नीले रंग के साथ:


दो पूरी तरह से प्राकृतिक आवश्यकताओं को पूरा करने के लिए फ़ंक्टर की आवश्यकता है:

1. किसी दिए गए ऑब्जेक्ट के प्रत्येक एकल आकार को अपनी छवि के एकल आकारवाद में अनुवाद करना होगा:
   F(id A ) = id F(A)
2. उसे आकार की रचना का अपनी छवियों की संरचना में अनुवाद करना चाहिए:
   F(h ∘ g) = F(h) ∘ F(g)

हास्क में फं

अब हम Hask श्रेणी से Hask के फंक्शनलर्स को देखते हैं । वैसे, ऐसे फंक्शनलर्स जो किसी श्रेणी को स्वयं में अनुवादित करते हैं, उन्हें एंडोफुन्क्टर कहा जाता है।

तो, फिर हमें प्रकारों में अनुवाद करने की आवश्यकता है, और कार्यों में फ़ंक्शन - दो मैपिंग। और हास्केल भाषा का निर्माण पहले किस रूप में होता है? यह सही है, प्रकार के साथ * → * ।

उदाहरण के लिए, पहले से ही वर्णित प्रकार Maybe ∷ * → * । यह एक ऐसा नक्शा है जो किसी भी ऑब्जेक्ट के लिए मैप करता a ∷ * एक ही श्रेणी से एक ऑब्जेक्ट (Maybe a) ∷ * । (Maybe a) ∷ * । यहाँ Maybe a दिए गए पैरामीटर a साथ एक पैरामीटर प्रकार के एक निर्माता के रूप में नहीं समझा जाना चाहिए, लेकिन गणितीय परिभाषा से F(A) समान एकल चरित्र के रूप में।

तो, पहली मैपिंग हमें मुफ्त में दी गई है - यह किसी भी प्रकार का एक पैरामीटर है।

  data Maybe a = Nothing | Just a 

लेकिन दूसरी मैपिंग कैसे प्राप्त करें? हास्केल ने इसके लिए एक विशेष वर्ग को परिभाषित किया:

  class Functor f where fmap ∷ (a → b) → (fa → fb) 

जहां f ∷ * → * । यही है, fmap एक बहुरूपी फ़ंक्शन है जो रूपवाद को a → b लेता है और morphism fa → fb लौटाता है। इसके आधार पर, हम Maybe इसके लिए एक फंक्शन को परिभाषित करके Maybe असली फ़नकार बनायेंगे:

  instance Functor Maybe where fmap g = fg where fg Nothing = Nothing fg (Just x) = Just (gx) 

इसलिए, हमें दो मैपिंग मिलीं:

  a ∷ * ↦ Maybe a ∷ * g ∷ a → b ↦ fmap g ∷ Maybe a → Maybe b 

कुछ भी नहीं, गणितीय संकेतन के विपरीत, उनके अलग-अलग नाम हैं, बस इस तरह की भाषा की विशिष्टता है, लेकिन यह किसी भी तरह से अर्थ को प्रभावित नहीं करता है।

खैर, आवश्यकताओं को पूरा करने के बारे में क्या? fmap को id को सहेजना चाहिए और रचना को रचना में अनुवाद करना चाहिए:

  fmap id ≡ id fmap (h . g) ≡ (fmap h) . (fmap g) 

यह जांचना आसान है, यह हो सकता है कि उपर्युक्त परिभाषा के मामले में Maybe ।

ध्यान दें कि हम एक पैरामीटर के साथ बस एक प्रकार के कंस्ट्रक्टर की घोषणा करके पहली मैपिंग प्राप्त करते हैं। और उसके लिए, जैसा कि वस्तुओं के बीच प्रदर्शित करने के लिए, यह मायने नहीं रखता है कि Maybe प्रकार कैसे Maybe : यह बस Maybe a ऑब्जेक्ट के ऑब्जेक्ट को मैप करता Maybe a , कोई फर्क नहीं पड़ता।

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

  data Foo a = Bar a Int [a] | Buz Char Bool | Qux (Maybe a) 

फ़ंक्शन g ∷ a → b को सभी डेटा कंस्ट्रक्टर्स को पुन: प्राप्त करना होगा और, जहाँ भी उनके पास a का पैरामीटर हो a उसे g का उपयोग करके परिवर्तित करें। इसके अलावा, अगर [a] या Maybe a , तो उनके fmap g को उनके लिए काम करना चाहिए, जो फिर से उनके ढांचे को बायपास कर देगा और उसे बदल देगा।

और लो और निहारना, यह संभव है! GHC का संगत विस्तार है । हम कोड में लिखते हैं:

  {-# LANGUAGE DeriveFunctor #-} … data Foo a = … deriving Functor 

और हम तुरंत इसी श्रेणी के साथ हास्क श्रेणी - Foo का पूर्ण- संपन्न एंडोफंकर fmap ।

वैसे, यह कहने योग्य है कि ये फ़ंक्शंस वास्तव में हास्क श्रेणी को इसके उपश्रेणी में प्रदर्शित करते हैं, अर्थात्, श्रेणी में वस्तुओं और आकार के छोटे वर्ग के साथ। उदाहरण के लिए, a ↦ Maybe a कि मैपिंग करके a ↦ Maybe a हम एक साधारण प्रकार Int नहीं पा सकते - कोई फर्क नहीं पड़ता कि हम क्या लेते हैं। फिर भी, वस्तुओं के परिणामस्वरूप उपवर्ग और उन पर फ़ंक्शंस के वर्ग भी रूप में एक श्रेणी बनाते हैं।

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

निष्कर्ष

इसलिए, मैंने हस्क श्रेणी के बारे में और उसमें मौजूद फंक्शनलर्स के बारे में बात की, और मुझे उम्मीद है कि इससे हास्केल प्रकार प्रणाली को एक नए परिप्रेक्ष्य में समझने में मदद मिली। शायद यह एक व्यावहारिक दृष्टिकोण से बेकार लगता है, क्योंकि हर कोई शायद अपने तरीके से fmap का अर्थ समझता है और यह जाने बिना कि एक fmap क्या है। लेकिन तब मैं Hask श्रेणी की कुंजी में प्राकृतिक परिवर्तनों, मठों और अन्य श्रेणीबद्ध निर्माणों के बारे में लिखने जा रहा हूं और फिर, मुझे लगता है, गणितीय एनालॉग्स अधिक उपयोगी होंगे, जिससे आप इन भाषा निर्माणों की आंतरिक प्रकृति को बेहतर ढंग से समझ पाएंगे और भविष्य में उन्हें और अधिक सचेत रूप से लागू कर पाएंगे।

---

1. यदि किसी को पहले प्रकार के साथ नहीं मिला है, तो मैं संक्षेप में समझाता हूं। किंड्स सामान्य प्रकारों पर एक प्रकार की प्रणाली है। प्रकार दो प्रकार के होते हैं:
   
   • * - यह एक सरल, गैर-पैरामीटर प्रकार का प्रकार है। उदाहरण के लिए Bool , Char इत्यादि। कस्टम data Foo = Bar | Buz (Maybe Foo) | Quux [Int] प्रकार data Foo = Bar | Buz (Maybe Foo) | Quux [Int] data Foo = Bar | Buz (Maybe Foo) | Quux [Int] data Foo = Bar | Buz (Maybe Foo) | Quux [Int] भी सरल होगा: Foo ∷ * , क्योंकि टाइप कंस्ट्रक्टर का कोई पैरामीटर नहीं है (हालाँकि इसके डेटा कंस्ट्रक्टर हैं)
   • … → … - यह एक अधिक जटिल प्रकार है, यह दीर्घवृत्त के स्थानों में * और → बना कोई अन्य प्रकार हो सकता है। उदाहरण के लिए: [] ∷ * → * , या (,) ∷ * → (* → *) या कुछ भी अधिक जटिल: ((* → *) → *) → (* → *) ।
   
   इन सभी का अर्थ सरल है: प्रकार के निर्माता प्रकारों पर प्रकार के प्रकार हैं और प्रकार यह वर्णन करते हैं कि ये फ़ंक्शन कैसे सही तरीके से सहभागिता करते हैं। उदाहरण के लिए, हम [Maybe] नहीं लिख सकते, क्योंकि [] ∷ * → * , अर्थात, कोष्ठक के तर्क में दयालुता * होनी चाहिए, और Maybe इसमें * → * , अर्थात, Maybe यह एक फ़ंक्शन भी है, और यदि हम इसे तर्क देते हैं तो Int ∷ * , हमें Maybe Int ∷ * मिलता है और इसे पहले से ही कोष्ठक में भेज सकते हैं: [Maybe Int] ∷ * । इस तरह के नियंत्रण के लिए, काइंड मौजूद हैं।