Cuvântul "algebră" poate avea mai multe semnificații în matematică dar în contextul teoriei categoriilor când spunem "algebră" ne vom referii în general la F-algebre sau algebre pentru endofunctori dacă nu se specifică altfel. În acest context, o algebră încapsulează noțiunea de structură algebraică și este o noțiune foarte utilă pentru a definii structuri de date, mai ales structuri recursive.

Definiție: Algebră pentru un endofunctor

Fie $F : \mathcal{C} \rightarrow \mathcal{C}$ un endofunctor. O algebră a lui $F$ este o pereche $(a, \alpha)$ unde $a \in Ob(\mathcal{C})$, numit și carrier, și $\alpha : Fa \rightarrow a \in Hom(\mathcal{C})$. Dacă din context morfismul $\alpha$ este cunoscut sau unic atunci carrier-ul este referit ca fiind algebra.

Un homomorfism între algebre $(a, \alpha)$ și $(b, \beta)$ este un morfism $f : a \rightarrow b$ pentru care $\beta \circ Ff = f \circ \alpha$, adică următoarea diagramă comută:

Din algebre și homomorfisme între acestea pentru endofunctorul $F$ putem forma o categorie iar dacă există obiectul inițial în acea categorie acesta este algebra inițială, adică avem câte un homomorfism unic de la acea algebră la oricare algebră a lui $F$. Vom nota carrier-ul pentru algebra inițială a lui $F$ cu $\mu F$. Algebra inițială este un concept foarte important pentru că putem defini tipuri de date recursiv.

De asemenea, ne vom referi la $F$ ca fiind signatura algebrei.

Lema lui Lambek

Dacă pentru un endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ există algebra inițială $(\mu F, \alpha)$ atunci $\mu F$ este izomorf cu $F\mu F$ prin $\alpha$.

Pentru că $(F\mu F, F\alpha)$ este tot o algebră și $(\mu F, \alpha)$ este inițial atunci există un morfism unic $i : \mu F \rightarrow F\mu F$ pentru care $i \circ \alpha = F\alpha \circ Fi$, dar cum $(\mu F, \alpha)$ este inițială și homomorfismul unic către ea însăși este dat de identitatea $id_{\mu F}$ rezultă că $\alpha \circ i = id_{\mu F}$ și atunci $i \circ \alpha = F\alpha \circ Fi = id_{F\mu F}$. Putem vedea cum se leagă toate aceste lucruri în diagrama următoare:

Prin algebra inițială putem defini tipuri de date inductive în semantică categorială pentru că algebra inițială este cel mai mic punct fix (least fixed point) a lui $F$.

Putem ilustra acest lucru prin următoarele exemple în $\mathbf{Set}$:

• pentru functorul $Fx = 1 + x$, unde $1$ este mulțimea singleton, algebra inițială este mulțimea numerelor naturale $(\mu F = \mathbb{N}, \alpha)$. Numerele naturale ca tip de date pot fi definite recursiv ca fiind $Nat = Zero~|~Succ~Nat$, din definiția acestei algebre unde trebuie să existe $\alpha : 1 + \mu F \rightarrow \mu F$ și faptul că avem o uniune disjunctă de mulțimi $\alpha$ poate fi împărțită în două funcții, un punct $1 \rightarrow \mu F$ și o funcție de succesiune $\mu F \rightarrow \mu F$ și de aici obținem cei doi constructori de tip. Unde intervine recursivitatea este în unicitatea funcției succesiune pentru că $\alpha$ este unic și inversabil iar inversa trebuie în mod necesar să fie incluziunea $\alpha^{-1} : \mu F \rightarrow 1 + \mu F$.

• pentru functorul $Fx = 1 + a \times x$ algebra inițială este mulțimea listelor de tip $a$, $List~a = Void~|~Cons(a, List~a)$.

• pentru functorul $Fx = 1 + a \times x \times x$ algebra inițială este mulțimea arborilor binari cu noduri cu valori de tip $a$, $BinTree~a= Void~|~Node(BinTree~a, BinTree~a)$.

Catamorfisme

Mofismul unic de la algebra inițială $(\mu F, \alpha)$ pentru un endofunctor $F$ la o altă algebră $(x, \phi)$ se numește catamorfism notat $cata \phi$.

Un catamorfism este conceptual o operație de tip fold, adică, transformăm valorile unui tip de date inductiv cum sunt listele într-o valoare de tip $x$. Pentru catamorphism avem următoarea diagramă comutativă:

Conform definiției algebrei $cata \phi \circ \alpha = \phi \circ F (cata \phi)$, dar cum $\mu F$ este algebra inițială $\alpha$ este invesabilă și atunci putem calcula recursiv $cata \phi = \phi \circ (F cata \phi) \circ \alpha^{-1}$.

Să luăm cazul $Fx = 1 + a \times x$ unde $\mu F = List~a$, dacă luam un tip $b$ cu $\phi : 1 + a \times b \rightarrow b$ atunci $cata \phi : List~a \rightarrow b$. Deci $cata$ mapează $((1 + a \times b) \rightarrow b) \rightarrow (List~a \rightarrow b)$, iar funcția $\phi$ poate fi spartă în $init \times op$, $init: 1 \rightarrow b \cong b$ și $op: a \times b \rightarrow b$.

Astfel, putem rescrie $cata$ ca un fold la dreapta $foldr : (b \times (a \times b \rightarrow b)) \rightarrow List~a \rightarrow b \cong b \rightarrow (a \times b \rightarrow b) \rightarrow List~a \rightarrow b$. Practic, dacă avem $lift : (b \times (a \times b \rightarrow b)) \rightarrow ((1 + a \times b) \rightarrow b)$ cu $\phi = lift(init \times op)$ atunci $foldr = cata \circ lift$. Este important de menționat că $cata$ corespunde cu fold-ul la dreapta, nu la stânga în acest caz.

Cu alte cuvinte, dacă avem o algebră, $cata$ transformă un morphism $Fb \rightarrow b$ într-un morphism $\mu F \rightarrow b$. Aici este un lucru foarte important de observat, cum $F$ este signatura algebrei aceasta servește ca un caz de bază pentru aplicarea catamorfismului, adică transformăm tratarea cazurilor de bază pentru a obține o valoare de tip $b$ într-o operație pe valorile algebrei inițiale (care este un tip inductiv) ca să obținem o valoare agregată de tip $b$.

Definiție: Coalgebră pentru un endofunctor

Fie $F : \mathcal{C} \rightarrow \mathcal{C}$ un endofunctor. O coalgebră a lui $F$ este o pereche $(a, \alpha)$ unde $a \in Ob(\mathcal{C})$, numit și carrier, și $\alpha : a \rightarrow Fa \in Hom(\mathcal{C})$. Dacă din context morfismul $\alpha$ este cunoscut sau unic atunci carrier-ul este referit ca fiind coalgebra.

Un homomorfism între coalgebre $(a, \alpha)$ și $(b, \beta)$ este un morfism $f : a \rightarrow b$ pentru care $\beta \circ f = Ff \circ \alpha$, adică următoarea diagramă comută:

Din coalgebre și homomorfisme între acestea pentru endofunctorul $F$ putem forma o categorie iar dacă există obiectul final în acea categorie acesta este algebra finală, adică avem câte un homomorfism unic de la oricare coalgebră a lui $F$ la această coalgebră. Vom nota carrier-ul pentru coalgebra finală a lui $F$ cu $\nu F$. Coalgebra inițială este un concept foarte important pentru că putem defini tipuri de date corecursiv.

De asemenea, ne vom referi la $F$ ca fiind signatura coalgebrei.

Corolarul lemei lui Lambek pentru coalgebre

Dacă pentru un endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ există coalgebra finală $(\nu F, \alpha)$ atunci $\nu F$ este izomorf cu $F\nu F$ prin $\alpha$.

Pentru că $(F\nu F, F\alpha)$ este tot o coalgebră și $(\nu F, \alpha)$ este finală atunci există un morfism unic $i : F\nu F \rightarrow \nu F$ pentru care $Fi \circ F\alpha = \alpha \circ i$, dar cum $(\nu F, \alpha)$ este finală și homomorfismul unic către ea însăși este dat de identitatea $id_{\nu F}$ rezultă că $i \circ \alpha = id_{\nu F}$ și atunci $\alpha \circ i = Fi \circ F\alpha = id_{F\nu F}$. Putem vedea cum se leagă toate aceste lucruri în diagrama următoare:

Prin coalgebra finală putem defini tipuri de date coinductive în semantică categorială pentru că coalgebra finală este cel mai mare punct fix (greatest fixed point) a lui $F$.

Anamorfisme

Mofismul unic către coalgebra finală $(\nu F, \alpha)$ pentru un endofunctor $F$ de la o altă coalgebră $(x, \phi)$ se numește anamorfism notat $ana \phi$.

Un anamorfism este conceptual o operație de tip unfold, adică, transformăm o valoare a unui tip de date $x$ în valorile unui tip de date coinductiv cum sunt stream-urile. Pentru anaamorphism avem următoarea diagramă comutativă:

Conform definiției coalgebrei $F(ana \phi) \circ \alpha = \phi \circ ana \phi$, dar cum $\nu F$ este coalgebra finală $\alpha$ este invesabilă și atunci putem calcula corecursiv $F(ana \phi) = \phi \circ ana \phi \circ \alpha^{-1}$.

Să luăm cazul $Fx = a \times x$ unde $\nu F = Stream~a$, dacă luam un tip $b$ cu $\phi : b \rightarrow a \times b$ atunci $ana \phi : b \rightarrow Stream~a$. Deci $ana$ mapează $(b \rightarrow a \times b) \rightarrow (b \rightarrow Stream~a)$, iar funcția $\phi$ poate fi spartă în $init \times op$, $init: 1 \rightarrow b \cong b$ și $op: a \times b \rightarrow b$.

Astfel, $ana$ este chiar unfold la dreapta $unfoldr : (b \rightarrow a \times b) \rightarrow b \rightarrow Stream~a$.

Cu alte cuvinte, dacă avem o coalgebră, $ana$ transformă un morphism $b \rightarrow Fb$ într-un morphism $b \rightarrow \mu F$. Aici este un lucru foarte important de observat, cum $F$ este signatura coalgebrei aceasta servește ca un generator pentru aplicarea anamorfismului, adică ne folosim de o valoare de tip $b$ ca să producem valorile coalgebrei finale (care este un tip coinductiv).