Programmation Fonctionnelle
Qu’est-ce que la programmation fonctionnelle ?
S’il n’est pas facile de répondre précisément à cette question, on peut essayer de mettre en évidence les idées que le paradigme fonctionnel promeut :
-
Les fonctions doivent être des objets de première classe, c’est à dire que les fonctions doivent pouvoir être passées comme arguments à une fonction, les fonctions doivent aussi pouvoir être retournées par une fonction.
-
Les fonctions doivent (le plus possible) être pures, c’est à dire ne générer aucun effet de bord.
-
La manipulation de variable doit être la plus limitée possible : il est possible de s’en servir comme étiquettes mais le contenu de ces variables doit être le moins modifié possible.
-
Les fonctions doivent permettre la composition : la valeur d’une fonction est passée comme argument à une fonction dont la valeur est passée comme argument à une autre fonction, … En fait, le programme lui-même est évalué et retourne une valeur.
-
La récursion doit être utilisée à la place des boucles puisqu’il n’est pas question de modifier l’état d’un programme (donc la valeur d’un compteur de boucle, par exemple).
-
Les listes (c’est même l’origine du langage Lisp) sont souvent la structure de données de base des programmes fonctionnels. Il n’est cependant pas question de modifier ces listes (méthode
append).
Découverte des quelques éléments de programmation fonctionnelle
On peut générer la suite de Collatz, pour un entier donné, de la sorte :
- si est pair, on le divise par 2 ;
- sinon on le multiplie par 3 et on ajoute 1. On stoppe le processus lorsque la valeur de est égale à 1.
La définition de la suite est donc :
Récursivité
- Définir la fonction dont la spécification est :
- Définir la fonction dont la spécification est :
Génération de listes
- Définir la fonction dont la spécification est :
Comment manipuler une liste sans réaliser la moindre boucle ?
Après avoir construit la liste contenant la suite de Collatz débutant au nombre , on peut vouloir en extraire, par exemple, tous les nombres pairs.
-
À l’aide de la fonction
helpdécouvrir la spécification de la fonctionfilter. Écrire cette spécification en français. -
Définir la fonction dont la spécification est la suivante :
- Quelle instruction permet de générer une nouvelle liste ne contenant que les éléments pairs de la liste générée par l’application
collatz(7)?
Remarque : filter réalise une évaluation paresseuse et ne retourne pas une liste mais un itérateur. Ce concept est fondamental en programmation fonctionnelle mais ne sera pas abordé dans ce document.
Le résultat de l’application de filter doit donc être passé comme argument à la fonction list : list(filter(..., ...)).
Programmer la fonction est_pair avec le mot-clé def nécessite d’entrer de nombreuses lignes de code pour, au final, ne nécessiter qu’une seule expression : n % 2 == 0. Les langages fonctionnels permettent généralement de définir des fonctions anonymes (lambda expressions).
En Python, l’expression
est une fonction qui associe à et le nombre . L’application suivante est donc possible
Malheureusement, la fonction anonyme, une fois utilisée est « perdue » puisqu’elle ne possède pas de nom ! Il est cependant possible de la référencer par une variable :
Les fonctions anonymes sont limitées à une expression en Python.
- Reprendre l’instruction qui permet de générer une nouvelle liste ne contenant que les éléments pairs de la liste générée par l’application
collatz(7), en remplaçant l’appel à la fonctionest_pairpar une fonction anonyme.
-
À l’aide de la fonction
helpdécouvrir la spécification de la fonctionmap. Écrire cette spécification en français. -
Quelle instruction permet de générer une nouvelle liste contenant chaque élément de la liste générée par l’application
collatz(7)multiplié par 3 ?
Utiliser une fonction anonyme.
Remarque : map réalise aussi une évaluation paresseuse et ne retourne pas une liste mais un itérateur. Le résultat de l’application de map doit donc être passé comme argument à la fonction list : list(map(..., ...)).
- Quelle instruction permet de générer une nouvelle liste contenant chaque élément pair de la liste générée par l’application
collatz(7)multiplié par 3 ?
Utiliser une fonction anonyme.
List comprehension
Les List Comprehensions, introduites en classe de première, permettent d’écrire en Python des instructions réalisant les mêmes opérations que filter et map de façon très efficace et lisible.
-
Écrire l’instruction qui permet de générer une nouvelle liste ne contenant que les éléments pairs de la liste générée par l’application
collatz(7), à l’aide d’une List comprehension. -
Écrire l’instruction qui permet de générer une nouvelle liste dont les termes sont le triple de chaque terme de la liste générée par l’application
collatz(7), à l’aide d’une List comprehension. -
Écrire l’instruction qui permet de générer une nouvelle liste dont les termes sont le triple de chaque terme de la liste générée par l’application
collatz(7)si ces termes sont pairs, à l’aide d’une List comprehension.
Quelques mots sur l’évaluation paresseuse (laziness)
La fonction collatz génère une liste de nombre. Ce comportement est acceptable tant que le nombre d’éléments de la liste est limité mais terriblement inefficace lorsque le nombre de termes devient très important puisque toute la structure doit être calculée et placée en mémoire avant toute autre opération.
On appelle évaluation paresseuse le mécanisme qui consiste à ne pas construire toute la structure dans un premier temps et à ensuite agir sur cette structure mais à agir sur les éléments au fur et à mesure de leur création.
L’iterateur le plus utilisé jusqu’à présent en cours est range :