Haskell Language
श्रेणी का सिद्धांत

अमूर्तता को व्यवस्थित करने के लिए एक प्रणाली के रूप में श्रेणी सिद्धांत

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

एक उदाहरण

Functor typeclass का कहना है कि अगर एक प्रकार F को दर्शाता है Functor (जिसके लिए हम लिख Functor F ) तो हम एक सामान्य ऑपरेशन है

fmap :: (a -> b) -> (F a -> F b)

जो हमें F ऊपर "मैप" करने देता है। मानक (लेकिन अपूर्ण) अंतर्ज्ञान यह है कि F a a प्रकार का मान रखने वाला एक कंटेनर a और a fmap हमें इन निहित तत्वों में से प्रत्येक में परिवर्तन लागू करने देता है। एक उदाहरण Maybe

instance Functor Maybe where
  fmap f Nothing = Nothing     -- if there are no values contained, do nothing
  fmap f (Just a) = Just (f a) -- else, apply our transformation

इस अंतर्ज्ञान को देखते हुए, एक आम सवाल "क्यों फोन नहीं है Functor कुछ की तरह स्पष्ट Mappable ?"।

श्रेणी सिद्धांत का एक संकेत

कारण यह है कि फ़नकार श्रेणी के सिद्धांत में सामान्य संरचनाओं के एक सेट में फिट बैठता है और इसलिए Functor "फ़ंक्टर" कहकर हम देख सकते हैं कि यह ज्ञान के इस गहरे शरीर से कैसे जुड़ता है।

विशेष रूप से, श्रेणी सिद्धांत एक स्थान से दूसरे स्थान पर तीरों के विचार से अत्यधिक चिंतित है। हास्केल में, तीरों का सबसे महत्वपूर्ण समूह फ़ंक्शन a -> b । श्रेणी थ्योरी में अध्ययन के लिए एक सामान्य बात यह है कि एक सेट का तीर दूसरे सेट से कैसे संबंधित होता है। विशेष रूप से, किसी भी प्रकार के निर्माता F , आकृति F a -> F b के आकार के तीर का सेट भी दिलचस्प है।

तो एक फ़नकार कोई भी F ऐसा है जो सामान्य हास्केल तीर a -> b और F -specific तीर F a -> F b । कनेक्शन को fmap द्वारा परिभाषित किया fmap और हम कुछ कानूनों को भी मान्यता देते हैं जिन्हें पकड़ना चाहिए

forall (x :: F a) . fmap id x == x

forall (f :: a -> b) (g :: b -> c) . fmap g . fmap f = fmap (g . f)

ये सभी कानून Functor की श्रेणी थ्योरेटिक व्याख्या से स्वाभाविक रूप से उत्पन्न होते हैं और स्पष्ट रूप से आवश्यक नहीं होंगे यदि हम केवल "तत्वों पर मानचित्रण" के संबंध में Functor बारे में सोचते हैं।

एक श्रेणी की परिभाषा

एक श्रेणी C शामिल हैं:

• Obj(C) नामक वस्तुओं का एक संग्रह;
• उन वस्तुओं के बीच आकारिकी का एक संग्रह (जिसे Hom(C) कहा जाता Hom(C) । यदि a और b Obj(C) , तो Hom(C) में एक आकारवाद f आमतौर पर f : a -> b , और a और b बीच सभी आकारिकी के संग्रह को चिह्नित किया जाता है hom(a,b) ;
• एक विशेष रूपवाद जिसे पहचान रूपवाद कहा जाता है - हर a : Obj(C) एक रूपवाद id : a -> a मौजूद है id : a -> a ;
• एक रचना संचालक ( . ), दो रूपकों को ले रहा है f : a -> b , g : b -> c और एक रूपवाद का निर्माण a -> c

जो निम्नलिखित कानूनों का पालन करते हैं:

For all f : a -> x, g : x -> b, then id . f = f and g . id = g

For all f : a -> b, g : b -> c and h : c -> d, then h . (g . f) = (h . g) . f

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

हास्केल में, Category को नियंत्रण में एक टाइपकास्ट के रूप में परिभाषित किया गया है। Category :

-- | A class for categories.
--   id and (.) must form a monoid.
class Category cat where
    -- | the identity morphism
    id :: cat a a

    -- | morphism composition
    (.) :: cat b c -> cat a b -> cat a c

इस मामले में, cat :: k -> k -> * आकारवाद संबंध को दर्शाता है - अगर कोई और केवल cat ab बसा हुआ है, तो एक आकृतिवाद cat ab मौजूद है (अर्थात इसका मूल्य है)। a , b और c सभी Obj(C) । Obj(C) का प्रतिनिधित्व स्वयं के प्रकार k द्वारा किया जाता है - उदाहरण के लिए, जब k ~ * , जैसा कि आमतौर पर होता है, ऑब्जेक्ट प्रकार होते हैं।

हास्केल में एक श्रेणी का विहित उदाहरण फ़ंक्शन श्रेणी है:

instance Category (->) where
  id = Prelude.id
  (.) = Prelude..

एक अन्य आम उदाहरण है Category के Kleisli एक के लिए तीर Monad :

newtype Kleisli m a b = Kleisli (a -> m b)

class Monad m => Category (Kleisli m) where
  id = Kleisli return
  Kleisli f . Kleisli g = Kleisli (f >=> g)

एक श्रेणी के रूप में हास्केल प्रकार

श्रेणी की परिभाषा

हास्केल प्रकारों के बीच फ़ंक्शन के साथ प्रकार (लगभग a) एक श्रेणी। हमारे पास प्रत्येक वस्तु (प्रकार) के लिए एक पहचान आकारवाद (कार्य) ( id :: a -> a ) a ; और आकारिकी की संरचना ( (.) :: (b -> c) -> (a -> b) -> a -> c ), जो श्रेणी कानूनों का पालन करते हैं:

f . id = f = id . f
h . (g . f) = (h . g) . f 

हम आमतौर पर इस श्रेणी को हास्क कहते हैं ।

Isomorphisms

श्रेणी सिद्धांत में, हमारे पास एक रूपवाद है जब हमारे पास एक आकृतिवाद होता है जिसका उलटा होता है, दूसरे शब्दों में, एक आकृतिवाद होता है जिसे पहचान बनाने के लिए इसके साथ जोड़ा जा सकता है। हास्क में इस राशि के जोड़ की आकृति का f , g ऐसा है कि:

 f . g == id == g . f

यदि हमें दो प्रकार के बीच इस तरह के आकारिकी की एक जोड़ी मिलती है, तो हम उन्हें एक दूसरे को आइसोमॉर्फिक कहते हैं।

दो आइसोमॉर्फिक प्रकारों का एक उदाहरण ((),a) और a लिए a । हम दो आकारिकी का निर्माण कर सकते हैं:

f :: ((),a) -> a
f ((),x) = x

g :: a -> ((),a)
g x = ((),x)

और हम उस f . g == id == g . f जांच कर सकते हैं f . g == id == g . f ।

functors

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

F :: * -> *

श्रेणीबद्ध फन्क्टर कानूनों का पालन करना (पहचान और संरचना को संरक्षित रखना) हास्केल फन्टर कानूनों का पालन करने के बराबर है:

fmap (f . g) = (fmap f) . (fmap g)
fmap id = id

इसलिए, हमारे पास, उदाहरण के लिए, कि [] , Maybe या (-> r) हास्क में फंक्शनल हैं ।

monads

श्रेणी सिद्धांत में एक सनद एंडोफुन्क्टरों की श्रेणी में एक मोनॉयड है । इस श्रेणी में एंडोफुक्टर्स के रूप में वस्तुओं F :: * -> * और प्राकृतिक परिवर्तनों (उनके बीच परिवर्तन forall a . F a -> G a ) आकारिकी के रूप में है।

एक मोनॉइड ऑब्जेक्ट को एक मोनोइडल श्रेणी पर परिभाषित किया जा सकता है, और एक प्रकार के दो आकार होते हैं:

zero :: () -> M
mappend :: (M,M) -> M

हम इसे मोटे तौर पर हास्क एंडोफिनर्स की श्रेणी में अनुवाद कर सकते हैं:

return :: a -> m a
join :: m (m a) -> m a 

और, मोनड कानूनों का पालन करने के लिए श्रेणीबद्ध मोनॉइड ऑब्जेक्ट कानूनों का पालन करने के बराबर है।

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

Hask में प्रकार के उत्पाद

श्रेणीबद्ध उत्पाद

श्रेणी सिद्धांत में, दो वस्तुओं के उत्पाद X , Y एक और वस्तु Z है, जिसमें दो अनुमान हैं : Z: Z → X और Y: Z → Y ; ऐसा है कि किसी अन्य वस्तु से किसी अन्य दो आकारिकी उन अनुमानों के माध्यम से विशिष्ट रूप से विघटित होती है। दूसरे शब्दों में, अगर वहाँ मौजूद है f₁: W → X और f W: W → Y , एक अद्वितीय रूपवाद मौजूद है g: W → Z जैसे कि ○ = g = f₁ और there = g = f₂ ।

Hask में उत्पाद

यह Haskell प्रकारों के Hask श्रेणी में अनुवाद करता है, Z , A , B का उत्पाद है जब:

-- if there are two functions
f1 :: W -> A
f2 :: W -> B
-- we can construct a unique function
g  :: W -> Z
-- and we have two projections
p1 :: Z -> A
p2 :: Z -> B
-- such that the other two functions decompose using g
p1 . g == f1
p2 . g == f2

उत्पाद प्रकार दो प्रकार A , B , जो ऊपर बताए गए कानून का पालन करता है, दो प्रकारों (A,B) का टपल है, और दो अनुमानों fst और snd । हम जाँच कर सकते हैं कि यह उपरोक्त नियम का अनुसरण करता है, यदि हमारे पास दो कार्य f1 :: W -> A और f2 :: W -> B तो हम उनका अनुसरण करने के लिए विशिष्ट रूप से विघटित कर सकते हैं:

decompose :: (W -> A) -> (W -> B) -> (W -> (A,B))
decompose f1 f2 = (\x -> (f1 x, f2 x))

और हम जांच सकते हैं कि अपघटन सही है:

fst . (decompose f1 f2) = f1
snd . (decompose f1 f2) = f2

समरूपता तक अद्वितीयता

A और B के उत्पाद के रूप में (A,B) की पसंद अद्वितीय नहीं है। एक और तार्किक और समकक्ष विकल्प होगा:

data Pair a b = Pair a b

इसके अलावा, हम भी उत्पाद के रूप में (B,A) चुना जा सकता है, या यहां तक कि (B,A,()) , और हम उपरोक्त नियमों की तरह एक अपघटन कार्य भी पा सकते हैं:

decompose2 :: (W -> A) -> (W -> B) -> (W -> (B,A,()))
decompose2 f1 f2 = (\x -> (f2 x, f1 x, ()))

ऐसा इसलिए है क्योंकि उत्पाद आइसोमोर्फिज्म तक अद्वितीय नहीं बल्कि अद्वितीय है । A और B हर दो उत्पादों के बराबर नहीं होना चाहिए, लेकिन उन्हें आइसोमोर्फिक होना चाहिए। एक उदाहरण के रूप में, जिन दो अलग-अलग उत्पादों को हमने अभी परिभाषित किया है, (A,B) और (B,A,()) , आइसोमोर्फिक हैं:

iso1 :: (A,B) -> (B,A,())
iso1 (x,y) = (y,x,())

iso2 :: (B,A,()) -> (A,B)
iso2 (y,x,()) = (x,y)

अपघटन की विशिष्टता

यह टिप्पणी करना महत्वपूर्ण है कि अपघटन समारोह भी अद्वितीय होना चाहिए। ऐसे प्रकार हैं जो उत्पाद होने के लिए आवश्यक सभी नियमों का पालन करते हैं, लेकिन अपघटन अद्वितीय नहीं है। एक उदाहरण के रूप में, हम अनुमानों fst fst . snd साथ (A,(B,Bool)) fst (A,(B,Bool)) का उपयोग करने का प्रयास कर सकते हैं fst . snd A और B उत्पाद के रूप में fst . snd :

decompose3 :: (W -> A) -> (W -> B) -> (W -> (A,(B,Bool)))
decompose3 f1 f2 = (\x -> (f1 x, (f2 x, True)))

हम जाँच सकते हैं कि यह काम करता है:

fst         . (decompose3 f1 f2) = f1 x
(fst . snd) . (decompose3 f1 f2) = f2 x

लेकिन यहाँ समस्या यह है कि हम एक और अपघटन लिख सकते हैं, अर्थात्:

decompose3' :: (W -> A) -> (W -> B) -> (W -> (A,(B,Bool)))
decompose3' f1 f2 = (\x -> (f1 x, (f2 x, False)))

और, क्योंकि अपघटन अद्वितीय नहीं है , (A,(B,Bool)) बूल) हास्क में A और B का उत्पाद नहीं है

हास्क में प्रकारों की नकल

सहज बोध

दो प्रकार ए और बी के श्रेणीगत उत्पाद में टाइप ए या टाइप बी के उदाहरण के अंदर आवश्यक न्यूनतम जानकारी होनी चाहिए। अब हम देख सकते हैं कि दो प्रकारों का सहज ज्ञान युक्त Either ab होना चाहिए। अन्य उम्मीदवारों, जैसे कि Either a (b,Bool) , में अनावश्यक जानकारी का एक हिस्सा होगा, और वे न्यूनतम नहीं होंगे।

औपचारिक परिभाषा को सहानुभूति की स्पष्ट परिभाषा से लिया गया है।

श्रेणीबद्ध प्रतिलिपि

एक श्रेणीगत उत्पाद एक श्रेणीगत उत्पाद की दोहरी धारणा है। यह सीधे उत्पाद की परिभाषा में सभी तीरों को उल्टा करके प्राप्त किया जाता है। दो ऑब्जेक्ट्स एक्स , वाई का कॉपीराइट एक और ऑब्जेक्ट जेड है जिसमें दो समावेश हैं: i_1: X → Z और i_2: Y → Z ; इस तरह के एक्स और वाई से किसी भी अन्य दो आकारिकी उन वस्तुओं के माध्यम से विशिष्ट रूप से विघटित होते हैं। दूसरे शब्दों में, यदि दो आकारिकी f₁ हैं: X → W और f Y: Y → W , एक अद्वितीय रूपवाद मौजूद है g: Z → W ऐसा कि g ₁ i₁ = f₁ और g ○ i₂ = f there

हस्क में उत्पाद

हस्क श्रेणी में अनुवाद उत्पाद के अनुवाद के समान है:

-- if there are two functions
f1 :: A -> W
f2 :: B -> W
-- and we have a coproduct with two inclusions
i1 :: A -> Z
i2 :: B -> Z
-- we can construct a unique function
g  :: Z -> W
-- such that the other two functions decompose using g
g . i1 == f1
g . i2 == f2

Hask में दो प्रकार A और B का प्रतिपादक प्रकार या Either ab या अन्य किसी भी प्रकार का isomorphic है:

-- Coproduct
-- The two inclusions are Left and Right
data Either a b = Left a | Right b

-- If we have those functions, we can decompose them through the coproduct
decompose :: (A -> W) -> (B -> W) -> (Either A B -> W)
decompose f1 f2 (Left x)  = f1 x
decompose f1 f2 (Right y) = f2 y 

श्रेणी सिद्धांत के संदर्भ में हास्केल लागू

एक हास्केल के Functor एक किसी भी प्रकार मैप करने के लिए अनुमति देता है a एक प्रकार की (Hask की एक वस्तु) F a और यह भी एक समारोह के नक्शे a -> b प्रकार के साथ एक समारोह के लिए (एक Hask की आकारिता) F a -> F b । यह एक श्रेणी थ्योरी की परिभाषा से मेल खाता है, जो कि फनकार बुनियादी श्रेणी की संरचना को संरक्षित करता है।

एक मोनॉयडल श्रेणी एक ऐसी श्रेणी है जिसमें कुछ अतिरिक्त संरचना होती है:

• एक टेंसर उत्पाद ( Hask में प्रकार के उत्पाद देखें)
• एक टेंसर यूनिट (यूनिट ऑब्जेक्ट)

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

class Functor f => Monoidal f where
    mcat :: f a -> f b -> f (a,b)
    munit :: f ()

Applicative वर्ग इस के बराबर है Monoidal एक और इस तरह यह करने के मामले में लागू किया जा सकता:

instance Monoidal f => Applicative f where
    pure x = fmap (const x) munit
    f <*> fa = (\(f, a) -> f a) <$> (mcat f fa)