La programmation fonctionnelle a de nombreux attraits dont le traitement réservé aux fonctions. Dans beaucoup de langages de programmation les fonctions ont un statut particulier. Par exemple en Java il est possible de créer un entier, de l’assigner à une variable ou de le passer comme argument à une autre fonction mais on ne peut pas de même avec les fonctions. En revanche les fonctions jouent un rôle central dans la programmation fonctionnelle et ne sont pas traitées comme des citoyens de seconde zone par les langages dits fonctionnels (Haskell, Caml, Clojure etc.). Cela est important pour l’écriture de certains types d’abstractions bien utiles et courantes en développement comme nous le verrons dans la suite mais avant d’aller plus loin définissons une fonction.
C’est quoi une fonction ?
Ce qu’on entend par fonction varie selon les langages de programmation mais la définition que je vais donner ici est suffisante pour les propos de l’article. Une fonction est une transformation qui produit une valeur à partir d’un ensemble de paramètres, les arguments de la fonction.
Les choses seront plus claires avec des exemples. Si nous notons par x un nombre entier quelconque. x peut donc prendre comme valeur 0, 1, 2 etc. nous pouvons définir la fonction f comme suit :
Ne vous laissez pas impressionner par la notation. f est le petit nom donné à la fonction, la lettre x à gauche de la flèche désigne l’argument de la fonction et à droite se trouve sa définition. En donnant une valeur spécifique au paramètre, par exemple 1 nous obtenons :
Si x vaut 3 la valeur retournée par la fonction est :
Au vu de ces valeurs il est aisé de comprendre que cette fonction double la valeur qu’on lui passe en paramètre. Renommons la fonction afin de mieux exprimer cette intention :
Le langage Scala est utilisé dans la suite pour illustrer nos propos. Et la fonction double est codée en Scala comme suit :
def double(number: Int) = 2 * number
Dans le code ci-dessus le mot clé def permet de définir une fonction. Il est suivi du nom de la fonction. J’ai choisi, à la place du paramètre x, un nom plus parlant : number. L’annotation Int (pour Integer) spécifie au compilateur que le paramètre number est un entier. Le reste du code est une traduction parfaite du pseudo code.
Les sorties suivantes de la console interactive (REPL) de Scala permettent de tester notre fonction :
$ scala scala> def double(number: Int) = 2 * number double: (number: Int)Int scala> double(3) res0: Int = 6 scala> double(1) res1: Int = 2
Une fonction peut avoir plusieurs arguments par exemple la fonction faisant la somme de deux nombres entiers prend deux arguments. Soient x et y les deux entiers dont nous souhaitons faire la somme, la fonction add est définie comme suit :
Cette définition se traduit aisément en Scala de la façon suivante :
def add(x:Int, y:Int) = x + y
Le test de la fonction donne :
$ scala scala> def add(x:Int, y:Int) = x + y add: (x: Int, y: Int)Int scala> add(1, 2) res0: Int = 3
Et si nous souhaitions définir une fonction qui incrémente un entier nous pouvons réutiliser la fonction add. En effet incrémenter un entier revient à lui ajouter 1 :
def increment(number: Int) = add(number, 1)
En action cela donne:
scala> def increment(number: Int) = add(number, 1) increment: (number: Int)Int scala> increment(3) res1: Int = 4 scala> increment(10) res2: Int = 11
Note : Une propriété importante de chacune des fonctions que nous avons vues jusque là est le fait que la valeur de retour est entièrement déterminée par les arguments de la fonction.
Munis de ces informations passions aux fonctions d’ordre supérieur.
Les fonctions d’ordre supérieur
Une fonction d’ordre supérieur est une fonction qui a au moins l’une des deux caractéristiques suivantes :
- prend en paramètre une ou plusieurs fonctions
- sa valeur de retour est une fonction
Les fonctions d’ordre supérieur aident à l’expressivité du code en mettant l’attention sur la tâche à accomplir plutôt que sur la façon de l’accomplir : le code dévient ainsi plus déclaratif. Cela devient plus clair avec un exemple. Considérons la classe Person ci-dessous :
public class Person {
private final String name;
private final String email;
private final int age;
public Person(String name, String email, int age) {
this.name = name;
this.email = email;
this.age = age;
}
public String getName() {
return name;
}
public String getEmail() {
return email;
}
public int getAge() {
return age;
}
}
Supposons que vous disposez d’une liste d’objets de type Person sur laquelle vous souhaitez faire différentes opérations : transformation, filtrage etc. Commençons par la transformation de la liste.
Transformation des éléments d’une collection
Voici la liste initiale :
List<Person> persons = Arrays.asList(// new Person("Toto", "toto@email.com", 23), // new Person("John Doe", "john.doe@email.com", 34), // new Person("Mad Max", "mad.max@crazymail.com", 20), // new Person("Jane Doe", "jane@email.com", 17));
La première transformation qui nous intéresse est l’extraction des adresses email à partir de la liste des personnes. C’est ce que fait la méthode extractEmails :
public static List<String> extractEmails(List<Person> persons) {
List<String> emails = new ArrayList<String>();
for (Person person : persons) {
emails.add(person.getEmail());
}
return emails;
}
Testons ce que cela donne :
System.out.println("Emails = " + extractEmails(persons));
Sortie de la console :
Emails = [toto@email.com, john.doe@email.com, mad.max@crazymail.com, jane@email.com]
On obtient une liste ayant la même taille que la liste des personnes mais ne contenant que les adresses email. Le code de la méthode extractEmails recèle quelques défauts dont la “dilution” de l’intention de la méthode dans du code verbeux.
Avant de voir comment résoudre ces défauts implémentons une autre fonctionnalité : extraire les noms à partir de la liste des personnes :
public static List<String> extractNames(List<Person> persons) {
List<String> names = new ArrayList<String>();
for (Person person : persons) {
names.add(person.getName());
}
return names;
}
Cette méthode fait ressortir un autre défaut de notre code : la duplication. Les deux méthodes ne diffèrent véritablement que par la transformation effectuée à chaque itération sur l’élément de la liste initiale. Cette transformation peut être matérialisée par une fonction f qui prend comme argument un objet de type Person et retourne son nom ou son adresse email. Ainsi l’implémentation de l’une ou l’autre de nos fonctions se résume comme suit : "applique la fonction f à chaque élément de la liste initiale et renvoie-moi la liste correspondante."
Nous pouvons schématiser cette phrase de la façon suivante, avec à gauche la liste initiale et à droite la liste obtenue suite à la transformation :
Cela correspond exactement à ce que fait la fonction map. La figure ci-dessous donne le fonctionnement de la méthode map présente sur la classe List de Scala.
Comme mentionné sur la figure la fonction map prend en paramètre une fonction, celle que nous souhaitons appliquer à chaque élément de la liste initiale. Dans notre cas la fonction a comme type Person => String.
Nous allons maintenant réimplémenter nos deux méthodes en utilisant la méthode map disponible dans l'API des listes Scala.
Les fonctions extractEmails et extractNames revisitées
Définition de la classe Person :
case class Person(name: String, email: String, age: Int)
Nous définissons d’abord la fonction qui extrait une adresse email à partir d’une instance de Person :
def extractEmail(person: Person) = person.email
Puis nous passons cette fonction à la méthode map de la liste afin de récupérer la liste des adresses email.
def extractEmails(persons: List[Person]): List[String] = persons.map(extractEmail)
Sur le même principe voici la définition de la fonction extractNames :
def extractName(person: Person) = person.name def extractNames(persons: List[Person]): List[String] = persons.map(extractName)
def extractNames(persons: List[Person]): List[String] = persons.map(p => p.name) def extractEmails(persons: List[Person]): List[String] = persons.map(p => p.email)
Qu'avons-nous gagné par rapport à avant ? Le code est plus expressif en éliminant le bruit et en mettant l’accent sur l’intention du code : "mapper chaque élément de la liste sur son application à la fonction que nous passons à la méthode map".
Les fonctions d’ordre supérieur rendent pratique une autre opération courante sur les collections : le filtrage.
Filtrer une collection
Nous disposons d’une liste de nombres entiers allant de 1 à 15 et nous souhaitons filtrer cette liste en éliminant tous les éléments qui ne sont pas des multiples de 3. Ce genre d’opération est résolu en programmation fonctionnelle avec la fonction d’ordre supérieur filter. Elle prend en arguments une liste et un prédicat, une fonction qui retourne "vrai" ou "faux". Dans notre exemple le prédicat retourne “vrai” si son argument est un multiple de 3 et "faux" dans le cas contraire. Scala étant un langage orienté-objet filter est une méthode de List.
Voici la définition du prédicat :
scala> def isMultipleOfThree(number: Int) = number % 3 == 0 isMultipleOfThree: (number: Int)Boolean scala> isMultipleOfThree(2) res0: Boolean = false scala> isMultipleOfThree(6) res1: Boolean = true
Et la liste de nombres :
scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
Le filtrage s’effectue simplement en passant la fonction isMultipleOfThree à la méthode filter de la liste de nombres :
scala> val multiplesOfThree = numbers.filter(isMultipleOfThree) multiplesOfThree: List[Int] = List(3, 6, 9, 12, 15)
Ceci peut être réécrit en remplaçant isMultipleOfThree par une fonction anonyme :
scala> numbers.filter(number => number % 3 == 0) res2: List[Int] = List(3, 6, 9, 12, 15)
Nous allons maintenant combiner filter et map.
Combiner filter et map
Nous souhaitons obtenir la somme des doubles des multiples de 3 compris entre 1 et 15. Cela correspond à une opération de filtrage (suppression des nombres non multiples de 3) suivie d’une transformation des éléments (doublement des éléments des éléments restants) et enfin une opération de réduction (la sommation). On y arrive aisément avec le code suivant :
scala> val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) scala> numbers.filter(number => number % 3 == 0).map(number => number * 2).sum res7: Int = 90
Il nous reste une dernière fonction d’ordre supérieur à découvrir avant de conclure cet article : la fonction fold.
La fonction fold, le couteau suisse
La fonction fold est un véritable couteau suisse. Elle réduit les éléments d’une liste en une valeur. Cette fonction existe en deux versions : l’une (foldLeft) parcourt la liste de la gauche vers la droite et l’autre de la droite vers la gauche (foldRight). Nous allons plutôt utiliser la première dont voici la signature :
def foldLeft[B](z: B)(f: (B, A) ⇒ B): B
C’est une fonction curryfiée. Elle prend une valeur initiale de type B, désignée par z et une fonction f prenant deux arguments de types A (le type des éléments de la liste) et B. Pour chaque élément de la liste la fonction f est invoquée. f est invoquée avec la valeur initiale z fournie à la méthode foldLeft. Puis la valeur résultante est passée avec le deuxième élément de la liste à la fonction f. Ce processus continue avec tous les éléments de la liste. Pensez à lire cet article si vous souhaitez en savoir davantage. Place à l’action !
Afin de comprendre comment fonctionne foldLeft nous allons résoudre trois petits problèmes. Le premier problème consiste à faire la somme des éléments d’une liste d’entiers.
La valeur initiale dans le cas de la somme est 0 (l’élément neutre de l’addition) et la fonction f additionne ces deux paramètres. Voici ce que cela donne dans le REPL :
scala> val nums = List(1, 2, 3, 4) nums: List[Int] = List(1, 2, 3, 4) scala> val sum = nums.foldLeft(0)((acc, num) => acc + num) sum: Int = 10 scala> val nums2 = List(1, 3, 5, 7) nums2: List[Int] = List(1, 3, 5, 7) scala> val sum2 = nums2.foldLeft(0)((acc, num) => acc + num) sum2: Int = 16
Simple non ?! Ne nous arrêtons pas en si bon chemin continuons sur le deuxième problème : faire le produit des éléments d'une liste. La valeur initiale passée à foldLeft dans ce cas est l’élément neutre de la multiplication à savoir 1. Quant à la fonction à passer foldLeft elle fait le produit de ces deux paramètres.
scala> val nums = List(1, 2, 3, 4) nums: List[Int] = List(1, 2, 3, 4) scala> val prod = nums.foldLeft(1)((acc, num) => acc * num) prod: Int = 24 scala> val nums2 = List(1, 3, 5, 7) nums2: List[Int] = List(1, 3, 5, 7) scala> val prod2 = nums2.foldLeft(1)((acc, num) => acc * num) prod2: Int = 105
So far so good! Maintenant résolvons le dernier exercice pour la route. Il s’agit de construire à partir d’une liste d’entiers une map dont les clés sont les éléments pairs de la liste et les valeurs leurs doubles. Voyons un exemple afin de clarifier les choses :
List(7, 2, 10, 8, 6) -> Map(2 -> 4, 10 -> 20, 6 -> 12)
La valeur initiale est une map vide. La fonction passée à foldLeft prend une map et un entier. Si l’entier est pair son double est mappé sur sa valeur. La fonction retourne la map résultante.
scala> val nums = List(1, 2, 3, 4)
nums: List[Int] = List(1, 2, 3, 4)
scala> val evenDoubled = nums.foldLeft(Map[Int, Int]()) { (acc, num) =>
| if (num % 2 == 0) acc + ((num, 2 * num)) else acc
| }
evenDoubled: scala.collection.immutable.Map[Int,Int] = Map(2 -> 4, 4 -> 8)
Pour conclure
Nous arrivons à la fin de cette introduction aux fonctions d’ordre supérieur. Elles sont particulièrement adaptées aux traitements sur des collections. Mais leur usage va au-delà des collections. Consultez la liste de références ci-dessous pour aller loin.
Références
- Higher Order functions
- Learn you a Haskell for Great Good !
- Pure, functional Javascript
1 comment for “Les fonctions et les fonctions d’ordre supérieur”