परिचय

ऐसा लगता है कि प्रोग्रामिंग में साधु सदी का रहस्य बन गए हैं। और इसके दो कारण हैं:

• श्रेणी सिद्धांत का अपर्याप्त ज्ञान;
• कई लेखक श्रेणियों का उल्लेख नहीं करने की कोशिश करते हैं।

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

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

मुझे यकीन है कि श्रेणियों के संदर्भ में मठ लगभग प्राथमिक हैं।

सामग्री

1. श्रेणी
2. functor
3. प्राकृतिक परिवर्तन
4. इकाई
5. अपवाद और स्थिति के मठ
6. प्रोग्रामिंग में मोनाड्स
7. संदर्भ

श्रेणी

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

कोई फर्क नहीं पड़ता कि वस्तु या तीर क्या है, केवल निम्नलिखित गुण महत्वपूर्ण हैं:

एक तीर वस्तुओं के बीच खींचा जाता है (इस मामले में, वस्तु एक और एक ही हो सकती है); इसे निम्नानुसार दर्शाया गया है: f: a → b , जहां f एक तीर है, और a और b ऑब्जेक्ट हैं।

1. तीर f के लिए: a → b और g: b → c, ऐसे तीर h मौजूद है : a → c जिसे रचना कहा जाता है: h = g ° f ।
   
2. प्रत्येक ऑब्जेक्ट ए के लिए, एक यूनिट एरो है , आईडी _a : a → a , जैसे कि किसी भी f के लिए: a → b निम्नलिखित सत्य है:
   f ° id _a = f और किसी भी g: c → के लिए हमारे पास id _a ° g = g है ।
3. रचना सहयोगी है: f ° (g ° h) = (f ° g) ° h ।

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

श्रेणी के उदाहरण

"क्लासिक" श्रेणियों के उदाहरण:

1. सेट सभी सेटों की श्रेणी है। इसकी वस्तुएं सभी सेट हैं, और आकारिकी सेट पर कार्य हैं।
2. सेटफ उनके बीच सभी परिमित सेटों और कार्यों की श्रेणी है।
3. Rel एक ऐसी श्रेणी है जहाँ ऑब्जेक्ट सभी सेट होते हैं, और बाइनरी संबंध मोर्फिज़्म की भूमिका निभाते हैं। एक आंतरिक संघ के माध्यम से रचना का विलय किया जाता है।
4. भाग सभी सेटों की श्रेणी है और आकृति विज्ञान के रूप में आंशिक कार्य करता है। X से Y तक का आंशिक कार्य, X _o Y X से Y के सबसेट से एक फ़ंक्शन है:
   
   
   
5. टॉप सभी टोपोलॉजिकल स्पेस की श्रेणी है और उनके बीच निरंतर कार्य करता है।

ऐसी श्रेणियां भी हैं जो केवल सामान्य सिद्धांत नहीं हैं:

1. किसी भी समूह को एक श्रेणी के रूप में माना जा सकता है: तत्वों का एक समूह एक वस्तु पर आकारिकी है।
   पहचान समारोह समूह का तटस्थ तत्व है। और रचना कई गुना है।
2. आंशिक रूप से ऑर्डर किए गए सेट को एक श्रेणी के रूप में दर्शाया जा सकता है। सेट के तत्व ऑब्जेक्ट हैं। प्रत्येक जोड़ी a, b के लिए एक तीर a → b जोड़ें ताकि एक <b और एक इकाई a → प्रत्येक a के लिए a ।
   प्रत्येक जोड़ी की वस्तुओं के लिए एक से अधिक तीर नहीं हैं और, चूंकि आंशिक क्रम सकर्मक है, हमारे पास एक रचना ( एक <b, b <c => a <c ) है, यानी आप इसकी समालोचना के बारे में चिंता नहीं कर सकते।
3. पिछले उदाहरण के एक विशेष मामले के रूप में, पूर्णांक [N ... M] के सेट को एक श्रेणी माना जा सकता है।
4. किसी भी निर्देशित ग्राफ को एक श्रेणी में तब्दील किया जा सकता है, अगर हम इसके रास्तों को तीर के रूप में मानते हैं। खाली पथ एक एकल आकारिकी है, और पथ का संघटन एक रचना होगी।
5. प्राकृतिक संख्याएं वस्तुओं के रूप में, तीर के रूप में परिपक्व होती हैं। कोई भी मैट्रिक्स NxM एक तीर N → M होगा। मैट्रिक्स गुणन रचना की भूमिका निभाएगा, और पहचान मैट्रिक्स NxN पहचान तीर N → N होगा।

अतिरिक्त सामग्री

बस एक आइसोमोर्फिज्म को एक श्रेणी में परिभाषित करें - यह एक है जिसमें एक उलटा है। यही है, इस घटना में कि हमारे पास f: a → b और g: b → a , और f ° g = id _b और g ° f = id _a संतुष्ट हैं। हमें बाद में इस परिभाषा की आवश्यकता होगी। मोनोमोर्फिज्म और एपिमोर्फिज्म को परिभाषित करना भी संभव है, यह कुछ अधिक जटिल है और इस लेख के दायरे से परे है।

पिछले अध्याय से वस्तुओं [0 ... N] को याद रखें? विशेष श्रेणियां हैं: 1 = [0] और 2 = [0 ... 1] । पहला एक एकल आकृतिवाद के साथ एक वस्तु है, दूसरा दो वस्तुओं और तीन आकार का है।

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

functor

फ़नकार एक श्रेणी को दूसरी श्रेणी में रखता है। ऐसा करने के लिए, हमें वस्तुओं को पहली श्रेणी से दूसरी श्रेणी में और तीर (आकारिकी) को पहली श्रेणी से दूसरे श्रेणी के तीर पर सुसंगत तरीके से मैप करने की आवश्यकता है।

हम किस स्थिरता की उम्मीद करते हैं? X और Y दो श्रेणियां हैं; एक फंक्टर को परिभाषित करें F: X → Y। अब हमें X से Y तक की वस्तुओं को मैप करने की आवश्यकता है, X में प्रत्येक में ऑब्जेक्ट F (a) के लिए Y और X में प्रत्येक तीर के लिए Y में तीर F (f) होना चाहिए ।

स्थिरता के लिए, निम्नलिखित नियमों का पालन किया जाना चाहिए:

• एफ के लिए: एक → बी, हमारे पास एफ (एफ): एफ (ए) → एफ (बी) - डोमेन और कोडनेम सहेजे गए हैं;
• आईडी के लिए _a : a → हमारे पास F (id _a ) = id _{F (a)} : F (a) → F (a) - यूनिट सेव है;
• एफ के लिए: एक → बी और जी: बी → सी एफ (जी ° एफ) = एफ (जी) ° एफ (एफ) , रचना संरक्षित है।

फंक्शनलर्स की संरचना स्पष्ट रूप से परिभाषित की गई है: शुरुआत में पहले फ़नकार को लागू किया जाता है, फिर बाकी को।

फनकार उदाहरण

1. श्रेणी X के लिए पहचान फ़नकार। यद्यपि पहचान X → X वस्तुओं और तीरों को अपरिवर्तित रखता है, फिर भी यह एक फ़नकार है।
2. सेटफ सेट एक ऐसा फन्नेकार है जिसमें सेटफ को सेट में शामिल किया जाता है, अपने आप में परिमित सेटों को मैप करता है, कार्यों के साथ भी। ध्यान दें कि यह एक समान फ़नकार नहीं है।
3. सेट करें → पिछले उदाहरण के समान शीर्ष , यह फ़नकार सेट को शीर्ष का हिस्सा बनाता है। प्रत्येक सेट को असतत टोपोलॉजिकल स्पेस में मैप किया जाता है।
4. किसी भी सेट A के लिए, हम निम्नलिखित फ़नकार को परिभाषित कर सकते हैं:
   (- xA): सेट → सेट - यह किसी भी सेट X को कार्टेशियन उत्पाद X × A में मैप करता है ।
   
5. किसी भी सेट A के लिए, कोई फ़नकार P _A : सेट → सेट को परिभाषित कर सकता है, जो किसी भी सेट X को X ^{A में} मैप करता है - A से X के कार्यों का सेट।
   
6. सेट भाग आंशिक कार्यों के साथ सेट में सेट का परिचय देता है - उनमें सेट और फ़ंक्शन प्रदर्शित करता है।
7. आइटम 6 का कनक्लूजन फन्क्टर + नूल : पार्ट → सेट है - यह फनकार प्रत्येक सैट X each (X + Null) में एक " Null एक्सटेंशन" जोड़ता है ताकि आंशिक फंक्शन X → Y फंक्शन के लिए मैप्स (X + Null) → (Y + नल) ।

व्यायाम करें । आंशिक कार्यों के लिए समान एक्सटेंशन को परिभाषित करें।

आइए छोटी श्रेणियों और उनके कार्यों को देखें।

1. यदि हम समूहों को श्रेणियों के रूप में लेते हैं, तो उनके कार्यकलाप क्या होंगे? फ़नकार को एक एकल रूपवाद और संरचना को बनाए रखना चाहिए। इसलिए, एक फ़नकार एक समूह समरूपता है।
2. कोई भी फ़ंक्शन जो दो आंशिक रूप से ऑर्डर किए गए सेटों के बीच ऑर्डर (तथाकथित मोनोटोन) को संरक्षित करता है, एक फ़नकार है।
3. उन्मुख रेखांकन और किनारों को संरक्षित करने वाले नक्शे की एक जोड़ी लें। हम इस मैपिंग को एक ऐसे फंक्शन तक बढ़ा सकते हैं, जो एक ग्राफ से दूसरे ग्राफ पर एक पथ पर मैप करता है। यह फ़ंक्शन, परिभाषा के अनुसार, लिंक और खाली रास्तों को बचाता है, इसलिए यह ग्राफ़ द्वारा बनाई गई एक श्रेणी से दूसरे तक एक फ़नकार है।
4. श्रेणी 1 याद है? और इसलिए, 1 से श्रेणी सी तक का फनकार कैसा दिखेगा? 1 में केवल एक वस्तु और एक समान रूपवाद है। इस प्रकार, इस फन्नेकार की परिभाषा सी और इसके विपरीत से एक वस्तु को चुनने के बराबर है - श्रेणी सी में किसी भी वस्तु एक्स के लिए हम एक फनकार प्वाइंट _एक्स : 1 → सी को परिभाषित कर सकते हैं ।

प्राकृतिक परिवर्तन

यह सबसे कठिन हिस्सा होना चाहिए। मान लें कि हमारे पास दो फ़ंक्शनलर्स हैं एफ, जी: एक्स → वाई। प्राकृतिक परिवर्तन each: F → G तब परिभाषित किया जाता है जब प्रत्येक वस्तु x ∈ X के लिए एक तीर होता है η (x): F (x) → G (x) Y में और हमारे पास निम्नलिखित गुण हैं:

• सभी f के लिए: a → b समानता रखती है: G (f) ° a (a) = η (b) ° F (f) ।

इसलिए, इसे "प्राकृतिक" कहा जाता है - यह तीरों पर फ़ंक्शंस के कार्यों के साथ लगातार कार्य करता है।

प्राकृतिक परिवर्तनों के उदाहरण

1. बिंदु फनकार याद है? और इसलिए, यदि श्रेणी C में हमारे पास एक तीर f: a → b है , तो यह तीर बिंदु _a से बिंदु _b तक के प्राकृतिक परिवर्तन को परिभाषित करता है। यह एक बिंदु फ़नकार रूपांतरण और श्रेणी तीर के बीच एक-से-एक संबंध है।
2. दो सेट A और B और एक फ़ंक्शन f: A → B लें। यह फ़ंक्शन फ़ंक्शंस (- xA), (- xB): सेट → सेट के बीच प्राकृतिक परिवर्तन को परिभाषित करता है। (- xf): (- xA) → (- xB) निम्नलिखित सूत्र के अनुसार: (x, a) f (x, f (a)) ।
   
   आप इस परिभाषा को निम्न रूप में लिख सकते हैं:

   (define (cartesian f)
       (lambda (x a) (list x (f a))))
   

   A A → (.), (.) , (- xA) → 1, X : X ⨯ A → X.

A Set 1 → P_A. X Set; X X^A. , x X A X, x.

, :

(define (return x) (lambda (a) (x)))

C T: C → C : η: 1 → T μ: T ° T → T. T(η): T → T ° T , T η T(μ): (T ° T) ° T → T ° T.
:

1. T(η) ° μ T → T
   
   
   
2. T(μ) ° μ μ ° μ:
   

1. C , .
2. , G. M_G Set. :
   X ↦ X × G.
   u(X): X → X × G x (x, e), e .
   M_G(M_G(X)) = (id_X, m_G), m_G .
3. Set. , List, X (x₁, x₂, x₃...) X, . , u m. u_X: X → List(X) x ∊ X m_X: List(List(X)) → List(X) .

. , «computer science».

, - , , ?

( ) C: X → X , ∀ x ∊ X x <= C(x) C(C(x)) = C(x).

, , - , , - . - .

Part. A :
PlusNull: X ↦ (X+Null)

, Part Set. Set Part, .

? u_X: X → (X+Null) m_X: ((X+Null)+Null) → (X+Null).

, Null Null. Lisp :

(define (ux x) x)

(define (mx x) x)

, ( , , , ).

Set. A :

X ↦ (X × A)^A

A , , (X × A)^A X X, A → (A × X), , X.

? u_X: X → (A × X)^A x ∊ X , A x X.

Lisp:

(define (ux x)
    (lambda (a) (list a x)))

m_X: (A × (A × X)^A)^A → (A × X)^A?

m_X: (A × (A × X)^A)^A, A , ( A , X ). , , A?

Lisp:

(define (mx f)
    (let (tr1 out1)
        ((car f) (cadr f))) ;  f: A → (A × (A × X))^A
    (lambda (a)
        (let a1 (tr1 a))    ;   
        (let f2 (out1 a))   ;    
        (let (tr2 out2) ((car f2) (cadr f2))) ;   
            (list (tr2 a1) (out2 a1))))

: A A × (A × X)^A, A → A A → (A × X)^A, a a1 , A A × X .

. , .

, f: X → Y, X «», Y «».

, ; , 100% , . , « » .

, , .

NullObject NaN.
, X, (Y+Null), .

, , .

IO Haskell

Haskell IO, , .

. , . , A , , X .

. A String, «», «».
, , getc, , , putc, .

, .

1. .
2. , , .
3. “Comprehending Monads” Frederik Eaton — .
4. Haskell u return, m join
5. Haskell List .
6. map/reduce Google.