Programmation fonctionnelle (I)

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:

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:

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 :

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 :

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:

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:

transforme: (A -> B) -> List[A] -> List[B]

Récrivons donc notre fonction transforme de cette manière:

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:

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.

Comme vu précédemment, un objet foncteur F est un objet ayant la signature suivante:

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:

def id(x):
    return x

alors on a l’égalité suivante:

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:

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.

Vus : 348
Publié par Chimrod : 44