En OCaml, une fonction s'écrit à partir de son type. Le type de la donnée donne les cas du filtrage (le match qui examine sa forme), et chaque cas qui contient une donnée du même type rappelle la fonction sur ce morceau plus petit. Une liste est soit vide, [], soit une tête suivie d'une queue, x :: q : pour savoir si x apparaît dans l, il y a donc deux cas.
let rec appartient x l = match l with
| [] -> false
| y :: q -> y = x || appartient x q
OCaml en déduit seul le type 'a -> 'a list -> bool : un élément d'un type quelconque 'a, une liste d'éléments de ce type, un booléen en sortie. Ce cours t'entraîne à faire ce chemin dans les deux sens, du type vers le code et du code vers le type, sans machine.
Objectifs du cours :
- Donner le type d'une fonction OCaml en lisant son code, sans ordinateur.
- Écrire un filtrage complet et bien ordonné sur un type somme : liste, option, arbre, expression.
- Écrire une fonction récursive sur les listes et les arbres, et justifier son coût.
Prérequis : avoir écrit quelques fonctions OCaml avec let et let rec, et savoir ce qu'est une fonction récursive.
I. Lire le type d'une fonction
OCaml vérifie les types avant toute exécution (typage statique) et les trouve seul (inférence). Le programme te demande d'« inférer un type à la lecture d'un fragment de code » et de manier les bases du langage même sans ordinateur (programme d'informatique MP2I-MPI, 2021).
Règle : la flèche s'associe à droite : int -> int -> int signifie int -> (int -> int). Une fonction « à deux arguments » prend le premier et renvoie une fonction qui attend le second : on dit qu'elle est curryfiée.
Conséquence directe : avec let ajoute x y = x + y, l'expression ajoute 1 est déjà une fonction, de type int -> int. Une fonction peut aussi recevoir une fonction en argument, on parle alors de fonction d'ordre supérieur. Lis celle-ci :
let compose f g x = f (g x)
Trois arguments. x ne sert qu'à travers g : rien ne contraint son type, appelle-le 'c. g prend un 'c et rend un type encore inconnu, 'a. f prend ce 'a et rend un 'b, qui est le résultat. Bilan : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b, exactement ce qu'affiche OCaml. Ces 'a, 'b, 'c sont des variables de type : compose marche pour tous les types, c'est le polymorphisme.
Les opérateurs fixent les types de base : + impose int, +. impose float, ^ impose string, || impose bool. Une comparaison = impose seulement que ses deux côtés aient le même type.
Piège classique : l'application d'une fonction passe avant tous les opérateurs (manuel OCaml, « Expressions »). f n - 1 se lit (f n) - 1, et f x :: q se lit (f x) :: q. Pour appeler f sur n - 1, écris f (n - 1) : sans les parenthèses, une fonction récursive se rappelle sur le même argument et ne termine jamais.
Exercice 1 : Donne, sans machine, le type de chacune de ces trois fonctions.
let f b n = if b then n + 1 else n
let g h = h 2 = 4
let double_tete x l = x :: x :: l
Correction :
f : bool -> int -> int. b sert de condition, c'est donc un booléen ; n + 1 impose int, et les deux branches du if ont le même type.
g : (int -> int) -> bool. L'application passe avant =, le corps se lit (h 2) = 4 : h va des entiers dans les entiers, et le résultat est un booléen.
double_tete : 'a -> 'a list -> 'a list. :: attend un élément à gauche et une liste du même type à droite ; rien d'autre ne contraint x.
II. Types somme et filtrage
Un type somme décrit une donnée qui prend une forme parmi plusieurs. Chaque forme a son constructeur, qui commence par une majuscule et peut porter des valeurs. Avec match, tu écris un cas par constructeur, introduit par un motif (la forme attendue, écrite après la barre |), et la récursion suit le type : là où un constructeur contient une donnée du même type, la fonction se rappelle.
type expr =
| Const of int
| Add of expr * expr
| Mul of expr * expr
let rec eval e = match e with
| Const n -> n
| Add (a, b) -> eval a + eval b
| Mul (a, b) -> eval a * eval b
Ainsi eval (Add (Const 2, Mul (Const 3, Const 4))) vaut $2 + 3 \times 4 = 14$, et eval a pour type expr -> int.
Une valeur du type prédéfini 'a option est None ou Some v. Il sert quand une fonction peut ne rien avoir à renvoyer :
let rec dernier l = match l with
| [] -> None
| [x] -> Some x
| _ :: q -> dernier q
Ici l'ordre compte. OCaml essaie les motifs de haut en bas et retient le premier qui filtre la valeur (manuel OCaml, « Expressions »). Or _ :: q filtre aussi une liste à un seul élément : écrit avant [x], il prendrait tous ces cas, et dernier renverrait toujours None. Le motif le plus particulier passe donc en premier. Un constructeur oublié déclenche à la compilation un avertissement de filtrage non exhaustif ; sur papier, personne ne t'avertit : compte tes cas.
Piège classique : une variable dans un motif ne compare rien : elle filtre n'importe quelle valeur et lui donne un nom (manuel OCaml, « Patterns »). Dans let rec compte x l = match l with [] -> 0 | x :: q -> 1 + compte x q | _ :: q -> compte x q, le x du motif cache l'argument : compte renvoie la longueur de la liste et le dernier cas ne sert jamais. Le programme exclut d'ailleurs les motifs qui réutilisent une variable déjà définie. Nomme la tête autrement, puis compare : | y :: q -> if y = x then 1 + compte x q else compte x q.
III. Listes : récursion et coût de la concaténation
x :: q pose une seule cellule (un maillon qui contient x et pointe vers q) devant q, sans recopier q : son coût est constant. La concaténation l0 @ l1 est d'une autre nature. Une liste ne s'atteint que par sa tête : pour accrocher l1 derrière l0, il faut refaire chaque cellule de l0, selon les deux égalités [] @ l1 = l1 et (x :: q) @ l1 = x :: (q @ l1).
Propriété : l0 @ l1 coûte un temps proportionnel à la longueur de l0, quelle que soit celle de l1. Le programme demande de connaître @ « y compris sa complexité ».
Ce coût se cache dans des fonctions d'allure innocente, comme celle qui renverse une liste en recollant la tête à la fin :
let rec renverser l = match l with
| [] -> []
| x :: q -> renverser q @ [x]
L'appel sur une liste de longueur $k$ fait un @ dont la partie gauche compte $k-1$ éléments. Pour une liste de longueur $n$, cela fait $0 + 1 + \dots + (n-1) = \frac{n(n-1)}{2}$ cellules recopiées : le coût est quadratique, soit $499\,500$ cellules pour $n = 1000$.
Un accumulateur, c'est-à-dire un argument qui porte le résultat en construction, ramène ce coût à une étape par élément :
let renverser_acc l =
let rec aux l acc = match l with
| [] -> acc
| x :: q -> aux q (x :: acc)
in
aux l []
Sur [1; 2; 3], les appels donnent aux [2; 3] [1], puis aux [3] [2; 1], puis aux [] [3; 2; 1] : un seul :: par élément. L'accumulateur se remplit par la tête, donc à l'envers, et c'est ici le but.
Piège classique : :: attend un élément à gauche et une liste à droite. Pour ajouter un élément x à la fin de q, ni q :: x ni q @ x ne passent le typage : il faut q @ [x], qui coûte la longueur de q. Répété à chaque appel récursif, ce coût devient quadratique.
Exercice 2 : Écris supprime x l, qui renvoie la liste l privée de toutes les occurrences de x, dans le même ordre. Donne son type, son coût, et calcule supprime 3 [3; 1; 3; 2].
Correction :
let rec supprime x l = match l with
| [] -> []
| y :: q -> if y = x then supprime x q else y :: supprime x q
Deux cas, comme le type liste, et la tête s'appelle y pour pouvoir la comparer à x. Type : 'a -> 'a list -> 'a list. Sur l'exemple, le premier 3 saute, 1 est gardé, le second 3 saute, 2 est gardé : le résultat est [1; 2]. Chaque élément est examiné une fois et chaque :: coûte une étape : le coût est linéaire en la longueur de l.
IV. Arbres binaires
Un arbre binaire est vide, ou bien c'est un nœud qui porte une étiquette et deux sous-arbres. Cette phrase se recopie en type, rendu polymorphe par le paramètre 'a :
type 'a arbre =
| Vide
| Noeud of 'a arbre * 'a * 'a arbre
Deux constructeurs, donc deux cas ; deux sous-arbres, donc deux appels récursifs :
let rec taille a = match a with
| Vide -> 0
| Noeud (g, _, d) -> 1 + taille g + taille d
let rec hauteur a = match a with
| Vide -> -1
| Noeud (g, _, d) -> 1 + max (hauteur g) (hauteur d)
Définition : une feuille est un nœud dont les deux sous-arbres sont vides. La hauteur d'un arbre non vide est le nombre d'arêtes du plus long chemin qui descend de la racine à une feuille. Le programme fixe la hauteur de l'arbre vide à $-1$ : une feuille seule est donc de hauteur $0$. Si un livre suit une autre convention, garde celle du programme.
Avec t = Noeud (Noeud (Vide, 2, Vide), 5, Noeud (Noeud (Vide, 7, Vide), 8, Vide)), les feuilles 2 et 7 sont de hauteur $0$, le nœud 8 de hauteur $1 + \max(0, -1) = 1$ et la racine de hauteur $1 + \max(0, 1) = 2$ ; taille t vaut 4.
Cette convention donne une borne nette, qui se prouve par induction structurelle : on vérifie la propriété pour Vide, puis pour Noeud (g, x, d) en la supposant vraie pour g et d.
Notons $h(a)$ la hauteur de $a$ et montrons que $\text{taille}(a) \le 2^{h(a)+1} - 1$. Pour Vide, $h = -1$ et $0 \le 2^{0} - 1 = 0$. Pour $a$ de la forme Noeud (g, x, d) et de hauteur $h$, on a $h(g) \le h - 1$ et $h(d) \le h - 1$, donc $\text{taille}(a) = 1 + \text{taille}(g) + \text{taille}(d) \le 1 + 2\,(2^{h} - 1) = 2^{h+1} - 1$.
Exercice 3 : Écris feuilles : 'a arbre -> int, qui compte les feuilles d'un arbre. Vérifie ta fonction sur t, puis dis ce qui se passe si l'on échange ses deux derniers cas.
Correction :
let rec feuilles a = match a with
| Vide -> 0
| Noeud (Vide, _, Vide) -> 1
| Noeud (g, _, d) -> feuilles g + feuilles d
Sur t, la racine n'est pas une feuille : on additionne. À gauche, la feuille 2 compte 1. À droite, le nœud 8 n'est pas une feuille et donne $1 + 0$ (la feuille 7, puis l'arbre vide). Total : 2.
Si l'on échange les deux derniers cas, Noeud (g, _, d) filtre aussi les feuilles, qui valent alors $0 + 0$ : la fonction renvoie toujours 0, et le compilateur signale le cas Noeud (Vide, _, Vide) comme inutile.
À retenir
| Type | Cas du filtrage |
|---|---|
'a list | [] et x :: q |
'a option | None et Some v |
'a arbre | Vide et Noeud (g, x, d) |
expr | Const n, Add (a, b) et Mul (a, b) |
À retenir :
- Un type se lit flèche par flèche, en associant à droite ; l'application d'une fonction passe avant tous les opérateurs.
- Un type somme donne la liste des cas ; les motifs sont essayés de haut en bas, le plus particulier d'abord, et une variable de motif ne compare jamais.
x :: qcoûte une étape,l0 @ l1coûte la longueur del0; un accumulateur évite le coût quadratique.
Sources
- Ministère de l'Enseignement supérieur, programmes d'informatique MP2I et MPI (2021), annexe B « Langage OCaml » et partie 3 « Structures de données ».
- Manuel de référence d'OCaml, chapitres « Expressions » et « Patterns ».