Functori

Programatorii sunt obișnuiți cu conceptul de functor și pot recunoaște tipuri generice, cum sunt listele, ca functori în limbajele orientate pe obiecte, deoarece de obicei au o metodă map/fmap/select care pot transforma o listă de tip List<int> într-o listă List<string> printr-o funcție $f : int \rightarrow string$.

Adevărul este că conceptul de functor din matematică și cel din programare reprezintă același concept din perspective diferite. Corespondența nu este întotdeauna intuitivă și evidentă, iar în continuare vom arăta de ce.

Definiție: Functor

Un functor $F$ de la o categorie $\mathcal{C}$ la alta $\mathcal{D}$, notat $F : \mathcal{C} \rightarrow \mathcal{D}$, este o mapare care trimite $\forall X \in Ob(\mathcal{C})$ într-un obiect $F(X) \in Ob(\mathcal{D})$ și care trimite $\forall f \in Hom(\mathcal{C})$ într-un morfism $F(f) \in Hom(\mathcal{D})$, astfel încât:

• $F$ conservă compoziția: $F(h \circ g) = F(h) \circ F(g)$
• $F$ conservă identitatea: $F(id_{X}) = id_{F(X)}$

Practic, un functor este un homomorfism (mapare care conservă structura) între două categorii.

Posibila formalizare in Lean 4

class Functor (C : Category ObjC) (D: Category ObjD) where
    mapObj : ObjC -> ObjD
    mapHom : ∀ {x y : ObjC}, C.Hom x y -> D.Hom (mapObj x) (mapObj y)
    conserveComp : ∀ {x y z : ObjC} (g : C.Hom y z) (f : C.Hom x y), D.comp (mapHom g) (mapHom f) = mapHom (C.comp g f)
    conserveId : ∀ {x : ObjC}, mapHom (C.id x) = D.id (mapObj x)

Legătura cu programarea

Revenind la corespondența între programare și matematică, putem evidenția legătura considerând următorul exemplu. Să presupunem că, în cadrul unui program, avem trei tipuri de date: int, bool și string, cu următoarele funcții între ele: $toString : int \rightarrow string$ și $isOdd : int \rightarrow bool$. Să presupunem că tipurile noastre de bază reprezintă o categorie, cu tipurile fiind obiecte, iar funcțiile morfisme. Dacă am introduce un functor numit $List$ ca un tip generic care are o funcție $map : List\ a \rightarrow (a \rightarrow b) \rightarrow List\ b$, atunci tuplul $(List, map)$ reprezintă functorul conform definiției date, ca cele două mapări pe obiecte, respectiv morfisme.

notă

Acesta este doar un exemplu care să ilustreze conceptual ideea de functor pentru un programator. În realitate, formalizarea sistemelor de tipuri sub forma de categorii este mult mai complexă.

Ce putem observa aici este că functorul nu conservă structura internă a unui tip de date - aceasta este irelevantă într-un context funcțional - ci conservă structura relațiilor între tipurile de date. De asemenea, pentru alte tipuri generice cu diferite proprietăți, trebuie incluse mai multe obiecte și morfisme în categoria destinație pentru functor. Categoria destinație poate include alte obiecte și morfisme la care nu se mapează din categoria sursă.

Compunere

La fel ca morfismele și functorii pot fi compuși, dacă avem functorii $F : \mathcal{C} \rightarrow \mathcal{D}$ și $G : \mathcal{D} \rightarrow \mathcal{E}$ atunci va exista un functor $G \circ F : \mathcal{C} \rightarrow \mathcal{E}$ care aplicat pe $X \in Ob(\mathcal{C})$ și $f \in Hom(\mathcal{C})$ duc în $G(F(X)) \in Ob(\mathcal{E})$ respectiv $G(F(f)) \in Hom(\mathcal{E})$.

Functorul identitate

Un caz special de (endo)functor este functorul identitate $Id_\mathcal{C} : \mathcal{C} \rightarrow \mathcal{C}$ (endofunctorii sunt functori cu sursa și destinația aceiași categorie) care satisface proprietățile:

$$Id_{\mathcal{C}}(X) = X,~\forall X \in Ob(\mathcal{C})$$ $$Id_{\mathcal{C}}(f) = f,~\forall f \in Hom(\mathcal{C})$$

Astfel acest functor pentru conpunerea oricare functori $F : \mathcal{X} \rightarrow \mathcal{C}$, $G : \mathcal{C} \rightarrow \mathcal{X}$ satisface relațiile:

$$Id_{\mathcal{C}} \circ F = F$$ $$G \circ Id_{\mathcal{C}} = G$$

Functori covarianți și contravarianți

În general, dacă avem un funtor de tipul $F : \mathcal{C} \rightarrow \mathcal{D}$ îl vom numi covariant iar atunci când functorul are ca domeniul de definiție categoria opusă $G : \mathcal{C}^{op} \rightarrow \mathcal{D}$ îl numim contravariant. Aceste două noțiuni se văd cel mai clar prin functorul $hom$ definit pentru o categorie local mică $\mathcal{C}$. Acest functor este definit $hom : \mathcal{C}^{op} \times \mathcal{C} \rightarrow \mathbf{Set}$ duce o pereche de obiecte $A, B \in Ob(\mathcal{C})$ în mulțimea $Hom_{\mathcal{C}}(A, B) \in Hom(\mathcal{C})$ a tuturor morfismelor de la $a$ la $b$.

Dacă fixam un $C \in Ob(\mathcal{C})$ atunci obținem doi functori, $Hom(X, -) : \mathcal{C} \rightarrow \mathbf{Set}$ care este covariant și $Hom(-, C) : \mathcal{C}^{op} \rightarrow \mathbf{Set}$ contravariant. Functorul $Hom(C, -)$ este covariant pentru că dacă avem un morfism $f : X \rightarrow Y \in Hom(\mathcal{C})$ atunci avem $Hom(C, f) : Hom(C, X) \rightarrow Hom(C, Y)$ unde $\forall q \in Hom(C, X), f \circ q \in Hom(C, Y)$. Functorul $Hom(-, C)$ este contravariant pentru că un morfism $f : X \rightarrow Y \in Hom(\mathcal{C})$ atunci există $Hom(f, C) : Hom(Y, C) \rightarrow Hom(X, Y)$ unde $\forall q \in Hom(Y, C), q \circ f \in Hom(X, C)$.

Resurse

• ncatlab