Transformări naturale

În secțiunea anterioară am discutat despre functori dar mai important decăt funtori în teoria categoriilor sunt transformările naturale. Informal o transformare naturală este mapare între functori, print-o transformare naturală un functor este transformat în altul.

Definiție: Transformare naturală

Dându-se două categorii $\mathcal{C}$, $\mathcal{D}$ și doi functori $F$, $G : C \rightarrow D$, o transformare naturală $alpha : F \implies G$ este o colecție de morfisme care pentru $\forall X \in Ob(C)$ $\exists \alpha_{X} = FX \rightarrow GX \in Hom(\mathcal{D})$, numită componenta lui $\alpha$ în $X$, astfel încât pentru oricare morfism $f : X \rightarrow Y \in Hom(\mathcal{C})$ următoarea diagramă comută:

Când ne referim că acestă diagramă comută ne referim la faptul că perechile de morfisme se compun pe diagonală în același morfism, astfel trebuie să fie satisfacută următoarea relație:

$$\alpha_Y \circ Ff = Gf \circ \alpha_X$$

Posibila formalizare in Lean 4

class NaturalTransformation (F G : Functor (C: Category ObjC) D) where
    app : (x : ObjC) -> D.Hom (F.mapObj x) (G.mapObj x)
    naturality : ∀ {x y : ObjC} {f : C.Hom x y}, D.comp (app y) (F.mapHom f) = D.comp (G.mapHom f) (app x)

Compunere

Și în cazul transformărilor naturale acestea se pot compune ca morfismele și functorii doar că exista două tipuri de compuneri, verticale și orizontale, din moment ce putem compune transformările naturale în serie, respectiv paralel cu compunerea functorilor.

Având functorii $F$, $G$, $H : \mathcal{C} \rightarrow \mathcal{D}$ și transformările naturale $\alpha : F \Rightarrow G$, $\beta : G \Rightarrow H$ atunci va exista mereu o transformare naturală $\beta \circ \alpha : F \Rightarrow H$ care are componentele $\forall X \in Ob(\mathcal{C})$ $(\beta \circ \alpha)_X = \beta_X \circ \alpha_X \in Hom(\mathcal{D})$. Acesta este compunerea verticală a transormărilor naturale, sau compunere în serie.

Compunerea verticală, uneori numită produs Godement, este compunerea transformărilor naturale paralele. Fie categoriile $\mathcal{C}, \mathcal{D}, \mathcal{E}$ și functorii $F_1, G_1 : \mathcal{C} \rightarrow \mathcal{D}$ și $F_2, G_2 : \mathcal{D} \rightarrow \mathcal{E}$. Dacă există transformările naturale $\alpha : F_1 \Rightarrow G_1$ și $\beta : F_2 \Rightarrow G_2$ atunci compunerea verticală este $\beta \ast \alpha$ care satisface următoarea diagramă comutativă:

Ca formulă componentele trebuie să satisfacă condiția ca indiferent ce tranformare naturală aplicăm prima dată nu trebuie să conteze, trebuie să obșinem aceiași componentă a transnformării naturale compuse, $(\beta \ast \alpha)_X = \beta_{G_1X} \circ F_2 \alpha_X = G_2 \alpha_X \circ \beta_{F_1X}$.

Putem simplifica această formulă folosind whiskering, cănd avem de aplicat o transformare naturală inainte sau după compunerea unui functor este mai simplu de specifica acest lucru prin a scrie $F\mu$ respectiv $\mu F$. Folosind whiskering condiția devine $\beta \ast \alpha = \beta G_1 \circ F_2 \alpha = G_2 \alpha \circ \beta F_1$. În această formă este mult mai ușur de gestionat, altfel putem vedea toate diagramele comutative într-o formă grafică ca mai jos:

Motivul de ce le spunem compuneri verticale, respectiv orizontale, o să fie mai evident cănd vom vorbi de 2-categorii dar până atunci putem avea o intuiție când desenăm diagramele cu ambele compuneri:

Legătura cu programarea

În programare se folosesc des transformările naturale deși nu sunt știute sub acest nume. Cea mai uzuală transformare naturală folosită în programare este parametrizarea tipurilor generice care impune o transformare naturală de la functor identitate către aplicarea unui tip generic care implementează acesta functie. De exemplu, putem vedea cum se aplică acest lucru la clasa generică pentru liste în diagrama următoare:

Morfismele verticale care sunt componentele transformării naturale reprezintă aplicarea tipului generic peste tipurile inițiale iar funcția map/fmap/select din programare funcțională este cea care adaugă existența morfismelor orizontale astfel încât diagrama să comute.

Resurse

• ncatlab