Monade și comonade

O noțiune care este de neevitat în programarea funcțională este aceea de monadă. În principiu, o monadă este un functor care poate condensa mai multe aplicări ale sale într-o singură aplicare într-un mod monoidal. Cu alte cuvinte, o monadă este un monoid în categoria endofunctorilor din care aparține (ignorăm momentan posibilitatea de a nu avea categoria de endofunctori dacă există probleme de dimensionare). Bineînțeles, noțiunea duală este cea de comonadă, un comonoid în categoria endofunctorilor din care aparține. O comonadă face exact inversul fată de o monadă, desfășoară aplicarea sa în mai multe aplicări.

Deși comonadele nu sunt atăt de discutate cum sunt monadele, aceste sunt extrem de utile și interesante. Vom vedea în cele ce urmează cum anume monadele și comonadele ne ajută.

Monade

Fie $\mathcal{C}$ o categorie. O monadă este un triplet $(T, \eta, \mu)$ unde $T : \mathcal{C} \rightarrow \mathcal{C}$ este un endofunctor, $\eta : Id_{\mathcal{C}} \Rightarrow T$ și $\mu : T^2 = T \circ T \Rightarrow T$ sunt două transformări naturale, numite unitatea, respectiv multiplicarea monadei, cu proprietatea că următoarele diagrame comută:

Diagramele pot fi condensate în formulele:

• $\mu \circ \eta T = \mu \circ T \eta = id_T$
• $\mu \circ T \mu = \mu \circ \mu T$

Practic, unitatea monadei duce obiecte în aplicări ale monadei iar multiplicarea condensează aplicări multiple astfel încât indiferent cum aplicăm transformările naturale obținem aceiași singură aplicare a monadei. Aceste două transformări naturale sunt cunoscute ca funcțiile return :: a -> T a și join :: T (T a) -> T a din Haskell dar de obicei monadele sunt definite ca operațiile return și bind :: T a -> (a -> T b) -> T b. Operația de bind este practic join aplicat după fmap. Alt nume pentru bind este flatMap pentru că asta și face, aplică o mapare și aplatizează (flattens) tipul de date, join este doar o operație de aplatizare și se mai numeste flatten. Utilitate monadelor constă în faptul că unitatea ne permite să înglobăm date într-un functor iar multiplicarea agregă datele din mai multe aplicări sau contexte într-un singur context ca să lucram mai ușor cu instanța functorului.

Comonade

Fie $\mathcal{C}$ o categorie. O comonadă este un triplet $(G, \epsilon, \delta)$ unde $G : \mathcal{C} \rightarrow \mathcal{C}$ este un endofunctor, $\epsilon : G \Rightarrow Id_{\mathcal{C}}$ și $G \Rightarrow : G \circ G = G^2$ sunt două transformări naturale, numite counitatea, respectiv comultiplicarea comonadei, cu proprietatea că următoarele diagrame comută:

Diagramele pot fi condensate în formulele:

• $\epsilon G \circ \delta = G \epsilon \circ \delta = id_G$
• $G \delta \circ \delta = \delta G \circ \delta$

Counitatea și comultiplicarea acționează în sensul invers ca la unitatea și multiplicarea monadei, acestea mai sunt cunoscute în limbajele de programare ca extract :: G a -> a și duplicate :: G a -> G (G a) având și dualul lui bind ca cobind :: (a -> G b) -> G a -> G b. Ambele asigură că indiferent cum le aplicăm obținem aceleași tipuri de date imbricate. Comonadele sunt foarte utile pentru că counitatea poate extrage obiectul din interiorul aplicării functorului, lucru care lipsește la monade, adică la nevoie putem accesa direct datele dintr-o comonadă dacă dorim. Comultiplicarea este de asemena foarte utilă pentru că ne permite să duplicăm date și să le refolosim în contexte noi.

Legătura cu adjuncții

Un lucru important legat de (co)monade este faptul că acestea apar mereu dintr-o pereche de functori adjuncți. Dacă avem doi functori adjuncți $L \vdash R$, $L : \mathcal{C} \rightarrow \mathcal{D}$ și $R : \mathcal{D} \rightarrow \mathcal{C}$ atunci există o monadă $T : \mathcal{D} \rightarrow \mathcal{D}$ și o comondă $G : \mathcal{C} \rightarrow \mathcal{C}$.

• monada $T$ este compusul functorilor $R \circ L$, unitatea monadei este unitatea adjuncției $\eta$ iar multiplicarea este data de counitatea adjuncției $\mu : T \circ T = R \circ L \circ R \circ L \xRightarrow{R \epsilon L} R \circ L = T$
• comonada $G$ este compusul functorilor $L \circ R$, counitatea comonadei este counitatea adjuncției $\eta$ iar comultiplicarea este data de unitatea adjuncției $\delta : L \circ R = G \xRightarrow{L \eta R} L \circ R \circ L \circ R = G \circ G$

Canonic exista două categorii prin care putem defini adjuncții care produc monade, anume categoria Kleisli a unei monade și categoria Eilenberg-Moore sau categoria algebrelor pentru o monadă.

Categoria Kleisli

Fie $\mathcal{C}$ o categorie și cu o monadă $(T, \eta, \mu)$. Categoria Kleisli a acestei monade este $\mathcal{C}_T$ cu:

• $Ob(\mathcal{C}) = Ob(\mathcal{C}_T)$
• $Hom_\mathcal{C}(x, Ty) = Hom_{\mathcal{C}_T}(x_T, y_T)$

Cu alte cuvinte, obiectele sunt aceleași dar $\forall f : x \rightarrow Ty \in Hom(\mathcal{C})$ devin $f^* : x_T \rightarrow y_T \in Hom(\mathcal{C}_T)$. Astfel avem:

• $id_{x_T} = \eta_X^*$
• $f^* : x_T \rightarrow y_T$, $g^* : y_T \rightarrow z_T$, $g^* \circ_T f^* = (\mu_z \circ Tg \circ f)^*$

Putem crea o pereche de functori adjuncți $L \vdash R$ în felul următor:

• L mapează fiecare obiect din $\mathcal{C}$ la același obiect din $\mathcal{C}_T$, $Lx = x_T$ și orice morfism $f : x \rightarrow y$ la $Lf = (\eta_y \circ f)^*$
• R mapează fiecare obiect din $x_T \in Ob(\mathcal{C}_T)$ la $R(x_T) = Tx$ și orice morfism $f^* : x_T \rightarrow y_T \in Hom(\mathcal{C}_T)$ la $Rf^* = \mu_y \circ Tf$

Se poate vedea ușor că acești doi functori sunt adjuncți și produc monada:

• $\forall x \in Ob(\mathcal{C})$, $(R \circ L)(x) = Rx_T = Tx$
• $\forall f : x \rightarrow y \in Hom(\mathcal{C})$, $(R \circ L)(f) = R((\eta_y \circ f)^*) = \mu_y \circ T(\eta_y \circ f) = Tf$
• unitatea adjuncției există deja și este unitatea monadei

Invers, obținem o comonadă $G : \mathcal{C}_T \rightarrow \mathcal{C}_T$:

• $\forall x_T \in Ob(\mathcal{C}_T)$, $Gx_T = (L \circ R)(x_T) = L(Tx) = (Tx)_T$
• $\forall f^* : x_T \rightarrow y_T \in Hom(\mathcal{C}_T)$, $Gf^* = (L \circ R)(f^*) = L(\mu_y \circ Tf) = (\eta_y \circ \mu_y \circ Tf)^* = (Tf)^*$
• counitatea adjuncției este dată de multiplicarea și unitatea monadei pentru că $\forall f^* : x_T \rightarrow y_T \in Hom(\mathcal{C}_T)$, $(\eta_y)^* \circ_T f^* = (\mu_y \circ T\eta_y \circ f)^* = (\mu_y \circ Tf \circ \eta_x)^* = (Tf)^* \circ_T (\eta_x)^*$
• comultiplicarea acestei comonade este dată de $delta_x = (T\eta_x)^*$ pentru că o diagrama în $\mathcal{C}$

Devine următoarea diagramă în $\mathcal{C}_T$:

Algebre pentru o monadă

Înainte de a introduce categoria Eilenberg-Moore trebuie definite algebrele pentru monade, acestea diferă față de algebrele pentru un endofunctori prin faptul că pe lângă definiția generală a acestora au o structură suplimentară compatibilă cu unitatea și multiplicarea monadei.

Fie $(T, \eta, \mu)$ o monadă, o algebră pentru acestă monadă este o algebră $(a, \alpha)$ cu structura suplimentară că următoarele diagrame comută:

Cu alte cuvinte, $\alpha \circ \eta_a = id_a$ și $\alpha \circ \mu_a = \alpha \circ T\alpha$.

Categoria Eilenberg-Moore

Fie $\mathcal{C}$ o categorie și cu o monadă $(T, \eta, \mu)$. Categoria Eilenberg-Moore a acestei monade este $\mathcal{C}^T$ cu:

• $Ob(\mathcal{C}^T) = \{(x, \nu^x)~|~x \in Ob(\mathcal{C}), \alpha : Tx \rightarrow x \in Hom(\mathcal{C})\}$, adică mulțimea de obiecte este mulțimea algebrelor pentru $T$
• $Hom(\mathcal{C}^T) = \{f^T~|~f^T = f : x \rightarrow y \in Hom(\mathcal{C},~\nu^y \circ Tf = f \circ \nu^x), \alpha : Tx \rightarrow x \in Hom(\mathcal{C})\}$ este mulțimea homomorfismelor între algebrele pentru $T$

Putem crea o pereche de functori adjuncți $L \vdash R$ în felul următor:

• L mapează $\forall x \in Ob(\mathcal{C})$ la $Lx = (Tx, \mu_x)$ și $\forall f : x \rightarrow y \in Hom(\mathcal{C})$ la $Lf = (Tf)^T : (Tx, \mu_x) \rightarrow (Ty, \mu_y)$
• R mapează $\forall (x, \nu^x) \in Ob(\mathcal{C}^T)$ la $R(x, \nu^x) = x$ și $\forall f^T : (x, \nu^x) \rightarrow (y, \nu^y)$ la $R(f^T) = f : x \rightarrow y$, cu alte cuvinte $R$ este un functor de uitare (forgetful functor), uită de anumite elemente din categorie, și pentru că este adjunctul la dreapta numim adjunctul la stânga al unui functor de uitate functor liber (free functor)

Se poate vedea ușor că acești doi functori sunt adjuncți și produc monada:

• $\forall x \in Ob(\mathcal{C})$, $(R \circ L)(x) = R(Tx, \mu_x) = Tx$
• $\forall f : x \rightarrow y \in Hom(\mathcal{C})$, $(R \circ L)(f) = R((Tf)^T) = Tf$
• unitatea adjuncției există deja și este unitatea monadei

Invers, obținem o comonadă $G : \mathcal{C}^T \rightarrow \mathcal{C}^T$:

• $\forall (x, \nu^x) \in Ob(\mathcal{C}^T)$, $G(x, \nu^x) = (L \circ R)(x, \nu^x) = L(x) = (Tx, \mu_x)$
• $\forall f^T : (x, \nu^x) \rightarrow (y, \nu^y) \in Hom(\mathcal{C}^T)$, $Gf^T = (L \circ R)(f^T) = L(f) = (Tf)^T$
• counitatea adjuncției este dată de multiplicarea și unitatea monadei pentru că $\forall f^T : (x, \nu^x) \rightarrow (y, \nu^y) \in Hom(\mathcal{C}^T)$ ține condiția $\nu^x \circ \mu_x = \nu^x \circ T\nu^x$ pentru algebra monadei și atunci $\epsilon_{(x, \nu^x)} = \nu^x : (Tx, \mu_x) \rightarrow (x, \nu^x)$ este un homomorfism care face să comute:

Care ține pentru că indiferent de ce compunere de homomorfism aplicăm obținem următoarele diagrame comutative care sunt echivalente:

Putem verifica imediat compunerile:

$$\nu^y \circ Tf \circ T\nu^x = \nu^y \circ T\nu^y \circ TTf =$$ $$f \circ \nu^x \circ \mu_x = \nu^y \circ Tf \circ \mu_x$$

• comultiplicarea acestei comonade este dată de $delta_x = T\eta_x : (Tx, \mu_x) \rightarrow (TTx, \mu_{Tx})$ este un homomorfism care face să comute:

Care ține pentru că indiferent de ce compunere de homomorfism aplicăm obținem următoarele diagrame comutative care sunt echivalente:

Putem verifica imediat compunerile pentru că $\eta_y \circ f = Tf \circ eta_x$:

$$\mu_{Ty} \circ TTTf \circ TT\eta_{x} = \mu_{Ty} \circ TT\eta_{y} \circ TTf =$$ $$T\eta_{y} \circ Tf \circ \mu_x = TTf \circ T\eta_{x} \circ \mu_x$$