Haskell Language
बीजगणित लिखें

प्रकार बीजगणित में प्राकृतिक संख्याएँ

हम हास्केल प्रकारों और प्राकृतिक संख्याओं के बीच एक संबंध बना सकते हैं। यह कनेक्शन हर प्रकार के निवासियों को असाइन किया जा सकता है जिनके पास इसकी संख्या है।

परिमित संघ प्रकार

परिमित प्रकारों के लिए, यह देखने के लिए पर्याप्त है कि हम प्रत्येक संख्या के लिए एक प्राकृतिक प्रकार असाइन कर सकते हैं, जो कि कंस्ट्रक्टरों की संख्या के आधार पर है। उदाहरण के लिए:

type Color = Red | Yellow | Green

होगा ३ । और Bool टाइप 2 होगा।

type Bool = True | False

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

हमने देखा है कि कई प्रकार एक ही संख्या के अनुरूप होंगे, लेकिन इस मामले में, वे आइसोमॉर्फिक होंगे। यह कहना है कि एक जोड़ी आकारिकी f और g , जिनकी रचना दो प्रकारों को जोड़ने वाली पहचान होगी।

f :: a -> b
g :: b -> a

f . g == id == g . f

इस मामले में, हम कहेंगे कि प्रकार आइसोमॉर्फिक हैं । हम अपने बीजगणित में दो प्रकार के बराबर विचार करेंगे जब तक कि वे आइसोमोर्फिक हैं।

उदाहरण के लिए, संख्या दो के दो अलग-अलग निरूपण ट्रिवली आइसोमॉर्फिक हैं:

type Bit  = I    | O
type Bool = True | False

bitValue :: Bit -> Bool
bitValue I = True
bitValue O = False

booleanBit :: Bool -> Bit
booleanBit True  = I
booleanBit False = O

क्योंकि हम bitValue . booleanBit == id == booleanBit . bitValue देख सकते हैं bitValue . booleanBit == id == booleanBit . bitValue

एक और शून्य

संख्या 1 का प्रतिनिधित्व स्पष्ट रूप से केवल एक निर्माता के साथ एक प्रकार है। हास्केल में, यह प्रकार कैनोनिक रूप से टाइप () , जिसे यूनिट कहा जाता है। केवल एक कंस्ट्रक्टर के साथ हर दूसरा प्रकार isomorphic to () ।

और 0 का हमारा प्रतिनिधित्व एक प्रकार का होगा जो बिना निर्माण के होगा। यह हास्केल में शून्य प्रकार है, जैसा कि Data.Void में परिभाषित किया Data.Void । यह एक अनहैबिटेड प्रकार के बराबर होगा, जो डेटा कंस्ट्रक्टर्स को मिटा देगा:

data Void

जोड़ और गुणा

इस प्रकार के बीजगणित में जोड़ और गुणन समतुल्य होते हैं। वे टैग किए गए यूनियनों और उत्पाद प्रकारों के अनुरूप हैं ।

data Sum a b = A a | B b
data Prod a b = Prod a b

हम देख सकते हैं कि कैसे हर प्रकार के निवासियों की संख्या बीजगणित के संचालन से मेल खाती है।

समान रूप से, हम Either और (,) जोड़ सकते हैं इसके अलावा और गुणा के लिए टाइप कंस्ट्रक्टर। वे हमारे पहले से परिभाषित प्रकारों के लिए समसामयिक हैं:

type Sum' a b = Either a b
type Prod' a b = (a,b)

इसके अलावा और गुणन के अपेक्षित परिणामों को बीजगणित के बाद आइसोमोर्फिज्म तक टाइप किया जाता है। उदाहरण के लिए, हम 1 + 2, 2 + 1 और 3 के बीच एक समरूपता देख सकते हैं; as 1 + 2 = 3 = 2 + 1।

data Color = Red | Green | Blue

f :: Sum () Bool -> Color
f (Left ())     = Red
f (Right True)  = Green
f (Right False) = Blue

g :: Color -> Sum () Bool
g Red   = Left ()
g Green = Right True
g Blue  = Right False

f' :: Sum Bool () -> Color
f' (Right ())   = Red
f' (Left True)  = Green
f' (Left False) = Blue

g' :: Color -> Sum Bool ()
g' Red   = Right ()
g' Green = Left True
g' Blue  = Left False

जोड़ और गुणा के नियम

कम्यूटिटी, समरूपता और वितरण के सामान्य नियम मान्य हैं क्योंकि निम्नलिखित कार्यों के बीच तुच्छ समरूपताएं हैं:

-- Commutativity
Sum a b           <=> Sum b a
Prod a b          <=> Prod b a
-- Associativity
Sum (Sum a b) c   <=> Sum a (Sum b c)
Prod (Prod a b) c <=> Prod a (Prod b c)
-- Distributivity
Prod a (Sum b c)  <=> Sum (Prod a b) (Prod a c)

पुनरावर्ती प्रकार

सूचियाँ

सूचियों को इस प्रकार परिभाषित किया जा सकता है:

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

यदि हम इसे अपने प्रकार के बीजगणित में अनुवाद करते हैं, तो हमें मिलता है

सूची (ए) = 1 + ए * सूची (ए)

लेकिन अब हम इस अभिव्यक्ति को कई बार सूची (ए) में बदल सकते हैं:

सूची (a) = 1 + a + a + a + a * a + a * a * a * a + ...

यह समझ में आता है यदि हम एक सूची को एक प्रकार के रूप में देखते हैं जिसमें केवल एक मान हो सकता है, जैसा कि [] ; [x] रूप में टाइप a का प्रत्येक मान; [x,y] रूप में टाइप a दो मान; और इसी तरह। सूची की सैद्धांतिक परिभाषा जो हमें वहां से मिलनी चाहिए:

-- Not working Haskell code!
data List a = Nil
            | One a
            | Two a a
            | Three a a a 
            ...

पेड़

हम उदाहरण के लिए, बाइनरी पेड़ों के साथ एक ही काम कर सकते हैं। अगर हम उन्हें परिभाषित करते हैं:

data Tree a = Empty | Node a (Tree a) (Tree a)

हमें अभिव्यक्ति मिलती है:

ट्री (ए) = 1 + ए * ट्री (ए) * ट्री (ए)

और यदि हम बार-बार एक ही प्रतिस्थापन करते हैं, तो हम निम्नलिखित अनुक्रम प्राप्त करेंगे:

ट्री (ए) = 1 + ए + 2 (ए * ए + ५) (ए * ए) +१४ (ए * ए * ए * ए) + ...

हम जो गुणांक यहां प्राप्त करते हैं, वह कैटलन संख्या अनुक्रम के अनुरूप है, और n-वें साह संख्या ठीक n नोड्स के साथ संभव बाइनरी पेड़ों की संख्या है।

संजात

एक प्रकार का व्युत्पन्न इसके प्रकार का एक-छेद संदर्भ है। यह वह प्रकार है जिसे हम प्राप्त करेंगे यदि हम हर संभव बिंदु में एक प्रकार का चर गायब कर दें और परिणाम प्राप्त करें।

एक उदाहरण के रूप में, हम ट्रिपल प्रकार (a,a,a) ले सकते हैं, और इसे प्राप्त कर सकते हैं

data OneHoleContextsOfTriple = (a,a,()) | (a,(),a) | ((),a,a)

यह व्युत्पत्ति की हमारी सामान्य परिभाषा के साथ सुसंगत है, जैसे:

d / da (a * a * a = = 3 * a *

इस विषय पर और अधिक इस लेख पर पढ़ा जा सकता है।

कार्य

हमारे बीजगणित में कार्यों को घातांक के रूप में देखा जा सकता है। हम देख सकते हैं, अगर हम एक प्रकार ले a n उदाहरणों और एक प्रकार के साथ b मीटर उदाहरणों, प्रकार के साथ a -> b मीटर n उदाहरणों की शक्ति करना होगा।

एक उदाहरण के रूप में, Bool -> Bool आइसोमोर्फिक टू (Bool,Bool) बूल, बूल (Bool,Bool) , जैसा कि 2 * 2 = 2 2।

iso1 :: (Bool -> Bool) -> (Bool,Bool)
iso1 f = (f True,f False)

iso2 :: (Bool,Bool) -> (Bool -> Bool)
iso2 (x,y) = (\p -> if p then x else y)