हस्क श्रेणी एंडोफुन्क्टर और उनके मोनोइडल संरचना

परिचय

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

पदनाम

पिछली बार मैं पत्र f साथ एक रूपवाद / कार्य को निरूपित करना चाहता था, लेकिन इसका इस्तेमाल फ़ंक्टर / वेरिएबल ऑफ़ टाइप f को निरूपित करने के लिए किया गया था - हास्केल भाषा के दृष्टिकोण से कोई समस्या नहीं है, लेकिन यदि आप इसे ध्यान से पढ़ते हैं, तो यह भ्रमित हो सकता है, और मैंने आकृतिवाद के लिए पत्र का उपयोग किया g । एक तिपहिया, लेकिन फिर भी, मेरा मानना ​​है कि यह विभिन्न प्रकृति की अलग-अलग संस्थाओं के लिए उपयोगी है। मैं सामान्य नामों से सामान्य प्रकारों को कॉल करूंगा, लेकिन प्रकार के चर जिन्हें मैं छोटे ग्रीक अक्षरों में कॉल करूंगा, वर्णमाला की शुरुआत से सरल (letters) अक्षरों के साथ, और पैरामीट्रिक ( ∗ → ∗ ) अक्षर वर्णमाला के अंत से ( θ अंत से नहीं हैं, लेकिन) यह looks से बेहतर दिखता है, जो कि X समान है)। तो, हास्क श्रेणी की शब्दावली में:

• ऑब्जेक्ट: α, β, γ, δ ∷ ∗
• फ़नकार: θ, φ, ψ, ω ∷ ∗ → ∗
• आकृति विज्ञान: f, g, h ∷ α → β

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

शब्दावली के बारे में एक और टिप्पणी: जैसा कि आप पहले ही देख चुके हैं, जिसे मैंने आखिरी बार "दयालु" (अब) शब्द कहा था, अब मैं शब्द को "सॉर्ट" कहता हूं - यह एक आम तौर पर स्वीकृत अनुवाद माना जाता है।

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

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

पहचान करने वाला फनकार

यूनिट मॉर्फिज़्म के रूप में एक पहचान फ़ंक्टर का चयन करना स्वाभाविक है, यानी एक ऐसा फ़नकार जो कुछ भी नहीं बदलता है। हास्केल में, इसके लिए कोई विशेष पदनाम नहीं है - चूंकि यह कुछ भी नहीं करता है, इसे किसी भी तरह से क्यों नामित किया जाना चाहिए? मैं एक "डमी" टाइप कंस्ट्रक्टर को पेश करूंगा, जिसकी मदद से हस्क श्रेणी की वस्तुओं पर इस फ़नकार की कार्रवाई की "कल्पना" करना संभव होगा:

 type Id α = α 

हास्केल में, आप टाइप पर्यायवाची के लिए अवतार घोषित नहीं कर सकते हैं, इसलिए Id को अन्य फंक्शनलर्स की तरह ही दर्ज नहीं किया जा सकता है, लेकिन यदि यह संभव था, तो हम इसे लिखेंगे:

 -- warning: - instance Functor Id where fmap ∷ (α → β) → (Id α → Id β) fmap f = f 

यही है, आकारिकी पर इस fmap ≡ id ∷ (α → β) → (α → β) के व्यवहार को तुच्छ रूप से परिभाषित किया गया है: fmap ≡ id ∷ (α → β) → (α → β) - यहाँ कोई निर्माता Id है, लेकिन यह एक ही हस्ताक्षर है। तो, दो फ़नकार मैपिंग इस तरह दिखते हैं:

 α ∷ ∗ ↦ Id α = α ∷ ∗ f ∷ α → β ↦ id f = f ∷ α → β 

हालाँकि यह फनकार बेकार लगता है, लेकिन हमें श्रेणी की परिभाषा को पूरा करने की आवश्यकता है। इसके अलावा, यह किसी भी प्रकार के α ∷ ∗ को Id α ∷ ∗ रूप में महसूस करना संभव बनाता है, Id α ∷ ∗ , एक समान Id α ∷ ∗ की कार्रवाई के तहत - यह अभी भी उपयोगी है जब हम भिक्षुओं के साथ मिलते हैं।

फनकार रचना

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

एक उदाहरण से शुरू करते हैं। हमारे लिए ज्ञात दो फ़ंक्शंस पर विचार करें: Maybe और [] । यहां बताया गया है कि वे वस्तुओं पर कैसे कार्य करते हैं:

 α ∷ ∗ ↦ Maybe α ∷ ∗ β ∷ ∗ ↦ [β] ∷ ∗ 

रचना का अर्थ है कि हम पहले एक मैपिंग लागू करते हैं, और परिणाम के लिए, दूसरा:

 α ↦ Maybe α ↦ [Maybe α] 

या किसी अन्य क्रम में:

 α ↦ [α] ↦ Maybe [α] 

रचना को टाइप कंस्ट्रक्टर में लागू करने के लिए, कुछ विशेष की आवश्यकता नहीं है - बस एक को पहले लिखें, फिर दूसरे को। हम इस ऑपरेशन के लिए एक नियमित रचना (ऑपरेटर के रूप में एक प्रकार के निर्माणकर्ता को एक बृहदान्त्र के साथ शुरू करना चाहिए, और मैं समरूपता के लिए दूसरा डालता हूं) के समान एक संकेतन प्रस्तुत करता हूं:

 type (φ :.: ψ) α = φ (ψ α) 

अब देखते हैं कि आकारिकी के मानचित्रण के साथ क्या होता है। चूँकि इस functor का किसी भी functor के लिए fmap नाम है, हम सामान्य रूप से कह सकते हैं कि आपको fmap लिए एक fmap को लागू करने की आवश्यकता है, और फिर दूसरा, अर्थात, λf → fmap (fmap f) की रचना की मैपिंग λf → fmap (fmap f) या सिर्फ fmap . fmap fmap . fmap । आपको यह समझने की आवश्यकता है कि ये दो fmap - एक पॉलीमॉर्फिक फ़ंक्शन के विभिन्न हाइपोस्टेसिस - प्रत्येक का अपना प्रकार और इसकी संबंधित परिभाषा है। आइए हम इसे स्पष्ट रूप से प्रदर्शित करें:

 instance Functor Maybe where -- fmap ∷ (α → β) → (Maybe α → Maybe β) fmap f = f' where f' Nothing = Nothing f' (Just x) = Just (fx) instance Functor [] where -- fmap ∷ (α → β) → ([α] → [β]) fmap g = g' where g' [] = [] g' (x:xs) = (gx) : (g' xs) 

अब एक उदाहरण का उपयोग करके रचना पर विचार करें: [] :.: Maybe

 (fmap . fmap) ∷ (α → β) → ([Maybe α] → [Maybe β]) (fmap . fmap) even [Just 2, Nothing, Just 3] ≡ [Just True, Nothing, Just False] 

और एक अलग क्रम में: Maybe :.: []

 (fmap . fmap) ∷ (α → β) → (Maybe [α] → Maybe [β]) (fmap . fmap) even Just [1, 2, 3] ≡ Just [False, True, False] (fmap . fmap) even Nothing ≡ Nothing 

अगर हम फंक्शंसर्स की रचना को फ़नकार वर्ग का अवतार बनाना चाहते हैं, तो हम इसे उसी तरह से करेंगे जैसे कि टाइपकास्ट पैकेज के लेखक करते हैं । हालाँकि, मुझे इसमें ज्यादा समझदारी नहीं है, क्योंकि मुझे अतिरिक्त डेटा कंस्ट्रक्टर में मानों को लपेटना है। तो, अगर हम फिगर्स के बारे में मैप्स (ऑब्जेक्ट्स और मॉर्फिज़्म पर) के जोड़े के रूप में बात करते हैं, तो दो (φ, fmap φ ) और (ψ, fmap ψ ) , उनकी रचना इस तरह के मैप्स की एक जोड़ी होगी: (φ :.: ψ, fmap (ψ, fmap ) (φ :.: ψ, fmap . fmap ψ ) , यानी

α ∷ ∗ ↦ (φ :.: ψ) α ∷ ∗
f ∷ α → β ↦ (fmap ) f ∷ (φ :.: ψ) α → (φ :.: ψ) β . fmap ) f ∷ (φ :.: ψ) α → (φ :.: ψ) β

औपचारिक रूप से, हमें यह सत्यापित करने की आवश्यकता है कि मैपिंग की यह जोड़ी अपने आप में हास्क श्रेणी का एक अंतःसंक्रमण है, अर्थात यह एकल आकारवाद और उसमें आकृति विज्ञान की संरचना को संरक्षित करता है, लेकिन चूंकि एक fmap सहेजता है, तो क्रमिक रूप से लागू किए गए fmap को बचाएगा:

 (fmap . fmap) id ≡ fmap (fmap id) ≡ fmap id ≡ id (fmap . fmap) (f . g) ≡ ≡ fmap (fmap (f . g)) ≡ ≡ fmap ((fmap f) . (fmap g)) ≡ ≡ (fmap (fmap f)) . (fmap (fmap g)) ≡ ≡ ((fmap . fmap) f) . ((fmap . fmap) g) 

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

इसलिए, आकृति के रूप में एक हास वस्तु और एंडोफुन्क्टरों के साथ एक श्रेणी का निर्माण करने के लिए, यह दो स्वयंसिद्धों की जांच करने के लिए रहता है:

• संघटन रचना
  

    ((φ :.: ψ) :.: ω) α ≡ (φ :.: ψ) (ω α) ≡ ≡ φ (ψ (ω α)) ≡ ≡ φ ((ψ :.: ω) α) ≡ (φ :.: (ψ :.: ω)) α 

  (fmap पर कार्रवाई (fmap φ . fmap ) एक साधारण रचना है, हमने पिछली बार इसकी संगति का परीक्षण किया था।
• एक एकल रूपवाद की निष्पक्षता
  

    (φ :.: Id) α ≡ φ (Id α) ≡ φ α ≡ Id (φ α) ≡ (Id :.: φ) α fmap . id ≡ id ≡ id . fmap 

सब ठीक है!

अखंड संरचना

वास्तव में, मोनॉयड्स के साथ हमारा परिचित पहले ही हो चुका है, क्योंकि ऊपर वर्णित श्रेणी एक मोनॉयड है। चलिए इसके बारे में अनावश्यक जानकारी को फ़िल्टर करते हैं और केवल परिभाषा छोड़ते हैं:

एक मोनॉइड एकल ऑब्जेक्ट श्रेणी है

इतना सरल। इस शब्दांकन से यह तुरंत स्पष्ट हो जाता है कि इसका ऐसा नाम क्यों है: "मोनो" का अर्थ है "एक"।

मैं एक स्पष्ट मोनॉइड का एक और उदाहरण दूंगा। एक Int साथ हस्क श्रेणी की एक उपश्रेणी पर विचार करें। आकृति विज्ञान के रूप में हम निम्नलिखित रूप के कार्य करते हैं λn → n + k या संक्षेप में (+k) प्रत्येक k ∷ Int , i.e. (+(-1)) , (+7) , (+100500) , आदि। सामान्य रचना और (+0) ≡ id a (+0) ≡ id , एक श्रेणी प्राप्त की जाती है। आप संख्या रेखा पर Int के प्रकार के सभी मूल्यों और उन पर इन आकारिकी के प्रभाव की कल्पना कर सकते हैं:

  Int: … -5 -4 -3 -2 -1 0 1 … (+(-2)) ∷ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Int: … -3 -2 -1 0 1 2 3 … (+3) ∷ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Int: … 0 1 2 3 4 5 6 … 

अर्थात्, नेत्रहीन, ये किसी दिए गए पदों द्वारा मूल ( 0 ) की पारियां हैं, हालांकि सामान्य रूप से संख्यात्मक रेखा समान रहती है। हमें श्रेणी की संरचना क्या है: सबसे पहले, एक एकल रूपवाद है जो जगह में सब कुछ छोड़ देता है, दूसरे, आकृति विज्ञान की एक संरचना है, यह साहचर्य है और id इसके संबंध में तटस्थ है। यदि m और n दो पूर्णांक हैं, तो रचना इस प्रकार है:

 (+m) . (+n) ≡ (+(m+n)) 

यह वास्तव में, यह एक राशि के रूप में कार्य करता है। आप प्रत्येक आकृतिवाद (+m) बारे में सोच सकते हैं कि बस संख्या m (जहां हमने मूल को स्थानांतरित किया: (+m) 0 ≡ m the (+m) 0 ≡ m ), फिर "रचना" m और n वास्तव में उनका योग है: (m+n) , और एक एकल रूपवाद केवल शून्य है।

यह दृश्य एक मोनॉइड की सेट-थेरैटिक परिभाषा से मेल खाता है:

एक मोनॉइड एक सेट से मिलकर एक ट्रिपल है, इस सेट पर एक साहचर्य बाइनरी ऑपरेशन और इस ऑपरेशन के संबंध में एक तत्व तटस्थ

इस उदाहरण में, यह ऐसा त्रिगुण है: (Int, (+), 0) ।

 (l + m) + n ≡ l + (m + n) m + 0 ≡ m ≡ 0 + m 

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

अब हम हास्केल में Monoid वर्ग पर एक नज़र Monoid :

 class Monoid μ where mappend ∷ μ → μ → μ mempty ∷ μ 

जहां μ पर विचार के तहत सेट किया जाता है, mappend वह ऑपरेशन है जो साहचर्य होना चाहिए, mempty वह तत्व है जो mappend संबंध में तटस्थ होना चाहिए। ट्रिपल (Int, (+), 0) इस वर्ग का अवतार प्रत्यक्ष होगा:

 instance Monoid Int where mappend = (+) mempty = 0 

इसी तरह किसी अन्य ट्रिपल के लिए, उदाहरण के लिए (Float, (*), 1) या ([α], (++), []) या (Bool, (||), False) , कहाँ || - तार्किक "या"। लेकिन हम स्पष्ट परिभाषा का एहसास कर सकते हैं, एक बार फिर उनके संबंधों का प्रदर्शन:

 type Mor α = α → α instance Monoid (Mor α) where mappend = (.) mempty = id 

इस स्थिति में, टाइप α ∷ ∗ Hask श्रेणी का एक ऑब्जेक्ट है, इस ऑब्जेक्ट पर Mor α प्रकार के कार्य रूप हैं। सामान्य रचना और एकल आकारिकी id वे एक वस्तु के साथ एक श्रेणी बनाते हैं, अर्थात एक मोनॉइड।

Data.Monoid मॉड्यूल में Endo प्रकार के लिए एक समान अवतार है। वैसे, इस मॉड्यूल में लगभग सभी अवतार "आवरणों में" प्रकार के लिए बनाए गए हैं। ऐसा इसलिए है क्योंकि एक ही सेट पर मोनोइडल संरचना को अलग-अलग तरीकों से पेश किया जा सकता है। उदाहरण के लिए, Int प्रकार के लिए, माना संरचना (Int, (+), 0) (cf. Sum ) के अलावा, हम भी विचार कर सकते हैं (Int, (*), 1) (cf. Product ), और Bool प्रकार के लिए, उपरोक्त उल्लिखित (Bool, (||), False) ( Any देखें) (Bool, (&&), True) ( All देखें)।

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

निष्कर्ष

यह पाठक को लग सकता है कि मैंने एक मोनॉइड की इन विभिन्न परिभाषाओं के साथ सब कुछ उल्टा कर दिया, लेकिन मैं सिर्फ यह दिखाना चाहता था कि संरचना स्वयं महत्वपूर्ण है, न कि यह क्या बनाया गया है: सेट के तत्वों पर, श्रेणी के आकार या कुछ और। ।

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

हम पहले से ही आकृति विज्ञान के बारे में जानते हैं, वस्तुओं के बीच के तीर के रूप में, हम श्रेणियों के बीच तीरों की तरह फंक्शनलर्स के बारे में जानते हैं। और फंक्शनलर्स के बीच तीरों की प्रकृति क्या है? इन तीरों को प्राकृतिक परिवर्तन कहा जाता है और मैं अगली बार उनके बारे में बात करूंगा।

इस लेख को सारांशित करने के लिए, मैं एक बार फिर से विचार की गई मुख्य अवधारणाओं को दोहराना चाहता हूं और उन्हें एक साथ जोड़ना चाहता हूं:

हस्क श्रेणी के एंडोफुन्क्टरों को एक साथ फंक्शनलर्स की रचना और एक समान फ़नकार की एक मोनोड संरचना होती है

जब यह (कड़ाई से) मोनॉयडल श्रेणी की बात आती है, तो यह महत्वपूर्ण वाक्यांश हमारे लिए बेहद उपयोगी साबित होगा, जिसे हम फंक्शनलर्स और प्राकृतिक परिवर्तनों से बनाएंगे।