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

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

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

## Ορισμός

Ας θεωρήσουμε μια αρχική 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|\!). Οι ανοιχτές αγκύλες που χρησιμοποιούνται είναι γνωστές ως **banana brackets**, από όπου προέρχεται και η ονομασία **bananas** για τους καταμορφισμούς, όπως αναφέρεται στο έργο των Ερικ Μέιτζερ «και άλλοι». Μία από τις πρώτες δημοσιεύσεις που εισήγαγε την έννοια του **καταμορφισμού** στο πλαίσιο της προγραμματισμού ήταν το άρθρο “Συναρτησιακός προγραμματισμός με μπανάνες, φακούς, φακέλους και συρματοπλέγματα“, των Έρικ Μέιτζερ και άλλοι, το οποίο ήταν στο πλαίσιο του φορμαλισμού Σκουίγκολ.
Ο γενικός κατηγορηματικός ορισμός δόθηκε από τον Γκραντ Μάλκολμ.

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

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

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


```haskell
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` που ορίζεται παρακάτω:

```haskell
data Nat = Zero | Succ Nat -- τύπος φυσικού αριθμού

ini :: Maybe Nat -> Nat -- αρχικό αντικείμενο της άλγεβρας Maybe (με ελαφρά κατάχρηση της σημειογραφίας) 
ini Nothing = Zero
ini (Just n) = Succ n
```

Η `cata` απεικόνιση μπορεί να οριστεί ως εξής:

```haskell
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)
```

Ως παράδειγμα, ας εξετάσουμε τον ακόλουθο μορφισμό:

```haskell
g :: Maybe String -> String 
g Nothing = "go!"
g (Just str) = "wait..." ++ str
```

Τότε `cata g ((Succ. Succ . Succ) Zero)` θα αξιολογηθεί ως "περίμενε... περίμενε... περίμενε... πάμε!".

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

Για έναν σταθερό τύπο `a` ας θεωρήσουμε τον συναρτητή `MaybeProd a` που ορίζεται ως εξής:

```haskell
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` που ορίζεται παρακάτω:

```haskell
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` μπορεί να οριστεί ως εξής:

```haskell
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))`.
Ως παράδειγμα, ας εξετάσουμε τον ακόλουθο μορφισμό:

```haskell
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` που ορίζεται από

```haskell
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` του καταλόγου μέσω:

```haskell
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` αντίστοιχα..


```haskell
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)
```



```haskell
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`.


```haskell
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`. Με αυτόν τον τρόπο προκύπτουν οι φυσικοί αριθμοί.


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



```haskell
pleaseWait :: Algebra Maybe String -- ξανά το απλό παράδειγμα της f-άλγεβρας από παραπάνω
pleaseWait (Just string) = "wait.. " ++ string
pleaseWait Nothing = "go!"
```


Και πάλι, το παρακάτω θα αξιολογηθεί ως "περίμενε... περίμενε... περίμενε... περίμενε... πάμε!": `cata pleaseWait (successor.successor.successor.successor $ zero)`

Και τώρα πάλι το παράδειγμα με το δέντρο. Για αυτό πρέπει να παρέχουμε τον τύπο δεδομένων του δέντρου-δοχείου, ώστε να μπορέσουμε να ρυθμίσουμε το  `fmap` (δεν χρειάστηκε να το κάνουμε για τον συναρτητή  `Maybe` καθώς είναι μέρος του τυπικού προλόγου)


```haskell
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)
```



```haskell
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
```



```haskell
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.

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