Καταμορφισμός

Στη θεωρία των κατηγοριών, η έννοια του καταμορφισμού (από το ελληνικό: κατά- = προς τα κάτω + μορφισμός) υποδηλώνει τον μοναδικό ομομορφισμό για μια αρχική άλγεβρα. Η έννοια έχει εφαρμοστεί στον συναρτησιακό προγραμματισμό. 

Οι καταμορφισμοί παρέχουν γενικεύσεις των καταλόγων πτυχών σε τυχαίους τύπους αλγεβρικών δεδομένων, οι οποίοι μπορούν να περιγραφούν ως αρχικές άλγεβρες. Η διπλή έννοια είναι αυτή του αναμορφισμού που γενικεύει τις ξεδιπλώσεις. Ο υλομορφισμός είναι η σύνθεση ενός αναμορφισμού που ακολουθείται από έναν καταμορφισμό.

Ορισμός

Ας θεωρήσουμε μια αρχική -άλγεβρα  για κάποιο ενδοσυναρτητή  κάποιας κατηγορίας στον εαυτό της. Εδώ  είναι ένας μορφισμός από  σε .
Δεδομένου ότι είναι η αρχική, γνωρίζουμε ότι όποτε  είναι μια άλλη -άλγεβρα, δηλαδή ένας μορφισμός  από  σε , υπάρχει ένας μοναδικός ομομορφισμός  από  σε . Σύμφωνα με τον ορισμό της κατηγορίας της -άλγεβρας, αυτό το  αντιστοιχεί σε ένα μορφισμό από το  στο , που συμβολίζεται επίσης με , έτσι ώστε . Στο πλαίσιο της -άλγεβρας, ο μοναδικά καθορισμένος μορφισμός από το αρχικό αντικείμενο συμβολίζεται με  και, ως εκ τούτου, χαρακτηρίζεται από την ακόλουθη σχέση:

 Ορολογία και ιστορία   

Μια άλλη σημειογραφία που συναντάται στη βιβλιογραφία είναι . Οι ανοιχτές αγκύλες που χρησιμοποιούνται είναι γνωστές ως banana brackets, από όπου προέρχεται και η ονομασία bananas για τους καταμορφισμούς, όπως αναφέρεται στο έργο των Ερικ Μέιτζερ «και άλλοι». Μία από τις πρώτες δημοσιεύσεις που εισήγαγε την έννοια του καταμορφισμού στο πλαίσιο της προγραμματισμού ήταν το άρθρο “Συναρτησιακός προγραμματισμός με μπανάνες, φακούς, φακέλους και συρματοπλέγματα“, των Έρικ Μέιτζερ και άλλοι, το οποίο ήταν στο πλαίσιο του φορμαλισμού Σκουίγκολ.
Ο γενικός κατηγορηματικός ορισμός δόθηκε από τον Γκραντ Μάλκολμ.
..

 Παραδείγματα      
Ακολουθεί μια σειρά παραδειγμάτων και στη συνέχεια, μια πιο γενική προσέγγιση των καταμορφισμών στη γλώσσα προγραμματισμού Χάσκελ:

 Καταμορφισμός για την άλγεβρα Maybe  

Ας εξετάσουμε τον συναρτητή Maybe που ορίζεται στον παρακάτω κώδικα Χάσκελ:

data Maybe a = Nothing | Just a -- Maybe τύπου

κλάση συναρτητή f όπου -- κλάση για συναρτητές
    fmap :: (a -> b) -> (f a -> f b)  -- δράση του συναρτητή στους μορφισμούς

instance Functor Maybe where -- Μετατροπή του Maybe σε συναρτητή
    fmap g Nothing = Nothing
    fmap g (Just x) = Just (g x)

Το αρχικό αντικείμενο της Maybe-άλγεβρας είναι το σύνολο όλων των αντικειμένων του τύπου φυσικού αριθμού Nat μαζί με τον μορφισμό ini που ορίζεται παρακάτω:
data Nat = Zero | Succ Nat -- τύπος φυσικού αριθμού

ini :: Maybe Nat -> Nat -- αρχικό αντικείμενο της άλγεβρας Maybe (με ελαφρά κατάχρηση της σημειογραφίας) 
ini Nothing = Zero
ini (Just n) = Succ n
Η cata απεικόνιση μπορεί να οριστεί ως εξής:
cata :: (Maybe b -> b) -> (Nat -> b)
cata g Zero = g (fmap (cata g) Nothing) -- Σημείωση:  fmap (cata g) Nothing = g Nothing and Zero = ini(Nothing)
cata g (Succ n) = g (fmap (cata g) (Just n)) -- Σημείωση: fmap (cata g) (Just n) = Just (cata g n) and Succ n = ini(Just n)
Ως παράδειγμα, ας εξετάσουμε τον ακόλουθο μορφισμό:
g :: Maybe String -> String 
g Nothing = "go!"
g (Just str) = "wait..." ++ str
Τότε cata g ((Succ. Succ . Succ) Zero) θα αξιολογηθεί ως "περίμενε... περίμενε... περίμενε... πάμε!".

 Κατάλογος κατά πτυχή 

Για έναν σταθερό τύπο a ας θεωρήσουμε τον συναρτητή MaybeProd a που ορίζεται ως εξής:
data MaybeProd a b = Nothing | Just (a, b) -- (a,b) είναι ο τύπος γινομένου των a και b

class Functor f where -- κλάση για συναρτητές
    fmap :: (a -> b) -> (f a -> f b)  -- δράση του συναρτητή επί των μορφισμών

instance Functor (MaybeProd a) where -- μετατρέψτε το MaybeProd a σε συναρτητή, η συναρτητικότητα υπάρχει μόνο στη δεύτερη μεταβλητή τύπου
    fmap g Nothing = Nothing
    fmap g (Just (x,y)) = Just (x, g y)
Η αρχική άλγεβρα του MaybeProd a δίνεται από τον κατάλογο των στοιχείων τύπου a μαζί με τον μορφισμό ini που ορίζεται παρακάτω:
data List a = EmptyList | Cons a (List a)

ini :: MaybeProd a (List a) -> List a -- αρχική άλγεβρα του MaybeProd a
ini Nothing = EmptyList
ini (Just (n,l)) = Cons n l
Η απεικόνηση cata μπορεί να οριστεί ως εξής:
cata :: (MaybeProd a b -> b) -> (List a -> b)
cata g EmptyList = g (fmap (cata g) Nothing) -- Σημείωση: ini Nothing = EmptyList
cata g (Cons s l) = g (fmap (cata g) (Just (s,l))) -- Σημείωση: Cons s l = ini (Just (s,l))
Ας σημειώσουμε επίσης ότι cata g (Cons s l) = g (Just (s, cata g l)).
Ως παράδειγμα, ας εξετάσουμε τον ακόλουθο μορφισμό:
g :: MaybeProd Int Int -> Int
g Nothing = 3
g (Just (x,y)) = x*y
cata g (Cons 10 EmptyList)  αποτιμάται σε 30. Αυτό μπορεί να φανεί αν αναπτυχθεί το
cata g (Cons 10 EmptyList) = g (Just (10,cata g EmptyList)) = 10*(cata g EmptyList) = 10*(g Nothing) = 10*3.

Με τον ίδιο τρόπο μπορεί να αποδειχθεί ότι
cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList)))  θα αποτιμηθεί σε 10*(100*(1000*3)) = 3.000.000.

Η απεικόνιση cata σχετίζεται στενά με τη δεξιά πτυχή (βλ. πτυχή (συνάρτηση ανώτερης τάξης)) των καταλόγων foldrList.
Ο μορφισμός lift που ορίζεται από
lift :: (a -> b -> b) -> b -> (MaybeProd a b -> b)
lift g b0 Nothing = b0
lift g b0 (Just (x,y)) = g x y
συνδέει το  cata με τη σωστή πτυχήfoldrList του καταλόγου μέσω:
foldrList :: (a -> b -> b) -> b-> List a -> b
foldrList fun b0 = cata (lift fun b0) 
Ο ορισμός του  cata υποδηλώνει ότι το foldrList είναι η δεξιά πτυχή και όχι η αριστερή πτυχή. Επί παραδείγματι : foldrList (+) 1 (Cons 10 (Cons 100 (Cons 1000 EmptyList))) θα αποτιμηθεί σε 1111 και foldrList (*) 3 (Cons 10 (Cons 100 (Cons 1000 EmptyList)) σε 3.000.000.

 Δέντρο πτυχή 

Για έναν σταθερό τύπο a, ας εξεταστεί τον συναρτητή που αντιστοιχεί τους τύπους b σε έναν τύπο που περιέχει ένα αντίγραφο κάθε όρου του a καθώς και όλα τα ζεύγη του b (όροι του τύπου γινομένου δύο περιπτώσεων του τύπου b). Μια άλγεβρα αποτελείται από μια συνάρτηση προς το b, η οποία ενεργεί είτε σε έναν όρο a είτε σε δύο όρους b . Αυτή η συγχώνευση ενός ζεύγους μπορεί να κωδικοποιηθεί ως δύο συναρτήσεις του τύπου a -> b και b -> b -> b αντίστοιχα..

type TreeAlgebra a b = (a -> b, b -> b -> b) -- η συνάρτηση "δύο περιπτώσεων" κωδικοποιείται ως (f, g)

data Tree a = Leaf a | Branch (Tree a) (Tree a) -- Το οποίο αποδεικνύεται ότι είναι η αρχική άλγεβρα.

foldTree :: TreeAlgebra a b -> (Tree a -> b) -- απεικονίσεις καταμορφισμών από (Δέντρο a) προς 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 -- μια f-άλγεβρα σε αριθμούς, η οποία λειτουργεί για οποιονδήποτε τύπο εισόδου
treeDepth = (const 1, \i j -> 1 + max i j)

treeSum :: (Num a) => TreeAlgebra a a -- μια f-άλγεβρα, η οποία λειτουργεί  για οποιονδήποτε τύπο αριθμού
treeSum = (id, (+))

 Γενική περίπτωση   

Βαθύτερες θεωρητικές μελέτες κατηγοριών αρχικών αλγεβρών αποκαλύπτουν ότι η F-άλγεβρα που προκύπτει από την εφαρμογή του συναρτητή στην ίδια την αρχική αλγεβρά του είναι ισομορφική με αυτήν.

Τα ισχυρά συστήματα τύπων μας επιτρέπουν να προσδιορίσουμε αφηρημένα την αρχική άλγεβρα ενός συναρτητή f ως το σταθερό του σημείο a = f a. Οι αναδρομικά ορισμένοι καταμορφισμοί μπορούν πλέον να κωδικοποιηθούν σε μία μόνο γραμμή, όπου η ανάλυση περιπτώσεων (όπως στα διάφορα παραδείγματα παραπάνω) ενσωματώνεται στο fmap. Δεδομένου ότι ο τομέας του τελευταίου είναι αντικείμενα στην εικόνα του f,  η αξιολόγηση των καταμορφισμών πηδάει μπρος-πίσω μεταξύ a και f a.

type Algebra f a = f a -> a -- οι γενικές f-άλγεβρες

newtype Fix f = Iso { invIso :: f (Fix f) } -- μας δίνει την αρχική άλγεβρα για τον συναρτητή f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- καταμορφισμός από Fix f σε a
cata alg = alg . fmap (cata alg) . invIso -- Ας σημειωθεί  ότι τα invIso και alg αντιστοιχούν σε αντίθετες κατευθύνσεις.

Τώρα πάλι το πρώτο παράδειγμα, αλλά τώρα μέσω της μετάδοσης του συναρτητή Maybe στο Fix.  Η επαναλαμβανόμενη εφαρμογή του συναρτητή Maybe δημιουργεί μια αλυσίδα τύπων, η οποία, ωστόσο, μπορεί να ενωθεί με τον ισομορφισμό από το θεώρημα του σταθερού σημείου. Εισάγουμε τον όρο  zero,  ο οποίος προκύπτει από το Maybe's του  Nothing και προσδιορίζουμε μια συνάρτηση διαδόχου με επαναλαμβανόμενη εφαρμογή του Just. Με αυτόν τον τρόπο προκύπτουν οι φυσικοί αριθμοί.

type Nat = Fix Maybe
zero :: Nat
zero = Iso Nothing -- κάθε 'Ίσως ένα' έχει έναν όρο Τίποτα, και το Iso το αντιστοιχίζει σε ένα
successor :: Nat -> Nat
successor = Iso . Just -- Απλώς αντιστοιχεί το a στο Maybe και το Iso αντιστοιχεί πίσω σε έναν νέο όρο.

pleaseWait :: Algebra Maybe String -- ξανά το απλό παράδειγμα της f-άλγεβρας από παραπάνω
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) -- η αρχική άλγεβρα
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 -- και πάλι, το παράδειγμα της f-άλγεβρας treeDepth
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"))

 Εξωτερικοί σύνδεσμοι 
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
ΑΓΓΛΟΕΛΛΗΝΙΚΟ. ΛΕΞΙΚΟ. ΜΑΘΗΜΑΤΙΚΩΝ. ΟΡΩΝ Αριάδνη Καλογερόπουλου. Μίλτος Γκίκας — Δ. Καραπαννακης — Μ. Λάμπρου. 
 Θεωρία Ομάδων-Πανεπιστήμιο Κρήτης
 Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
 Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
 Θεωρία Αριθμών και Εφαρμογές
 Υπολογιστική Θεωρία Αριθμών
 Καμπυλότητες και γεωμετρία του Riemann σε διαφορίσιμες πολλαπλότητες Εθνικό Αρχείο Διδακτορικών Διατριβών
 Μέθοδοι μηχανικής μάθησης βασισμένες σε έλεγχο μονοτροπικότητας Εθνικό Αρχείο Διδακτορικών Διατριβών
  Παράμετροι και Στατιστικά. Διωνυμική και Κανονική Κατανομή
 Wolfram Mathematica Online Integrator
  A Table of Integrals of the Error Functions

 Δείτε επίσης 

 Απαγορευτική αρχή του Πάουλι
 Μορφοκλασματική διάσταση
 Ομοπαραλληλική γεωμετρία
 Αλγεβρική θεωρία αριθμών
 Άρθουρ Στάνλεϋ Έντινγκτον
 Μοναδιαία βηματική συνάρτηση
 Σουμπραμανιάν Τσαντρασεκάρ
 Ευκλείδειος χώρος
 Αρχιμήδεια ιδιότητα
 Βαθμός (γραμμική άλγεβρα)
 Εφαρμοσμένα μαθηματικά
 Υπολογιστική ρευστοδυναμική
 Αβελιανή ομάδα
 Σύνθεση συνάρτησης
 Καρτεσιανό σύστημα συντεταγμένων
 Θεμελιώδες θεώρημα αριθμητικής
 Αλγεβρική γεωμετρία
 Ένα προς ένα
 Συνήθης διαφορική εξίσωση
 Γραμμική απεικόνιση
 Αβελιανή ομάδα

 Βιβλιογραφία











Παραπομπές



.
 .
.
.

 Murray Bremner and  Sara Madariaga. (2014) Permutation of elements in double semigroups









 Πηγές 






 Wendelin Degen, Lothar Profke: Grundlagen der affinen und euklidischen Geometrie. Teubner, Stuttgart 1976, ISBN 3-519-02751-8.
 Hans Freudenthal: Mathematik als pädagogische Aufgabe. Band 1. Klett, Stuttgart 1973, ISBN 3-12-983220-3.
 Thomas W. Hungerford: Algebra (= Graduate Texts in Mathematics. Bd. 73). 5th printing. Springer, New York NY u. a. 1989, ISBN 0-387-90518-9.

Κατηγορία:Θεωρία κατηγοριών
Κατηγορία:Θεωρία ομάδων
Κατηγορία:Αλγεβρική θεωρία αριθμών
Κατηγορία:Θεωρία δακτυλίων 
Κατηγορία:Αφηρημένη άλγεβρα