Fonctions d'Ordre Supérieur : Map, Filter, Fold

1. Le principe d'abstraction et les fonctions d'ordre supérieur

En programmation, nous suivons souvent le principe de non-répétition (DRY - Don't Repeat Yourself). Lorsque vous écrivez deux fonctions qui se ressemblent beaucoup, c'est le signe qu'une abstraction est possible.

Une fonction d'ordre supérieur (en anglais, Higher-Order Function ou HOF) est une fonction qui traite d'autres fonctions comme des données : soit elle prend une fonction en argument, soit elle retourne une fonction. C'est le mécanisme principal qui nous permet de capturer des patrons de calcul dans des abstractions réutilisables.

Nous allons maintenant appliquer ce principe pour "découvrir" map, filter et fold.

2. map : Appliquer une transformation

Imaginons que vous ayez besoin d'écrire une fonction qui ajoute 1 à chaque entier d'une liste, et une autre qui concatène une chaîne de caractères à chaque chaîne d'une autre liste. Vous vous retrouveriez avec un code très similaire.

La vidéo suivante illustre parfaitement comment on peut factoriser ce code répétitif pour aboutir à une fonction générique.

Ce processus nous mène à la définition de map : une fonction qui applique une fonction f donnée à chaque élément d'une liste l pour produire une nouvelle liste.

Voici l'implémentation récursive canonique :

let rec map f l =
  match l with
  | [] -> []
  | h :: t -> (f h) :: (map f t)

Le type de map

Le plus intéressant est son type. OCaml l'infère automatiquement :
val map : ('a -> 'b) -> 'a list -> 'b list

Analysons cette signature, qui est l'essence même du polymorphisme :

• ('a -> 'b) : C'est le premier argument, une fonction f. Elle prend une valeur de type 'a et retourne une valeur de type 'b. Les types d'entrée et de sortie peuvent être différents.
• 'a list : Le deuxième argument est une liste d'éléments de type 'a.
• 'b list : Le résultat est une liste d'éléments de type 'b.

map est donc une sorte de "moule" à transformation de listes. Il garantit que si vous lui donnez une liste et une fonction, la structure de la liste sera préservée (la taille reste la même), mais chaque élément sera transformé.

3. filter : Sélectionner des éléments

Le second grand patron de calcul sur les listes est la sélection. Imaginez devoir écrire une fonction evens qui ne garde que les nombres pairs d'une liste, et une fonction positives qui ne garde que les nombres strictement positifs. À nouveau, la structure récursive serait identique.

La fonction filter capture cette abstraction. Elle prend un prédicat (une fonction qui retourne un booléen) et une liste, et retourne une nouvelle liste ne contenant que les éléments pour lesquels le prédicat est vrai.

L'implémentation standard est la suivante :

let rec filter p l =
  match l with
  | [] -> []
  | h :: t ->
      if p h then h :: (filter p t)
      else filter p t

Un aparté crucial : la récursivité terminale

L'implémentation ci-dessus, bien que correcte, a un défaut : elle n'est pas récursive terminale. Sur une très grande liste, elle peut causer un débordement de pile (Stack Overflow). Pour l'Agrégation, il est impératif de savoir transformer une telle fonction en une version récursive terminale à l'aide d'un accumulateur.

La vidéo suivante détaille ce processus pour filter.

La version récursive terminale ressemble à ceci :

let filter p l =
  let rec aux acc l' =
    match l' with
    | [] -> List.rev acc (* On inverse à la fin *)
    | h :: t ->
        if p h then aux (h :: acc) t (* L'accumulateur est mis à jour *)
        else aux acc t
  in
  aux [] l

4. fold : Combiner les éléments

fold (parfois appelé reduce) est l'itérateur de liste le plus fondamental. Il abstrait le patron de calcul qui consiste à "réduire" une liste à une seule valeur en appliquant répétitivement un opérateur binaire. Pensez à calculer la somme ou le produit des éléments d'une liste.

Il existe deux variantes de fold : fold_left et fold_right.

fold_left (pliage à gauche)

fold_left parcourt la liste de gauche à droite, en maintenant un accumulateur. Sa signature est :
val fold_left : ('acc -> 'el -> 'acc) -> 'acc -> 'el list -> 'acc

• ('acc -> 'el -> 'acc) : une fonction qui prend l'accumulateur courant et l'élément suivant pour calculer le nouvel accumulateur.
• 'acc : la valeur initiale de l'accumulateur.
• 'el list : la liste à parcourir.
• Le résultat est la valeur finale de l'accumulateur.

List.fold_left f acc [b1; b2; ...; bn] calcule f (... (f (f acc b1) b2) ...) bn.

fold_left est naturellement récursif terminal, ce qui en fait le fold le plus couramment utilisé en pratique.

Exemples d'utilisation :

(* Calculer la somme d'une liste *)
List.fold_left (+) 0 [1; 2; 3; 4] (* ((((0+1)+2)+3)+4) = 10 *)

(* Calculer la longueur d'une liste *)
List.fold_left (fun acc _ -> acc + 1) 0 ['a'; 'b'; 'c'] (* 3 *)

fold_right (pliage à droite)

fold_right est conceptuellement plus proche de la définition récursive des listes. Il parcourt la liste de droite à gauche.
List.fold_right f [x1; x2; ...; xn] init calcule f x1 (f x2 (... (f xn init) ...)).

Sa signature est :
val fold_right : ('el -> 'acc -> 'acc) -> 'el list -> 'acc -> 'acc

Il est moins utilisé pour des calculs simples car sa version naïve n'est pas récursive terminale, mais il est très naturel pour construire des listes.

La puissance de fold

fold est si puissant qu'il peut être utilisé pour implémenter map et filter. C'est un excellent exercice de réflexion, typique de ce qui peut être demandé à un oral.

5. Exercices de synthèse

Pour consolider votre compréhension, mettez ces fonctions en pratique.

Exercice 1 : map, filter, et fold

En utilisant les fonctions du module List (List.map, List.filter, List.fold_left), écrivez les fonctions suivantes en une seule ligne (sans let rec) :

1. carres_pairs : int list -> int list qui prend une liste d'entiers, ne garde que les nombres pairs, puis retourne la liste de leurs carrés.
   Exemple : carres_pairs [1; 2; 3; 4; 5] doit retourner [4; 16].
2. produit : float list -> float qui calcule le produit de tous les flottants d'une liste.
3. contient_zero : int list -> bool qui retourne true si la liste contient au moins un 0, et false sinon.

(* 1. carres_pairs *)
let carres_pairs l = List.map (fun x -> x * x) (List.filter (fun x -> x mod 2 = 0) l)

(* Une autre façon, en utilisant l'opérateur de pipe |> pour la lisibilité *)
let carres_pairs_pipe l =
  l
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.map (fun x -> x * x)

(* 2. produit *)
let produit l = List.fold_left ( *. ) 1.0 l

(* 3. contient_zero *)
let contient_zero l = List.fold_left (fun acc x -> acc || (x = 0)) false l
(* Alternative plus idiomatique avec List.mem *)
let contient_zero_alt l = List.mem 0 l

Exercice 2 : Le défi fold

Comme mentionné, map et filter peuvent être implémentés avec fold. L'implémentation de map avec fold_right est dans la lecture.
Votre défi : implémentez filter en utilisant List.fold_right.

let mon_filtre p l = List.fold_right ...

let mon_filtre p l =
  List.fold_right (fun x acc -> if p x then x :: acc else acc) l []

(* Décortiquons :
   - la fonction est `fun x acc -> ...`
     - `x` est l'élément courant de la liste (de droite à gauche)
     - `acc` est la liste filtrée déjà construite du reste de la liste
   - `if p x then x :: acc else acc` : Si l'élément `x` satisfait le prédicat,
     on le rajoute en tête de l'accumulateur. Sinon, on retourne l'accumulateur tel quel.
   - `[]` est la valeur initiale de l'accumulateur (la liste vide).
*)

Conclusion

Aujourd'hui, nous avons fait un grand pas dans la pensée fonctionnelle. Vous avez découvert que derrière de nombreux algorithmes sur les listes se cachent des patrons de calculs simples et répétitifs.

Points clés à retenir :

• Les fonctions d'ordre supérieur sont des outils d'abstraction qui prennent des fonctions en argument pour généraliser des comportements.
• map est l'abstraction de la transformation 1-pour-1 des éléments d'une liste.
• filter est l'abstraction de la sélection d'un sous-ensemble d'éléments d'une liste.
• fold est l'abstraction de la combinaison ou de la réduction des éléments d'une liste en une seule valeur. C'est la plus fondamentale des trois.
• La connaissance des signatures de type et de la récursivité terminale est essentielle pour une compréhension profonde et une utilisation correcte de ces fonctions.

Dans notre prochaine leçon, nous allons mettre en synergie les deux dernières leçons. Nous utiliserons les types algébriques pour définir une structure de données classique, l'arbre binaire de recherche, et nous implémenterons ses opérations, où les principes de la programmation fonctionnelle que nous venons de voir s'appliqueront à merveille.