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

Not to be confused with एनामोर्फिज्म.

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

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

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

परिभाषा

इस प्रकार अपने आप में कुछ श्रेणी के कुछ एंडोफंक्टर एफ के लिए प्रारंभिक $F$-बीजगणित $(A,in)$ पर विचार करें। यहां $F$ से $A$ तक मोर्फिस्म है। चूंकि यह $in$ प्रारंभिक है, हम जानते हैं कि जब भी $(X,f)$ और $FA$-बीजगणित है, अर्थात $FX$ से $f$ तक मोर्फिस्म $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 नहीं को b के निश्चित पद nil पर माप करता है और जहां कॉपी किए गए शब्दों पर कार्य को 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 भी जोड़ते हैं। एफ-बीजगणित अब शून्य को b के कुछ विशेष पद Nil में मैप करेगा या एक जोड़ी (निर्मित एक प्रकार का कोई अन्य शब्द) को 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 पर एक ऐसे प्रकार पर विचार करें जिसमें 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!"

फिर, निम्नलिखित प्रतीक्षा करने का मूल्यांकन "wait.. wait.. wait.. wait.. 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