From b9e22325bb46e2611a73e54a3f0ade31800d1bd9 Mon Sep 17 00:00:00 2001 From: Sébastien Dailly Date: Fri, 9 May 2014 14:30:46 +0200 Subject: Moved to pelican 3.3 --- content/Informatique/2012-11-09-fonctionnel.rst | 190 ++++++++++++++++++++++++ 1 file changed, 190 insertions(+) create mode 100644 content/Informatique/2012-11-09-fonctionnel.rst (limited to 'content/Informatique/2012-11-09-fonctionnel.rst') diff --git a/content/Informatique/2012-11-09-fonctionnel.rst b/content/Informatique/2012-11-09-fonctionnel.rst new file mode 100644 index 0000000..06d75d0 --- /dev/null +++ b/content/Informatique/2012-11-09-fonctionnel.rst @@ -0,0 +1,190 @@ + +Programmation fonctionnelle +########################### + +:date: 2012-11-09 +:tags: Programmation + +Dans cet article, je vais essayer de présenter différents cas de programmation +fonctionnelle en essayant de partir d'un cas pratique pour présenter les +difficultés et solutions disponibles. + +Je vais présenter ici des exemples dans le langage python, par ce qu'il s'agit +d'un langage simple, pouvant être utilisé de manière fonctionnelle (dans une +certaine limite). Je me contente d'un python `basique` et ne vais pas chercher +entrer dans des syntaxes spécifiques, le but étant ici de servir de support, et +non pas de présenter le langage. + +Un besoin +========= + +Imaginons la situation suivante : une application reçoit des données d'un +client et doit les traiter. Ces données arrivent dans des fichiers textes, +chaque ligne du fichier correspond à une donnée à traiter. + +Un programme +============ + +Commençons le programme, pour lire le fichier commençons par le localiser : + +.. code-block:: python + + def get_file(nom): + chemin = os.path.join("repertoire", nom) + return open(chemin) + +Cette fonction est simple : elle prend en argument un nom de fichier, et +retourne le fichier correspondant. On peut également dire qu'elle effectue la +transformation suivante : + +.. code-block:: ocaml + + get_file: String -> File + +Cette notation indique que le type de la fonction est le suivant : elle prend +un string en entrée, et retourne un file en sortie. Nous l'utiliserons +régulièrement dans cet article. + +Dans notre cas, nous n'avons pas un fichier a traiter, mais une série de +fichiers. Nous allons donc devoir appeler la fonction sur tous nos nom de +fichiers. La première solution est la solution itérative, à travers une boucle +: + +.. code-block:: python + + def transforme(noms): + fichiers = [] + for nom in noms + fichiers.append(get_file(nom)) + return fichiers + +À la fin de l'exécution de la boucle, la liste `fichiers` contient la liste des +fichiers construits à partir de la liste `noms`. + +C'est une opération très fréquente et bien qu'elle soit très courte. Essayons +de réfléchir un peu à ce que nous venons de faire en terme de type : notre but +est de transformer une liste de String en liste de File de la manière suivante +: + +.. code-block:: ocaml + + transforme: List[String] -> List[File] + +Si l'on généralise, on peut essayer de créer une fonction qui aurait le schéma +suivant : + +.. code-block:: ocaml + + transforme: List[A] -> List[B] + +Cette fonction a par contre besoin d'une transformation à appliquer pour +transformer A en B, dans notre cas, cette transformation a déjà été créée plus +haut ! + +Notre schéma devient donc le suivant : + +.. code-block:: ocaml + + transforme: (A -> B) -> List[A] -> List[B] + +Récrivons donc notre fonction transforme de cette manière: + +.. code-block:: python + + def transforme(func, source): + results = [] + for nom in source + results.append(func(nom)) + return results + + fichiers = transforme(get_file, noms) + +Et voilà ! Nous avons maintenant notre fonction générique, destinée à changer +le contenu de notre liste. Qu'est ce que cela apporte par rapport à la version +impérative que nous avons écrit tout à l'heure ? En fait pas grand chose. Sauf +que la fonction `transforme` est présente nativement dans python. Elle +s'appelle en fait `map`, et effectue le même travail. + +Nous aurions donc tout aussi bien pu écrire : + +.. code-block:: python + + fichiers = map(get_file, noms) + +Une réflexion +============= + +Pourquoi avoir écrit tout ça ? Par ce que semblant de rien, nous avons changé +notre manière de concevoir le programme : au lieu d'écrire une suite +d'instructions qui s'exécutent séquentiellement, nous venons d'appliquer des +transformations dans un contexte : la liste des noms de fichiers est notre +contexte de base, sur lequel nous appliquons des transformations pour créer un +autre contexte. + +Ces transformations ne modifient pas notre contexte initial, et par la suite +les transformations que nous continueront d'appliquer ne modifieront rien non +plus de notre environnement. Dans cet esprit, l'ensemble du programme peut être +perçu comme un grande transformation qui s'applique sur un point d'entrée +initial. + +Une théorie +=========== + +La fonction `map` que nous venons de présenter ici, s'inscrit en fait dans un +cadre de fonctions plus vaste : les foncteurs_. Il s'agit d'une notion +mathématique que l'on retrouve appliquée en informatique. + +.. _foncteurs: http://fr.wikipedia.org/wiki/Foncteur + +Comme vu précédemment, un objet foncteur F est un objet ayant la signature +suivante : + +.. code-block:: ocaml + + map: (A -> B) -> F[A] -> F[B] + +Le foncteur a deux contraintes, qui sont plutôt intuitives: + +identité +-------- + +Soit la fonction `id` défini comme suit: + +.. code-block:: python + + def id(x): + return x + +alors on a l'égalité suivante : + +.. code-block:: python + + map(id, fichiers) == fichiers + +Autrement dit, le foncteur ne doit pas modifier la structure de la donnée. On +peut essayer de repenser la fonction `transforme` écrite plus haut pour briser +cette règle, je laisse au lecteur le soin de réfléchir à cette question. + +composition +----------- + +La deuxième contrainte est celle de la composition : + +.. code-block:: python + + map(f(g), source) = map(f, map(g, source)) + +C'est à dire qu'il est possible de composer les fonctions les entre elles : +c'est encore heureux, car cela permet de chaîner les traitements entre eux… + +Une conclusion +============== + +Notre contexte est ici une liste, mais nous allons voir par la suite qu'il en +existe beaucoup d'autres, ce qui va nous faciliter la vie… Cela va venir dans +les articles qui suivent. + +Une fois les deux contraintes validées, nous allons pouvoir construire de +nouveaux types basés sur ce foncteur. Et derrière la solution informatique mise +en place, je vais essayer de présenter les concepts mathématiques qui sont +derrière. -- cgit v1.2.3