Les foncteurs

aha! A force de lire de la vulgarisation neuneu, on finit par avoir quelques éclairs. 

Ici on a réalisé la correspondance entre concepts de la théorie des catégories et autre fonctionnellations des langages de programmation. Plus exactement on a réalisé le sens des mots, la plus importante chose qui soit au monde. 

Algèbre

D'abord l'algèbre (al gabr)  c'est ce qui permet la réduction (chirurgicale, aussi) dans le calcul. L'"algébrique" c'est tout ce qui traite des "opérations" sur les objets. L'opération chirurgicale veut donc dire ce que ça veut dire... 

Une structure algébrique est une collection d'objets (on ne dira pas "ensemble" par snobisme) et une opération, définie par une collection des flèches entre les objets. 

Les structures algébriques se différencient suivant leurs propriétés... Les principales d'entre elles concernent la composition entre les flèches. On doit bien distinguer flèche et composition entre flèches. En fait la véritable "opération" est bien sur celle qui s'applique entre deux flèches et qui produit une autre flèche. "Produit" et non "Réduit" à moins que ce ne soit l'inverse, la réduction consistant à remplacer les deux flèches originales par une nouvelle. 

Une "catégorie" se caractérise par une composition associative des flèches, avec une flèche identité pour chaque objet qui compose à l'identique dans les deux directions. La catégorie est la première structure de ce type, la structure "première" donc.

D'un certain point de vue, une catégorie est exclusivement un ensemble de flèches, les flèches "identité" représentant très bien les objets...

Le "monoïde", catégorie à un objet, n'a qu'une flèche identité et autant de flèches composables de et vers l'unique objet qu'on veut. Une seule flèche composable suffit pour toute les avoir par composition. L'image de tout cela est évidemment l'ensemble des entiers défini par zéro (la flèche identité) et l'incrément (la flèche "inc") qui peut générer tout entier par exemple 1000 (inc composé 1000 fois avec elle-même). 

Une catégorie n'est pas "fermée", car deux flèches peuvent très bien ne pas "composer".  Elle n'est pas forcément ni "invertible" ni "commutative", comme les groupes et les groupes abéliens. 

Un "monoïde" est évidemment "fermé" et un "semi groupe" n'est pas "invertible".

Un "groupoïde" est une catégorie "invertible".

Un "magma" n'a qu'une propriété: la "fermeture"... 

Entre catégories, on a les "foncteurs" qui sont des transformations de catégorie à catégorie qui préservent la structure de la catégorie, c’est-à-dire associent une flèche associative de l'un à une flèche  associative de l'autre... 

Entre les foncteurs, on a les "transformations naturelles". Elles jouent le rôle des flèches dans la catégorie des foncteurs. 

Programmes

La correspondance avec la programmation est basique. "Prog" est la catégorie des types et les flèches sont les fonctions entre les types. 

On passe tout de suite aux "foncteurs", en fait les "endofoncteurs" restant dans Prog. 

On les définira comme DEUX fonctions, une entre types (un type générique étant évidemment une application des types vers les types) et une entre flèches, c’est-à-dire entre fonctions. La deuxième fonction est une fonctionnelle, c’est-à-dire prend en argument une fonction simple entre deux types, une flèche, quoi. 

Aha ! Un  trait "higher kind" F[_] doté d'une fonction "map" qui préserve la structure est donc un "foncteur". 

Note: préserver la structure signifie préserver la structure des flèches: s'il y a flèche, l'image de la flèche sera une flèche. Par conséquent "map", la fonction de correspondance entre flèches aura pour signature dans "Prog": 

A->B    ->    F[A]->F[B]

Ce qui exactement la projection astucieuse et pratique que l'on utilise dans les langages Haskell et Scala. 

Pour enfoncer le clou sur cette histoire de vocabulaire,

1) On dit que la fonction (la flèche) originale mappée par map est "liftée" (soulevée, poussée) en une fonction de l'autre monde. 

2) On dit que le type générique F[_] est en fait un "constructeur unaire" du type de destination du foncteur (en fait sa première fonction de mapping) 

3) Toutes les associations possibles internes à Prog sont ainsi par extensions des "foncteurs", le mot étant la super classe des entités dérivées qui toutes rajoutent des moyens de produire des flèches dans Prog. 

On trouvera ainsi parmi les foncteurs, les "Applicative"s et les "Monades". 

Monades

Les endo-foncteurs de Prog forment une catégorie (la démonstration est laissée au lecteur). 

On va chercher à construire un monoïde dans cette catégorie là. Pour cela il nous faut un objet, un foncteur donc, et deux flèches. Une identité, qui associe le foncteur avec lui-même et une opération "binaire" ou une addition itérable.

L'identité est une identité entre foncteurs appliquée au foncteur choisi. C'est une flèche qui s'identifie au foncteur lui-même c’est-à-dire à son constructeur. La fonction qui à partir d'un type donné donne son correspondant fonctor-arisé (...). Ce sera la flèche "zéro" du monoïde, qui transforme le foncteur en lui-même exactement. 

La flèche "un" ("inc") du monoïde va transformer le foncteur en lui-même mais d'une manière différente. Pour décrire cette transformation, il faut considérer la signification profonde du foncteur, sa structure interne ! En effet un foncteur est lui-même une transformation de types et de flèches. Pour décrire une transformation de foncteurs on doit spécifier comment se font les mises en correspondances internes des objets. 

Par exemple un carré peut être mis en correspondance avec lui-même de plusieurs manières, suivant la manière dont on le retourne. 

Ici, on va mettre en correspondance les flèches de A vers F[B] et les flèches de F[A] vers F[B]. La transformation des flèches va s'appeller "flatMap". Est ce la bonne interprétation ? En tout cas je me comprends. 

En fait, on se doit de considérer les "transformations naturelles", qui sont les flèches entre endofoncteurs.

Une autre tentative est la définition stricte: les deux "transformations naturelles" à définir pour que le monoïde apparaisse sont :

"éta" l'identité et "mu" la composition. En fait ce sont des contraintes supplémentaires sur le foncteur choisi.

Une monade est donc un monoïde sur la catégorie des endofoncteurs, et s'identifie donc à un endofoncteur unique. 

On se retrouve avec un nouveau foncteur, la "monade", et  une opération supplémentaire, flatMap. 

Ce qu'il y a d'assez saisissant ici, c'est le boulevard de correspondances signifiantes et organisées qui s'ouvre devant nous. 

Car la monade c'est aussi un foncteur sur la catégorie de Kleisli. 

On a ici une transformation de flèches particulières, celle de A vers C ou C est en fait l'image par F d'un type B, que finalement on retrouve après la transformation. Ces flèches qui transforment par le foncteur leur type de destination, ici B, sont des "flèches de Kleisli". Leur type de destination est le résultat d'une transformation ou extension, qui modélise ce qu'on appelle en programmation fonctionnelle un "effet". Par exemple, le foncteur "option" ajoute une valeur indéterminée (None) à tout type. On avait déjà expliqué ce genre de chose. La catégorie de ces flèches est la catégorie de Kleisli. 

Ce qui est propre à la monade, c'est de transformer les flèches de Kleisli de manière à les rendre composables, la composition via flatMap ayant la sémantique du séquencement avec passage de paramètres, essence de la programmation "utile", celle qui consiste à programmer(...). 

 

Les références explicitent tout cela bien mieux... 

Applicatives 

Il y a mieux et moins connu, mais tout aussi essentiel à la compréhension de la partie "catégorie" de la programmation fonctionnelle. C'est "Applicative", l'intermédiaire entre Foncteur et Monade, un autre foncteur (5).

La fonction de mapping des flèches qui produit une flèche entre les images de deux objets par le foncteur est ici appliquée non pas aux flèches elles-mêmes (comme pour les foncteurs) , aux flèches de kleilsli (comme pour les monades) mais pour l'image par le foncteur d'une flèche:

F[A=>B]    =>   F[A] => F[B]

Pour comprendre "ap", il faut se ramener à "List". 

La fonctorisation de la flèche va donner ici une liste de fonctions à appliquer: 

(_+1 , _+2) ap List(0, 1) == (1, 2)  ++ (2, 3)  

Le truc marrant dans l'histoire, est que l'on peut lors de cette fabrication, distribuer les fonctions ou les associer strictement dans la liste passée en argument. Les deux formes sont compatibles avec les lois. Tout sera alors une question de dénomination. 

On doit évoquer aussi mapN... 

 

 

(1) https://medium.com/free-code-camp/demystifying-the-monad-in-scala-cc716bb6f534

(2) https://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

(3) histoire des langages de programmation http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html

(4) les monades par tous les bouts https://justinhj.github.io/2021/02/02/monads-in-scala-3-for-the-genius.html

(5) Whatsap ? https://justinhj.github.io/2020/04/04/whats-ap.html