Les Catégories, la théorie.
Il est sans doute encore trop tôt pour aborder cette cote raide, mais après tout, on peut se mettre à comprendre à tout moment... Et puis je l'avais fait déjà un peu en (1)
Ici on s'est tapé (rapidement) le très addictif cours de Bartosz Milewski (2), avec du texte en (3) et bien sur la référence absolue (4).
Il est en Mathématique, et ailleurs d'ailleurs, un principe qui consiste à réexprimer un problème avec d'autres mots, en espérant que celui ci devienne plus simple. La résolution de conjectures serait ainsi une science du choix de la meilleure transformation, le voyage devenant l'essentiel, l'arrivée résolvant tout toute seule. Une citation de Poincaré: les maths c'est donner le même nom à des choses différentes...
Cette science des correspondances, de la structure de ces correspondances, est la théorie de catégories, science des sciences des sciences. On avait abordé la chose, et on y reviendra, la chose étant vaste.
Une autre manière de présenter la chose est que les catégories sont les structures, et qu'il n'y a guère que les structures qui caractérisent les choses qu'on veut comparer ou égaler. De part et d'autre, on projette sur la structure et on associe les structures enfin comparables... Bref, ces squelettes sont fait de multiples relations et il n'y a que les relations qui comptent.
Tout cela fut inventé par un certain Saunders Mac Lane, un américain.
Disons aujourd'hui pour commencer aussi que Curry et Howard n'étaient pas seuls, il y avait Lambek, qui ajouta à la correspondance entre propositions et types, celle, mutuelle, avec les catégories cartésiennes fermées.
Cette identification des trois seules choses qui vaillent au monde s'appelle la "trinité computationnelle". Elle signifie que toute notion manifeste dans l'une des vues l'est aussi, sous forme transformée, dans les deux autres (5). Rien que ça. Wagnérien, c'est le moins qu'on puisse dire... Le mot catégorie est lourd de sens.
Joachim Lambek introduisit aussi les grammaires catégoriques pour le langage naturel.
Reste à s'enfoncer dans les catégories, donc.
Les catégories
En trois mots, on a dans une catégorie des objets ET des morphismes, les foncteurs relient les catégories, et les tranformations naturelles les foncteurs. Une 2 catégorie a en plus des morphismes sur les morphismes et ad infinitum. Après... On distingue les petites catégories (à zéro ou UN objet) et les grandes, les autres.
Definition
On commencera par définir ce qu'on appelle "catégorie", "tas" d'objets (il n'est évidemment pas question d'ensembles pour définir ce type de multiplicité), et de "flèches", avec quelques contraintes: tout objet a une flèche vers lui même; toute paire d'objets a zéro, une ou plusieurs flèches orientées; entre trois objets les flèches composent; et entre quatre objets, la composition est associative.
Juste un point au sujet de la composition: il s'agit d'un "il existe", la flèche qui compose (a-f->b-g->c implique il existe une flèche nommée gof telle que a-gof->c) étant l'une des flèches pré existantes entre a et c... Ce type de remarques n'a pas grand intérêt, mais illustre que ces propriétés sont statiques et non pas génératives: gof existe, un point c'est tout...
Un autre point concerne le fait que les morphismes entre deux objets d'une catégorie, le "hom-set" EST un ensemble... Et oui, les objets ne forment pas des ensembles, mais leurs morphismes entre deux d'entre eux, si. C'est comme ça. Ces morphismes sont des "hom" homomorphismes car internes à la catégorie.
De plus, et ça n'a rien à voir, la catégorie des ensembles, "Set" est une catégorie: voilà qui est inclusif.
Les ensembles et les fonctions
Les "flèches" sont souvent nommées "morphismes". J'ai toujours été choqué par cette "over" interprétation de l'objet défini par deux points ordonnés: elle suppose que les objets sont des ensembles et les flèches des fonctions entre ces ensembles. Bien sur c'est l'interprétation lambda, la primaire la bébête: la catégorie "Set", celle des ensembles et des fonctions, précisément... Cette interprétation a évidemment pour mérite qu'on s'intéresse à la chose, elle est celle qui rend les catégories signifiantes dans le monde enchanté de la programmation, du moins la programmation fonctionnelle. Il faut noter toutefois que l'interprétation catégorielle de la programmation c'est de l'après coup, et du récent.
En fait, il s'agit pour comprendre quelque chose, de tenter donc de développer une sorte d'intuition de ces choses. Cela est possible, car précisément ces concepts là sont intuitifs et ne furent développés QUE pour des raisons intuitives. Au fait Alexandre Grothendick fut bien sur en pointe sur ce coup là, car il avait lui une intuition ça comme...
Les morphismes
On commencera par là, car c'est un "haha". On m'avait expliqué en sixième les subtilités de l'injection et de la surjection entre ensembles, à partir de la notion d'application, dont l'ensemble de départ (on m'expliqua plus tard que c'était le "domaine") est peuplé d'origines exclusivement solitaires pour les flèches qui en partent.
On a donc la surjection et l'injection et leur contraires. Et bien, l'intuition avec les flèches, ou avec les petits ronds, est inutile, on peut exprimer le concept de manière encore plus abstraite, en contraignant les compositions dans une notion purement catégorique.
D'abord la non-surjection: c'est quand l'ensemble de départ se projette dans un sous ensemble strict de l'ensemble d'arrivée. La destination n'est pas couverte, il y a des éléments à l'arrivée qu'on adresse pas, l'ensemble de départ est "trop petit".
Ensuite la non-injection: c'est quand il y a deux éléments de départ qui ont la même destination. L'ensemble de départ est "trop grand"...
Qu'on me comprenne bien, ici les ensembles "de départ" et "d'arrivée" sont des objets DANS une catégorie: on a bien l'interprétation du morphisme comme UNE flèche dans cette catégorie entre ces deux objets là, mais signifiant (au moins "in abstracto") une fonction entre ces objets, un morphisme entre eux donc, à condition que chaque objet soit en fait lui-même un ensemble, c'est à dire composite, permettant de produire la définition faite ici, basée sur une structure imaginaire attribuée aux objets de la catégorie...
De fait, cette explication négative des concepts de surjection et d'injection est bien claire: elle repose hélas sur une vision du monde partielle, la notion est bien plus générale et peut, c'est ça le haha, se décrire avec une vision des ensembles comme des objets ponctuels sans structure interne, simplement reliés par des flèches composables... La catégorie est bien plus (grande, générale, expressive) que l'ensemble. Au lieu d'avoir des ensembles comme des tas de points, on a des catégories comme des tas de points, mais au niveau du dessus: les points sont les ensembles, et au lieu d'imaginer l'intérieur des ensembles, et d'en déduire quelque chose (berk), on se contentera de contraindre les flèches qui en sont issus en produisant un autre type de définition.
Etre une non-surjection pour un morphisme, c'est donc quand il existe un objet de la catégorie et deux flèches différentes de l'ensemble d'arrivée vers cet objet, telles que les deux compositions avec l'application soient égales.
Intuitivement, si on se ramène (comme vous y tenez) à l'"image" des ensembles et de leurs éléments, ici abstraits en des points dans une catégorie, les deux flèches sont égales sur le domaine de l'application et doivent donc, pour pouvoir être différentes, pouvoir partir d'éléments de l'ensemble d'arrivée non adressés: le codomaine est un sous ensemble strict de l'ensemble d'arrivée, ce qu'on se disait plus haut...
L'intuition ensembliste est dégénérée, et on a grâce aux catégories, une intuition de plus haut niveau, qui couvre les objets infinis de tout l'univers: une intuition de l'inimaginable, donc.
Une non-injection est du même type: c'est quand il existe un objet et deux flèches différentes issues de lui vers l'ensemble de départ, telles les compositions avec l'application soient égales. Si les flèches sont différentes, elles diffèrent sur au moins un point, en fait deux points, qui se trouvent donc avoir la même destination. Contre exemple, bingo. Ce qu'on disait s'applique: point besoin des petits points, sinon pour appréhender avec ses pieds. La définition, abstraite, structurelle, prévaut et c'est ça l'idée.
Pour finir, on ajoutera que les catégoriciens sont hellénistes et parlent de monomorphisme (injection) et d'épimorphisme (surjection). On ajoutera également que l'épimorphisme (surjection) permet surtout de simplifier à droite la malheureuse surjection: g1 o f = g2 o f donc, g1=g2, tout comme d'ailleurs le monomorphisme (injection) qui lui est simplifiable à gauche.
Pour finir, on ajoutera aussi que ce n'est que dans la catégorie Set que la conjonction des deux fait d'un morphisme un isomorphisme. Dans la catégorie des Ring, ce n'est pas le cas, et Q et Z ne SONT PAS isomorphes... Alors là, mon prof de maths de 6ème est à la retraite.
Mais pour vraiment finir, on dira qu'épi et mono morphismes s'échangent si on inverse le sens des flèches, c'est à dire si on passe d'une catégorie à sa duale...
Trucs cartésiens
Point besoin de beaucoup de laïus ici, et on devrait apprendre ça en 6ème: le produit c'est le produit cartésien et le coproduit l'union bien sur. Notons l'absence de l'intersection et le fait que l'union est représentée en notant bien pour chaque élément de l'union le nom de son ensemble de départ... Le produit, lui utilise la droite et la gauche du tuple pour noter la chose. Le grand truc de la notion, c'est qu'on la définit bien sur de manière structurale, la chose étant définie non pas par des accouplements impurs, des petits tuples extraits des catégories multipliées (berk), mais par de belles définitions de morphismes qui commutent, le retour aux catégories d'origine se faisant via des fonctions "first" et "second".
Au passage, et pour compléter encore le programme de 6ème, on ajoutera qu'un poset est "un ensemble partiellement ordonné" (un epo).
Un objet initial est tel qu'il a une flèche vers tous les objets de la catégorie. Son dual est le terminal, bien sur.
Une catégorie cartésienne fermée s'identifie à la structure qui SIMULTANEMENT a un produit et une exponentielle. La notion, spécialement complexe est sans doute ce qui est à l'origine de la complexité et de la puissance de la structure structurelle de la belle théorie. On y trouve par exemple, comme corolaire évident, la notion de foncteur adjoint. Par contre, on s'y retrouve assez bien, les ensembles avec leurs morphismes forment une catégorie cartésienne fermée, ouf... Un chapitre entier mérite cette chose, en tout cas.
Les Foncteurs
Les foncteurs sont des opérations de mise en correspondances de catégories, on dit endofoncteur quand les catégories sont les mêmes. Naturellement la "structure" est préservée, et c'est tout l'intérêt de la notion, centrale dans ce domaine des maths, on veut identifier partiellement des objets différents.
Car le Foncteur projette les points mais aussi les blocs de flèches, les "hom-sets". Ce sont des ensembles, et le foncteur est donc défini aussi par les fonctions de projection de tous les hom-sets.
Naturellement, les notions d'injection, de surjection sont préservées mais peuvent s'appliquer à des projections de natures différentes et là on voit qu'on en a plein.
Dans l'interprétation standard des catégories en programmation (on considère la catégorie des types comme points et des fonctions d'un type vers un autre comme les flèches), des Foncteurs apparaissent comme les "constructeurs de type", c'est à dire des endofoncteurs dans la catégorie. Là encore, un simple haha peut se manifester: la notion de "liste", "List", est un foncteur, qui transforme un type quelconque en un type "liste" associé. On a bien la notation fonctionnelle (List[Int] en Scala). L'application fonctionnelle paramétrisée de niveau supérieur... Le type "paramétrisé" n'est que le résultat de l'appel d'une sorte de "fonction", le foncteur.
Au passage on évoquera le terme "lift" (soulever) qui désigne l'opération de passage d'un type à son transformé, nécessairement "vers le haut" pour suivre la notation arbitraire:
M a - fmap f -> M b
^ ^
| F | F
a - f - > b
Ici, "fmap" (en fait la très classique opération "map") est une transformation de fonction, qui exprime la manière dont le foncteur, ici un endofoncteur, transforme les morphismes. "fmap" caractérise le foncteur, et il y en un par foncteur. Par exemple, le map de "List" est évidemment différent du map de "Option".
Cet aspect "double" du foncteur (il transforme les objets ET les flèches) mérite d'être souligné.
Pour finir, la notion de Foncteur comme "container" d'un type, abondamment utilisée en Haskell ou Scala, s'applique assez bien.
Les transformations naturelles
Une transformation entre deux foncteurs est dite "naturelle" intrinsèquement: c'est un morphisme entre foncteurs qui préserve la structure de la transformation. On a là un truc bien abstrait, les deux foncteurs préservant déjà une structure, mais avec une structuration qui leur était propre... Notons que la transformation transforme non seulement le mapping des points, mais aussi le mapping des morphismes.
On a donc un splendide diagramme, qui doit "commuter", pour préserver les structures: n étant un opérateur de transformation naturelle.
On voit que F transforme a et b, et aussi f (un foncteur transforme tout ce qui constitue une catégorie). G aussi , bien sur, et n transforme F en G. Bien sur ça commute, la transformation naturelle d'une functorisation étant égale à la functorisation d'une transformation naturelle... En fait cette "commutatibilité" est le sens même de la "naturalité": si c'est naturel, c'est que ça commute.
---------------> Ga
-na>
a --> Fa |Gf
| |
|f |Ff v
v | Gb
v -nb>
b --> Fb
Quitte à généraliser un peu (mais ici, le terme "over" n'a pas lieu d'être), disons que si une 2-catégorie a aussi des morphismes sur les morphismes, et bien "Cat" (avec les objets formant un ensemble) sera la catégorie des catégories avec comme morphismes les foncteurs et comme 2-morphismes les transformations naturelles. Of course. De plus c'est une catégorie cartésienne fermée: boucle bouclée...
Adjonction
L'adjonction est considérée comme un concept premier de la théorie des catégories. Il s'agit d'une forme d'égalité, et la notion d'égalité, ou de mise en correspondance étant ici première, on en a là une sorte de généralisation.
En gros, on considèrera deux catégories "équivalentes" si il y a deux foncteurs entre elles, dans chaque direction (les droite et gauche) dont les compositions (dans les deux sens) sont isomorphiques aux identités respectives de chacune des deux catégories.
On considèrera les deux catégories comme "adjointes" si il n'y a que deux transformations naturelles unidirectionnelles entre identité et composition d'une part et entre composition duale et identité d'autre part...
L'adjonction est donc une forme affaiblie de d'équivalence, avec un symétrie inversée de la correspondance particulièrement tordue.
En gros, on a les catégories A et B et deux foncteurs AB et BA adjoints, c'est à dire tels que il y ait deux transformations naturelles:
eta: IA -> BA o AB
epsilon: AB o BA -> IB
Monoïdes
Le mot est DABORD utilisé pour désigner des ensembles particuliers (parmi les structures algébriques), dotés de la structure d'associativité et d'élément neutre, l'ancêtre du monoïde étant le semi-groupe à qui il ajoute l'élément neutre. Le semi groupe est le fils du magma, à qui il ajoute l'associativité. Un groupe est un monoïde dont tout élément a un symétrique. Un groupe n'est pas forcément commutatif...
Les monoïdes algébriques peuvent être identifiés à la catégorie à un élément, à part que l'ensemble algébrique est identifié au hom-set de l'unique élément de la catégorie. C'est un ensemble... Les deux notions sont strictement équivalentes donc, mais visibles sous un autre angle, et encore...
En fait, la chose n'est pas exactement celle là et Bartosz rate complètement son coup. On a en fait d'abord les catégories dites "monoïdales", catégories pourvues ENPLUS d'un produit tensoriel et d'une élément neutre suivant la sémantique algébrique traditionnelle. Ce produit tensoriel est un "bifoncteur".
L'associativité est demandée, mais sous la forme d'un isomorphisme (qui est donc une transformation "naturelle", car liant des foncteurs) entre formes duales des foncteurs associés.
La catégorie des ensembles avec le produit cartésien est ainsi une catégorie monoïdale.
On appelle "monoïde" sur une telle catégorie un objet de la catégorie monoïdale que l'on munit LUITOUTSEUL d'une multiplication définie avec le produit tensoriel de la catégorie englobante: MxM->M. Bien sur, on exige un élément neutre et les associativités qui s'imposent.
Il y a en plus une catégorie des monoïdes sur une catégorie monoïdale donnée, formée DES monoïdes avec comme flèches les morphismes qui (utilisant le MEME produit tensoriel global) préservent la structure monoïdale.
Les Monades
Le parangon de la prétention fonctionnelle pour un programmeur et d'identifier sans sourciller les monades aux monoïdes sur la catégorie des endofoncteurs. Cela est donc maintenant à ma portée, même si il y a encore des petites choses qui m'échappent.
Catégorie monoïdale par excellence, la catégorie des endofoncteurs avec pour produit tensoriel la composition se trouve avoir pour monoïdes des entités nommées monades, il suffit de le savoir...
Notez les 3 catégories différentes, parfaitement comparables, mais qui n'ont rien à voir entre elles et qui me permette de faire le malin en les citant hors de propos: la catégorie des ensembles/morphismes (l'interprétation programmatique traditionnelle), la catégorie des endofoncteurs (des morphismes de la catégorie des ensembles citée avant vers eux mêmes)/composition, et la catégorie des monoïdes/morphismes ! Tout ça partage une structure, on s'y perd ou on s'y retrouve...
D'autant plus que les monades sont directement liées à l'adjonction, et que l'on ne peut pas sortir de la cage sans avoir réalisé certaines choses au sujet des relations entre la currification et les listes, et entre l'option et le pointage...
Yoneda
On se permettra finalement, pour déconner, d'évoquer le très abstrait lemme de Yoneda. Car les foncteurs entre deux catégories forment une catégorie dont les flèches sont les transformations naturelles. On note C^D la catégorie des foncteurs de D vers C (en descendant, c'est l'exponentiation).
A partir de là, Yoneda s'est déchainé... Qui l'aime le suive.
(1) http://francoiscarmignola.hautetfort.com/archive/2015/09/30/les-categories-5692791.html
(2) Les vidéos de Bartoscz: https://www.youtube.com/watch?v=I8LbkfSSR58&index=1&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_
(3) Le texte de Bartoscz: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/
(4) La référence en maths: https://ncatlab.org/nlab/show/category+theory
(5) La sainte trinité: https://existentialtype.wordpress.com/2011/03/27/the-holy-trinity/
(6) Gérard Huet: https://pages.lip6.fr/Pierre-Evariste.Dagand/stuffs/notes/cats.pdf