Vue d'ensemble
Tu as déjà écrit dix fois la même récursion : « parcourir une liste et faire quelque chose à chaque élément ». En OCaml, une fonction est une valeur comme une autre : on peut la stocker, la passer en argument, la renvoyer. Cela permet d'écrire une seule fois le squelette du parcours, et de lui confier « ce qu'il faut faire » sous la forme d'une petite fonction. C'est toute l'idée des fonctions d'ordre supérieur, et des trois outils incontournables du programme : List.map, List.filter et List.fold_left.
fun x -> ...) ; passage d'une fonction en argument. Les itérateurs de la bibliothèque List : map, filter, fold_left. Savoir les utiliser et savoir les réécrire soi-même récursivement par filtrage. Aucun théorème n'est exigible ici : l'objectif est la maîtrise pratique.
Prérequis
- Manipulation des listes OCaml : constructeur
::, liste vide[], et filtrage (match ... with) — fiche ocaml-filtrage-listes. - Écrire une fonction récursive simple sur une liste (longueur, somme).
- Distinguer les opérateurs entiers (
+ - * /,mod) des opérateurs flottants (+. -. *. /.).
Le déclic « une fonction est une valeur ». C'est le concept qui sépare ceux qui subissent l'info de ceux qui la dominent. Nos mentors alumni X · Centrale · Mines te le font passer en une séance, sur tes propres exos.
Trouver un mentor →Fonctions anonymes et ordre supérieur
Une fonction est dite d'ordre supérieur lorsqu'elle prend une fonction parmi ses arguments, ou renvoie une fonction comme résultat (ou les deux). Par opposition, une fonction dite de premier ordre ne manipule que des données « ordinaires » (entiers, listes, etc.).
Une fonction anonyme est une fonction écrite sans lui donner de nom, avec la syntaxe fun paramètre -> expression. Par exemple fun x -> x * x est la fonction « élever au carré ». On l'utilise directement là où on en a besoin, typiquement en argument d'une fonction d'ordre supérieur.
Nommer une fonction ou l'écrire anonymement, c'est exactement la même chose. Les deux définitions ci-dessous produisent la même fonction :
let carre x = x * x (* version nommée *)
let carre = fun x -> x * x (* version anonyme, liée au nom carre *)
(* carre 5 vaut 25 dans les deux cas *)let carre x = x * xdéfinition usuelle : carre prend un argument x et renvoie x * x.let carre = fun x -> x * xon lie le nom carre à la valeur fonctionnelle fun x -> x * x. Une fonction est une valeur : on peut la mettre dans un let comme un entier.carre 5applique la fonction à 5 ; l'évaluation remplace x par 5, donne 5 * 5 = 25.Écrivons maintenant notre première fonction d'ordre supérieur : elle reçoit une fonction f et une valeur x, et se contente d'appliquer f à x.
let applique f x = f x
let r1 = applique carre 5 (* 25 *)
let r2 = applique (fun x -> x + 1) 9 (* 10 *)let applique f x = f xf est un argument qui est une fonction ; x est une valeur. Le corps f x applique f à x. C'est ce qui fait de applique une fonction d'ordre supérieur.applique carre 5ici f = carre et x = 5, donc on calcule carre 5 = 25.applique (fun x -> x + 1) 9on passe une fonction anonyme comme argument, sans la nommer ; f = (fun x -> x+1), x = 9, résultat 9 + 1 = 10.applique : ('a -> 'b) -> 'a -> 'b. La présence d'une flèche à l'intérieur des parenthèses du type d'un argument (ici 'a -> 'b) est la signature typographique d'un argument fonctionnel : tu tiens une fonction d'ordre supérieur.List.map — transformer chaque élément
List.map f l applique f à chaque élément de l et renvoie la liste des résultats, dans le même ordre. List.filter p l garde les éléments de l qui vérifient le prédicat p (une fonction renvoyant un booléen). List.fold_left f acc l accumule : elle combine les éléments un à un dans un accumulateur initialisé à acc, de la gauche vers la droite.
Commençons par map. Elle transforme une liste en une autre de même longueur :
let carres = List.map (fun x -> x * x) [1; 2; 3]
(* carres = [1; 4; 9] *)
let longueurs = List.map String.length ["ab"; "cpge"; ""]
(* longueurs = [2; 4; 0] *)List.map (fun x -> x * x) [1; 2; 3]on applique le carré à chaque élément : 1→1, 2→4, 3→9. La liste de sortie a autant d'éléments que celle d'entrée.List.map String.length [...]f n'a pas besoin d'être anonyme : String.length est déjà une fonction, on la passe telle quelle. map renvoie ici une liste d'entiers à partir d'une liste de chaînes : le type d'entrée et de sortie peuvent différer.List.map ne peut ni ajouter ni supprimer d'élément : la liste résultat a toujours exactement la même taille que l'entrée. Si tu veux éliminer des éléments, ce n'est pas map qu'il te faut, mais filter.Réécrire map soi-même
Pour démystifier List.map, réécrivons-la par récursion et filtrage. C'est un exercice de cours classique.
let rec map f l =
match l with
| [] -> []
| x :: reste -> (f x) :: map f restelet rec map f l =rec car la fonction s'appelle elle-même ; elle reçoit la fonction f et la liste l.match l withon distingue les deux formes possibles d'une liste : vide, ou « une tête suivie d'un reste ».| [] -> []cas de base : transformer la liste vide donne la liste vide. Sans lui, la récursion ne s'arrêterait jamais.| x :: reste -> (f x) :: map f restecas récursif : x est la tête, reste la queue. On calcule f x (l'élément transformé), et on le place en tête (::) devant le résultat du traitement récursif du reste. L'ordre est donc préservé.| Étape | Appel en cours | x | f x | Valeur renvoyée (en remontant) |
|---|---|---|---|---|
| 1 (descente) | map f [1;2;3] | 1 | 1 | en attente de map f [2;3] |
| 2 (descente) | map f [2;3] | 2 | 4 | en attente de map f [3] |
| 3 (descente) | map f [3] | 3 | 9 | en attente de map f [] |
| 4 (base) | map f [] | — | — | [] |
| 5 (remontée) | retour étape 3 | 3 | 9 | 9 :: [] = [9] |
| 6 (remontée) | retour étape 2 | 2 | 4 | 4 :: [9] = [4;9] |
| 7 (remontée) | retour étape 1 | 1 | 1 | 1 :: [4;9] = [1;4;9] ✓ |
List.filter — garder ce qui vérifie un test
List.filter p l conserve les éléments x tels que p x vaut true, dans l'ordre, et jette les autres. p s'appelle un prédicat : une fonction à valeurs booléennes.
let pairs = List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4]
(* pairs = [2; 4] *)
let non_vides = List.filter (fun s -> s <> "") ["a"; ""; "bc"; ""]
(* non_vides = ["a"; "bc"] *)fun x -> x mod 2 = 0prédicat « x est pair ». x mod 2 est le reste dans la division entière par 2 ; = 0 le teste. Attention : ici = est le test d'égalité (booléen), pas une affectation.List.filter (...) [1;2;3;4]on teste chaque élément : 1 impair (jeté), 2 pair (gardé), 3 impair (jeté), 4 pair (gardé) → [2; 4].fun s -> s <> ""<> est l'opérateur « différent de » en OCaml. Ce prédicat garde les chaînes non vides.map, la liste renvoyée par filter a une longueur inférieure ou égale à celle de l'entrée. Elle peut même être vide si aucun élément ne passe le test. filter ne transforme jamais les éléments : il les garde tels quels ou les supprime.l », on filtre d'abord, puis on transforme : List.map (fun x -> x*x) (List.filter (fun x -> x mod 2 = 0) l). Sur [1;2;3;4] : filter donne [2;4], puis map donne [4;16].List.fold_left — accumuler en un seul résultat
map et filter renvoient une liste. fold_left, elle, réduit toute la liste à une seule valeur (une somme, un maximum, une chaîne concaténée…). Elle promène un accumulateur de gauche à droite.
[a; b; c] :List.fold_left f acc [a; b; c] = f (f (f acc a) b) c.On part de
acc, on le combine avec a, puis le résultat avec b, puis avec c. L'accumulateur avance de la gauche vers la droite.let s = List.fold_left (+) 0 [1; 2; 3] (* somme : 6 *)
let m = List.fold_left max min_int [4; 9; 2] (* maximum : 9 *)
let n = List.fold_left (fun acc _ -> acc + 1) 0 [7; 7; 7] (* longueur : 3 *)List.fold_left (+) 0 [1;2;3](+) est l'addition vue comme une fonction à deux arguments. On calcule ((0+1)+2)+3 = 6. Le 0 est l'accumulateur de départ (élément neutre de l'addition).List.fold_left max min_int [4;9;2]max renvoie le plus grand de deux entiers ; en partant de min_int (plus petit entier possible), l'accumulateur retient le maximum rencontré : max (max (max min_int 4) 9) 2 = 9.fun acc _ -> acc + 1l'accumulateur compte les éléments ; _ ignore la valeur de l'élément (on ne s'intéresse qu'à sa présence). Résultat : la longueur, 3.fold_left reçoit (acc, elem) dans cet ordre : fun acc x -> .... Se tromper d'ordre est l'erreur la plus fréquente. Par exemple List.fold_left (fun acc x -> acc - x) 0 [1;2;3] vaut ((0-1)-2)-3 = -6 : c'est toujours l'accumulateur qui est « à gauche » de l'opération.| Étape | acc avant | x | Calcul acc*10 + x | acc après |
|---|---|---|---|---|
| départ | — | — | accumulateur initial | 0 |
| 1 | 0 | 1 | 0*10 + 1 | 1 |
| 2 | 1 | 2 | 1*10 + 2 | 12 |
| 3 | 12 | 3 | 12*10 + 3 | 123 ✓ |
Une somme réécrite par récursion (puis par fold)
Pour comprendre ce que fold_left fait « sous le capot », réécrivons une somme récursive à accumulateur — c'est exactement le schéma de fold_left spécialisé à l'addition.
let rec somme_acc acc l =
match l with
| [] -> acc
| x :: reste -> somme_acc (acc + x) reste
let somme l = somme_acc 0 l
(* somme [1;2;3] = 6 *)
(* la version « pro », en une ligne, avec fold_left : *)
let somme' l = List.fold_left (+) 0 llet rec somme_acc acc l =fonction récursive à accumulateur acc : il porte la somme partielle déjà calculée.| [] -> acccas de base : plus rien à ajouter, on renvoie la somme accumulée.| x :: reste -> somme_acc (acc + x) resteon ajoute la tête x à l'accumulateur, puis on continue sur le reste. C'est mot pour mot ce que fait fold_left (+) : combiner l'accumulateur avec l'élément courant, de gauche à droite.let somme' l = List.fold_left (+) 0 lmême comportement en une ligne : fold_left factorise ce schéma récursif une fois pour toutes.fold_left écrit ce squelette une seule fois ; il ne te reste qu'à fournir la fonction de combinaison et l'accumulateur initial. Moins de code, moins de bugs de récursion.fold_left, c'est le boss de fin de niveau. Une fois que tu sais reconstruire n'importe quel parcours de liste avec, tu tiens la moitié des exos d'info de MP2I. Nos mentors alumni X · Centrale · Mines t'entraînent sur les folds tordus des annales.
Trouver un mentor →Choisir le bon outil
- Le résultat est-il une liste ou une valeur unique ? Une valeur unique (nombre, booléen, chaîne) ⟶
fold_left. - Si c'est une liste : garde-t-on la même longueur ? Oui, on transforme chaque élément ⟶
map. Non, on en supprime ⟶filter. - Combinaison ? « les carrés des éléments pairs » =
filterpuismap. « la somme des carrés » =mappuisfold_left, ou directement un seulfold_left. - Vérifie la longueur attendue :
mapconserve,filterréduit (ou égale),fold_leftrenvoie une seule valeur.
Exercices corrigés
Donne la valeur de chacune de ces expressions.
let a = List.map (fun x -> x + 10) [0; 5; 9]
let b = List.filter (fun x -> x > 3) [1; 4; 2; 5]
let c = List.fold_left (+) 0 [4; 5; 6]Voir la correction détaillée
map ajoute 10 à chaque élément, en gardant l'ordre et la longueur : [10; 15; 19].filter garde les éléments strictement supérieurs à 3 : 1 non, 4 oui, 2 non, 5 oui ⟶ [4; 5].fold_left (+) 0 fait la somme : ((0+4)+5)+6 = 15.Écris toi-même, par récursion et filtrage, une fonction mon_filter p l équivalente à List.filter. Déroule ensuite mon_filter (fun x -> x > 2) [3; 1; 4].
Voir la correction détaillée
let rec mon_filter p l =
match l with
| [] -> []
| x :: reste ->
if p x
then x :: mon_filter p reste (* on garde x *)
else mon_filter p reste (* on jette x *)p x : si vrai, on le remet en tête (::) devant le résultat du reste ; si faux, on saute directement au reste sans le remettre. C'est ce « on remet ou pas » qui permet de raccourcir la liste.[3; 1; 4] avec p = (fun x -> x > 2) :
x=3:3 > 2vrai ⟶3 :: mon_filter p [1;4]x=1:1 > 2faux ⟶mon_filter p [4](on jette 1)x=4:4 > 2vrai ⟶4 :: mon_filter p [][]⟶[]
4 :: [] = [4], puis 3 :: [4] = [3; 4]. Résultat : [3; 4].On considère let renverse l = List.fold_left (fun acc x -> x :: acc) [] l. Explique pourquoi cette fonction renverse la liste, et donne la valeur de renverse [1; 2; 3].
Voir la correction détaillée
acc (la liste construite jusque-là) et l'élément courant x, et place x en tête : x :: acc. Comme fold_left traite les éléments de gauche à droite et que chaque nouvel élément passe devant les précédents, le premier élément de l finit tout au fond, et le dernier tout devant : l'ordre est inversé.[1; 2; 3], accumulateur initial [] :
x=1:1 :: [] = [1]x=2:2 :: [1] = [2; 1]x=3:3 :: [2; 1] = [3; 2; 1]
renverse [1; 2; 3] = [3; 2; 1].fun acc x (accumulateur d'abord). Écrire x :: acc renverse ; écrire acc @ [x] conserverait l'ordre mais serait bien plus lent ( à cause de @).Récap final — Ce qu'il faut absolument retenir
Une fonction est une valeur : on la passe, on la renvoie. Trois itérateurs suffisent à couvrir l'immense majorité des parcours de listes. Vérifie que tu peux répondre « oui » à tout ceci.
- Sais-tu écrire une fonction anonyme
fun x -> ...et la passer en argument ? - Sais-tu reconnaître une fonction d'ordre supérieur à son type (une flèche entre parenthèses dans un argument) ?
- Sais-tu que
List.mappréserve la longueur et transforme chaque élément ? - Sais-tu que
List.filterpeut réduire la longueur et ne modifie jamais les éléments ? - Sais-tu la règle
fold_left f acc [a;b;c] = f (f (f acc a) b) c? - Sais-tu que la fonction de
fold_leftreçoit l'accumulateur d'abord, l'élément ensuite ? - Sais-tu réécrire
mapet une somme (par fold) récursivement, par filtrage[]/x :: reste? - Sais-tu choisir entre
map,filteretfold_leftselon que le résultat est une liste (même taille / plus petite) ou une valeur unique ?