कैटामोर्फिज्म

Not to be confused with Anamorphism.

श्रेणी सिद्धांत में, कैटामोर्फिज्म की अवधारणा (प्राचीन ग्रीक से: κατά नीचे की ओर और μορφή रूप, आकार ) प्रारंभिक बीजगणित से किसी अन्य बीजगणित में अद्वितीय समरूपता को दर्शाता है।

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

परिभाषा

प्रारंभिक बीजगणित एफ-बीजगणित पर विचार करें|$F$-बीजगणित $(A,in)$ कुछ एंडोफन्क्टर के लिए $F$ अपने आप में कुछ श्रेणी (गणित) की। यहाँ $in$ से एक रूपवाद है $FA$ को $A$. चूंकि यह प्रारंभिक है, हम जानते हैं कि जब भी $(X,f)$ दूसरा है $F$-बीजगणित, यानी एक रूपवाद $f$ से $FX$ को $X$, एक अद्वितीय समरूपता है $h$ से $(A,in)$ को $(X,f)$. की श्रेणी की परिभाषा के अनुसार $F$-बीजगणित, यह $h$ से एक रूपवाद से मेल खाता है $A$ को $X$, परंपरागत रूप से भी निरूपित किया जाता है $h$, ऐसा है कि $h\circ in=f\circ Fh$. के सन्दर्भ में $F$-बीजगणित, प्रारंभिक वस्तु से विशिष्ट रूप से निर्दिष्ट रूपवाद को निरूपित किया जाता है $\mathrm {cata} \ f$ और इसलिए निम्नलिखित संबंध की विशेषता है:

• $h=\mathrm {cata} \ f$
• $h\circ in=f\circ Fh$

शब्दावली और इतिहास

साहित्य में पाया जाने वाला एक और संकेतन है $(\!|f|\!)$. उपयोग किए गए खुले ब्रैकेट को केला ब्रैकेट के रूप में जाना जाता है, जिसके बाद कैटामोर्फिज्म को कभी-कभी केला कहा जाता है, जैसा कि एरिक मीजर (कंप्यूटर वैज्ञानिक) एट अल में बताया गया है। प्रोग्रामिंग के संदर्भ में कैटामोर्फिज्म की धारणा को पेश करने वाले पहले प्रकाशनों में से एक एरिक मीजर (कंप्यूटर वैज्ञानिक) एट अल द्वारा लिखा गया पेपर "केले, लेंस, लिफाफे और कांटेदार तार के साथ कार्यात्मक प्रोग्रामिंग" था।जो स्क्विगोल औपचारिकता के संदर्भ में था। सामान्य श्रेणीबद्ध परिभाषा ग्रांट मैल्कम द्वारा दी गई थी।

उदाहरण

हम उदाहरणों की एक श्रृंखला देते हैं, और फिर हास्केल (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा में कैटामोर्फिज्म के लिए एक अधिक वैश्विक दृष्टिकोण देते हैं।

पुनरावृत्ति

पुनरावृत्ति-चरणीय नुस्खे प्रारंभिक वस्तु के रूप में प्राकृतिक संख्याओं की ओर ले जाते हैं।

फ़नकार पर विचार करें fmaybe डेटा प्रकार को मैप करना b एक डेटा प्रकार के लिए fmaybe b, जिसमें प्रत्येक पद की एक प्रति शामिल है b साथ ही एक अतिरिक्त पद Nothing (हास्केल में, यही है Maybe करता है)। इसे एक टर्म और एक फ़ंक्शन का उपयोग करके एन्कोड किया जा सकता है। तो मान लीजिए कि स्टेपअलजेब्रा के एक उदाहरण में एक फ़ंक्शन भी शामिल है fmaybe b को b, जो मानचित्र करता है Nothing एक निश्चित अवधि के लिए nil का b, और जहां कॉपी की गई शर्तों पर कार्रवाई की जाएगी next.

type StepAlgebra b = (b, b->b) -- the algebras, which we encode as pairs (nil, next)

data Nat = Zero | Succ Nat -- which is the initial algebra for the functor described above

foldSteps :: StepAlgebra b -> (Nat -> b) -- the catamorphisms map from Nat to b
foldSteps (nil, next) Zero       = nil
foldSteps (nil, next) (Succ nat) = next $ foldSteps (nil, next) nat

एक मूर्खतापूर्ण उदाहरण के रूप में, एन्कोडेड स्ट्रिंग्स पर बीजगणित पर विचार करें ("go!", \s -> "wait.. " ++ s), जिसके लिए Nothing को मैप किया गया है "go!" और अन्यथा "wait.. " पूर्वनिर्मित है. जैसा (Succ . Succ . Succ . Succ $ Zero) में संख्या चार को दर्शाता है Nat, निम्नलिखित प्रतीक्षा करने का मूल्यांकन करेगा.. रुको.. रुको.. रुको.. जाओ! : foldSteps ("go!", \s -> "wait.. " ++ s) (Succ . Succ . Succ . Succ $ Zero). हम आसानी से कोड को अधिक उपयोगी ऑपरेशन में बदल सकते हैं, जैसे कि संख्याओं पर बीजगणितीय ऑपरेशन का बार-बार संचालन, केवल एफ-बीजगणित को बदलकर। (nil, next), जिसे पारित कर दिया गया है foldSteps

सूची तह

एक निश्चित प्रकार के लिए a, फ़ंक्टर मैपिंग प्रकारों पर विचार करें b उन दो प्रकारों के उत्पाद प्रकार के लिए। इसके अलावा हम एक शब्द भी जोड़ते हैं Nil इस परिणामी प्रकार के लिए. एक एफ-बीजगणित अब मानचित्र करेगा Nil किसी विशेष शब्द के लिए nil का b या किसी युग्म (निर्मित प्रकार का कोई अन्य पद) को एक पद में मिला दें b. जोड़ी के इस विलय को एक प्रकार के फ़ंक्शन के रूप में एन्कोड किया जा सकता है a -> b -> b.

type ContainerAlgebra a b = (b, a -> b -> b) -- f-algebra encoded as (nil, merge)

data List a = Nil | Cons a (List a) -- which turns out to be the initial algebra

foldrList :: ContainerAlgebra a b -> (List a -> b) -- catamorphisms map from (List a) to b
foldrList (nil, merge) Nil         = nil
foldrList (nil, merge) (Cons x xs) = merge x $ foldrList (nil, merge) xs

एक उदाहरण के रूप में, एन्कोड किए गए संख्या प्रकारों पर बीजगणित पर विचार करें (3, \x-> \y-> x*y), जिसके लिए संख्या से a से संख्या पर कार्य करता है b सादे गुणन द्वारा. फिर निम्नलिखित का मूल्यांकन 3.000.000 होगा: foldrList (3, \x-> \y-> x*y) (Cons 10 $ Cons 100 $ Cons 1000 Nil)

पेड़ की तह

एक निश्चित प्रकार के लिए a, फ़ंक्टर मैपिंग प्रकारों पर विचार करें b एक प्रकार के लिए जिसमें प्रत्येक पद की एक प्रति होती है a साथ ही सभी जोड़े b(प्रकार के दो उदाहरणों के उत्पाद प्रकार की शर्तें b). बीजगणित में एक फ़ंक्शन शामिल होता है b, जो या तो एक पर कार्य करता है a अवधि या दो b शर्तें। एक जोड़ी के इस विलय को दो प्रकार के कार्यों के रूप में एन्कोड किया जा सकता है a -> b सम्मान b -> b -> b.

type TreeAlgebra a b = (a -> b, b -> b -> b) -- the "two cases" function is encoded as (f, g)
 
data Tree a = Leaf a | Branch (Tree a) (Tree a) -- which turns out to be the initial algebra
 
foldTree :: TreeAlgebra a b -> (Tree a -> b) -- catamorphisms map from (Tree a) to b
foldTree (f, g) (Leaf x)            = f x
foldTree (f, g) (Branch left right) = g (foldTree (f, g) left) (foldTree (f, g) right)

treeDepth :: TreeAlgebra a Integer -- an f-algebra to numbers, which works for any input type
treeDepth = (const 1, \i j -> 1 + max i j)
 
treeSum :: (Num a) => TreeAlgebra a a -- an f-algebra, which works  for any number type 
treeSum = (id, (+))

सामान्य मामला

प्रारंभिक बीजगणित के गहन श्रेणी के सैद्धांतिक अध्ययनों से पता चलता है कि फ़ंक्टर को अपने प्रारंभिक बीजगणित में लागू करने से प्राप्त एफ-बीजगणित इसके लिए आइसोमोर्फिक है।

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

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

अब फिर से पहला उदाहरण, लेकिन अब फिक्स करने के लिए हो सकता है फ़ैक्टर को पास करके। हो सकता है फ़ैक्टर का बार-बार अनुप्रयोग प्रकारों की एक श्रृंखला उत्पन्न करता है, जो, हालांकि, निश्चित बिंदु प्रमेय से समरूपता द्वारा एकजुट किया जा सकता है। हम शब्द का परिचय देते हैं zero, जो शायद से उत्पन्न होता है Nothing और बार-बार आवेदन के साथ एक उत्तराधिकारी फ़ंक्शन की पहचान करें Just. इस प्रकार प्राकृतिक संख्याएँ उत्पन्न होती हैं।

type Nat = Fix Maybe
zero :: Nat
zero = Iso Nothing -- every 'Maybe a' has a term Nothing, and Iso maps it into a
successor :: Nat -> Nat
successor = Iso . Just -- Just maps a to 'Maybe a' and Iso maps back to a new term

pleaseWait :: Algebra Maybe String -- again the silly f-algebra example from above
pleaseWait (Just string) = "wait.. " ++ string
pleaseWait Nothing = "go!"

फिर, निम्नलिखित प्रतीक्षा करने का मूल्यांकन करेगा.. रुको.. रुको.. रुको.. जाओ! : cata pleaseWait (successor.successor.successor.successor $ zero) और अब फिर से पेड़ का उदाहरण. इसके लिए हमें ट्री कंटेनर डेटा प्रकार प्रदान करना होगा ताकि हम इसे सेट कर सकें fmap (हमें इसके लिए ऐसा करने की ज़रूरत नहीं थी Maybe फ़ंक्टर, क्योंकि यह मानक प्रस्तावना का हिस्सा है)।

data Tcon a b = TconL a | TconR b b
instance Functor (Tcon a) where
    fmap f (TconL x)   = TconL x
    fmap f (TconR y z) = TconR (f y) (f z)

type Tree a = Fix (Tcon a) -- the initial algebra
end :: a -> Tree a
end = Iso . TconL
meet :: Tree a -> Tree a -> Tree a
meet l r = Iso $ TconR l r

treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra example
treeDepth (TconL x)   = 1
treeDepth (TconR y z) = 1 + max y z

निम्नलिखित 4 का मूल्यांकन करेगा: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))

यह भी देखें

• रूपवाद
• एफ-बीजगणित की आकृतियाँ|एफ-बीजगणित
  • कोलजेब्रा से अंतिम कोलजेब्रा तक: एनामोर्फिज्म
  • एक एनामॉर्फिज्म जिसके बाद कैटामॉर्फिज्म आता है: हाइलोमोर्फिज्म (कंप्यूटर विज्ञान)
  • कैटामोर्फिज्म के विचार का विस्तार: परारूपवाद
  • एनामोर्फिज्म के विचार का विस्तार: अपोमोर्फिज्म

संदर्भ

अग्रिम पठन

• Ki Yung Ahn; Sheard, Tim (2011). "A hierarchy of mendler style recursion combinators: taming inductive datatypes with negative occurrences". Proceedings of the 16th ACM SIGPLAN international conference on Functional programming. ICFP '11.

बाहरी संबंध

• Catamorphisms at HaskellWiki
• Catamorphisms by Edward Kmett
• Catamorphisms in F# (Part 1, 2, 3, 4, 5, 6, 7) by Brian McNamara
• Catamorphisms in Haskell