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.