Langage OCaml en MP2I : cours, méthodes et exercices corrigés

Q: Quelle différence entre = et == en OCaml ?

`=` est l'égalité structurelle : elle compare deux valeurs du même type, composante par composante pour les listes et les n-uplets, et `[1; 2] = [1; 2]` vaut `true`. `==` est l'égalité physique : elle teste si les deux valeurs sont le même objet en mémoire, et `[1; 2] == [1; 2]` vaut `false`, car les deux listes sont construites séparément. `==` n'est pas dans l'annexe du programme : on compare toujours avec `=` et `<>`. Venant de Python, `==` s'écrit `=` et `!=` s'écrit `<>`.

Q: Pourquoi 1 + 2.5 est refusé en OCaml ?

`+` additionne deux entiers, et `2.5` est un flottant : OCaml ne convertit jamais seul, et répond `The constant "2.5" has type "float" but an expression was expected of type "int"`. Les flottants ont leurs opérateurs pointés, `+.`, `-.`, `*.`, `/.`, et des constantes du même type : `1. +. 2.5` vaut `3.5`. Un entier se convertit par `float_of_int` : `float_of_int total /. float_of_int n` donne une moyenne avec ses décimales, alors que `total / n` tronque. `` ne s'applique qu'aux flottants, et le reste s'écrit `mod`.

Q: Comment écrire une fonction récursive sur une liste en OCaml ?

On déclare la fonction avec `let rec`, puis on filtre les deux formes d'une liste, `[]` et `x :: reste` : `let rec longueur l = match l with | [] -> 0 | _ :: reste -> 1 + longueur reste`. On écrit d'abord la réponse pour la liste vide, puis le cas `x :: reste` en supposant connu le résultat sur `reste`. Chaque appel porte sur la queue, plus courte d'un élément : on atteint la liste vide, avec un appel par élément. Sans `rec`, OCaml répond `Unbound value`, car le nom n'existe pas encore dans le corps de sa propre définition.

Q: Que veut dire Warning 8 this pattern-matching is not exhaustive en OCaml ?

Un cas possible n'est couvert par aucun motif du `match`. OCaml compile quand même et donne un exemple de cas oublié, souvent `[]` ; si ce cas se présente, l'exécution s'arrête sur l'exception `Match_failure`. Tout filtrage doit être exhaustif : un cas que la spécification interdit se traite quand même, par exemple `| [] -> failwith "tete : liste vide"`. Les motifs sont essayés dans l'ordre, du plus particulier au plus général : `[x]` avant `_ :: reste`, sinon l'avertissement 11 signale une branche jamais utilisée.

Q: Quelle différence entre une liste et un tableau en OCaml ?

Une liste (`[1; 2; 3]`, de type `'a list`) est immuable : `x :: l` construit une nouvelle liste en temps constant, et on la parcourt par filtrage ; atteindre le i-ième élément demande de parcourir i maillons. Un tableau (`[|1; 2; 3|]`, de type `'a array`) est mutable et de taille fixe : on lit `t.(i)` et on écrit `t.(i) <- v` en temps constant, et on le parcourt avec une boucle `for`. Construction et parcours de bout en bout : une liste ; beaucoup d'accès par indice ou de modifications : un tableau. La consigne du sujet passe avant : style imposé, fonctions interdites.

MP2I
Offert à l'essai

Expressions et types d'OCaml, liaisons let, fonctions et application partielle, types somme et produit, filtrage, listes et récursivité ; traits impératifs : séquence, références, boucles, tableaux, enregistrements mutables, exceptions ; premiers programmes complets en OCaml.

18méthodes
33exercices corrigés
4problèmes
25pièges
36figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

OCaml est le langage fonctionnel de l'option informatique : on y décrit des valeurs et des fonctions plutôt que des suites d'instructions, et OCaml vérifie les types avant toute exécution, sans jamais convertir seul un entier en flottant (typage statique et fort). En MP2I, il faut savoir prévoir le type d'une expression, écrire des fonctions avec let et let rec, appliquer une fonction partiellement, parcourir une liste par filtrage avec match en couvrant tous les cas, puis passer au style impératif avec des références, des boucles et des tableaux. Le chapitre couvre l'annexe B.1 du programme et la partie de B.2 utile au premier semestre ; il ne suppose aucune connaissance d'OCaml. Les sujets de CCINP, de Mines-Ponts, de Centrale-Supélec et de X-ENS posent des questions de ce niveau, reprises dans les exercices. Tu y trouves un cours d'OCaml pas à pas, la récursivité sur les listes, le coût des opérations, et des exercices OCaml corrigés avec les réponses de la boucle interactive.

Ce que tu sauras faire

OCaml est le langage fonctionnel du programme : on y décrit des valeurs et des fonctions plutôt que des suites d'instructions, et le compilateur vérifie les types avant toute exécution. Ce chapitre présente tout le langage de l'annexe B.1 du programme et la partie de B.2 utile au premier semestre, dans l'ordre où l'on s'en sert ; les piles, files, tables de hachage, fichiers et fils d'exécution de B.2 viennent avec les chapitres qui les étudient. À la fin, tu dois savoir :

prévoir le type et la valeur d'une expression, et lire un message d'erreur d'OCaml ;
calculer avec des entiers, des flottants, des booléens, des caractères et des chaînes sans mélanger les types ;
nommer des valeurs, écrire des fonctions à plusieurs arguments, appliquer une fonction partiellement, passer une fonction en argument ;
écrire une fonction récursive sur un entier ou sur une liste, et connaître le coût des opérations sur les listes ;
filtrer une valeur avec des motifs exhaustifs et bien ordonnés ;
déclarer des types sommes, des types récursifs, des enregistrements, et utiliser 'a option ;
programmer en style impératif : séquence, références, boucles, tableaux ;
distinguer les valeurs mutables des valeurs immuables, et lever ou rattraper une exception.

L'essentiel : Expressions et types Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Le principe

Tout est expression : une valeur et un type, connus avant l'exécution (typage statique). Aucune conversion implicite (typage fort). La boucle interactive répond - : int = 7 pour une expression, val x : int = 7 pour une déclaration.

type	valeurs	opérateurs
`int`	`7`, `-3`, `max_int`	`+ - * / mod` ; `/` tronque vers zéro
`float`	`2.`, `3.14`, `1e-3`	`+. -. . /.` ; `*` (B.2)
`bool`	`true`, `false`	`not`, `&&`, `\|\|` (paresseux)
`char`	`'a'`	comparaisons
`string`	`"abc"`	`^`, `s.[i]`, `String.length` ; immuable
`unit`	`()`	valeur des actions

Comparaisons = <> < > <= >= entre deux valeurs du même type ; pas de == (égalité physique, hors annexe). Sur un type somme, la comparaison polymorphe range les constructeurs sans argument avant ceux avec argument : on écrit sa propre comparaison.
(-7) / 2 vaut $-3$ , (-7) mod 2 vaut $-1$ ; max_int + 1 = min_int, sans erreur.
Conversions (B.2) : float_of_int, int_of_float (tronque), string_of_int.
Flottants comparés avec une tolérance : x -. y < eps && y -. x < eps.

Une méthode du chapitre Extrait gratuit

Méthode Écrire une fonction récursive sur une liste par filtrage

Quand l’utiliser

L'énoncé demande une fonction sur une liste, souvent « récursive » : compter, chercher, transformer, extraire.

Rappel de cours

Une liste est [] ou x :: reste : on filtre ces deux cas, et le cas x :: reste appelle la fonction sur reste, plus courte d'un élément. Au besoin, on filtre aussi [x] (un seul élément) ou x :: y :: reste (deux têtes). Deux listes se filtrent ensemble par un couple : match u, v with.

Démarche

Écrire la signature et ce que vaut la fonction sur la liste vide.
Écrire le cas x :: reste en supposant connu le résultat sur reste.
Ajouter un motif particulier ([x], deux têtes) si la réponse en a besoin, avant le motif général.
Dérouler sur une liste de deux ou trois éléments.

Rédaction type

let rec f l =
  match l with
  | [] -> (* réponse pour la liste vide *)
  | x :: reste -> (* utilise x et f reste *)

« Chaque appel porte sur la queue de la liste, plus courte d'un élément : on atteint la liste vide. Un appel par élément : coût linéaire si le reste du calcul est en temps constant. »

Exemple traité

Nombre de caisses d'une variété dans le registre :

(* compte_variete : variete -> livraison list -> int
   nombre de caisses de la variété v *)
let rec compte_variete v registre =
  match registre with
  | [] -> 0
  | c :: reste ->
    if c.variete = v then 1 + compte_variete v reste
    else compte_variete v reste

let n = (compte_variete Majhoul registre,
         compte_variete Jihel registre)

La boucle interactive répond :

val compte_variete : variete -> livraison list -> int = <fun>
val n : int * int = (2, 1)

Le registre contient deux caisses de Majhoul et une de Jihel. Un appel par caisse : le coût est linéaire.

Erreurs fréquentes

Oublier le cas [] : avertissement 8, puis Match_failure.
Appeler la fonction sur l au lieu de reste : récursion sans fin.
Écrire l.(i) ou l[i] sur une liste : les correcteurs de X-ENS (rapport 2023, MP et MPI, informatique A) relèvent des candidats qui écrivent « l[i] avec l une liste », opérations « souvent considérées comme étant en temps constant ».

Pour s’entraîner

Exercices 4, 6, 7, 8, 9, 10, 16, 18, 20, 21, 29, 30, 31 et 33, problèmes 1 et 3.

Un exercice corrigé Extrait gratuit

Exercice Comparer des mots sur deux lettres ★☆☆

On fixe l'alphabet $\Sigma = \{a, b\}$ , ordonné par $a < b$ . Les mots sur $\Sigma$ sont rangés dans l'ordre lexicographique, celui du dictionnaire : on compare les premières lettres, puis, si elles sont égales, les suivantes ; un mot précède tous ses prolongements, et le mot vide précède tous les autres. Le sujet adopte les types suivants.

type letter = A | B
type word = letter list

Q1. Écrire une fonction cmp_letter (x1:letter) (x2:letter) : int qui renvoie 0 si les lettres $x_1$ et $x_2$ sont égales, un entier strictement négatif si $x_1$ précède strictement $x_2$ , et un entier strictement positif sinon.

Q2. Écrire une fonction cmp_word (w1:word) (w2:word) : int qui renvoie 0 si les mots $w_1$ et $w_2$ sont égaux, un entier strictement négatif si $w_1$ précède strictement $w_2$ , et un entier strictement positif sinon. Le sujet interdit la fonction de comparaison List.compare du module List et toute approche semblable, ce qui exclut aussi la comparaison générale compare.

Indications

Q1, méthode 12 : on filtre le couple x1, x2 ; il y a quatre cas.
Q2, méthode 6 : on filtre les deux listes à la fois avec match w1, w2 with : vide et vide, vide et non vide, non vide et vide, deux mots non vides.

Analyse : comment trouver l’idée

Comparer deux mots, c'est comparer leurs premières lettres ; si elles diffèrent, la réponse est celle de cmp_letter ; sinon, on compare les deux suites. Quand un mot est épuisé avant l'autre, c'est un préfixe de l'autre, donc le plus petit. Sur [A; B] et [A; B; A], les deux premières lettres sont égales, puis le premier mot est vide : il précède le second.

Correction détaillée

(* cmp_letter : letter -> letter -> int
   -1, 0 ou 1 selon que x1 précède x2, lui est égale
   ou le suit *)
let cmp_letter (x1:letter) (x2:letter) : int =
  match x1, x2 with
  | A, A -> 0
  | B, B -> 0
  | A, B -> -1
  | B, A -> 1

(* cmp_word : word -> word -> int
   -1, 0 ou 1 selon que w1 précède w2, lui est égal
   ou le suit dans l'ordre lexicographique *)
let rec cmp_word (w1:word) (w2:word) : int =
  match w1, w2 with
  | [], [] -> 0
  | [], _ :: _ -> -1
  | _ :: _, [] -> 1
  | x1 :: r1, x2 :: r2 ->
    let c = cmp_letter x1 x2 in
    if c <> 0 then c else cmp_word r1 r2

Les quatre cas de chaque filtrage couvrent toutes les possibilités : OCaml n'émet aucun avertissement. La fonction cmp_word s'arrête, car la longueur de w1 diminue de 1 à chaque appel ; elle fait au plus $\min(\lvert w_1 \rvert, \lvert w_2 \rvert) + 1$ appels.

Expression	Type	Valeur
`cmp_word [A; B] [A; B; A]`	`int`	`-1`
`cmp_word [B] [A; B; B]`	`int`	`1`
`cmp_word [A; A] [A; B]`	`int`	`-1`
`cmp_word [] []`	`int`	`0`

Méthodes à retenir

Pour parcourir deux listes en même temps, on filtre le couple : un cas par combinaison de formes, sans en oublier. La comparaison lexicographique s'arrête à la première différence. Voir les méthodes 6 et 12.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 18 méthodes, 25 pièges corrigés, la carte mentale, 33 exercices corrigés, 4 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit Une question ? WhatsApp

Plan du cours

Partie A. Le cœur fonctionnel
- 1. Premiers pas
- 1. Types de base
- 1. Nommer des valeurs
- 1. Fonctions
- 1. L'expression conditionnelle
- 1. Récursivité
- 1. N-uplets
- 1. Listes
- 1. Filtrage
- 1. Déclarer des types
- 1. Fonctions d'ordre supérieur sur les listes
Partie B. Les traits impératifs
- 12. Effets, unit et séquence
- 1. Références
- 1. Boucles
- 1. Tableaux
- 1. Mutable et immuable
- 1. Exceptions
- 1. Modules et programme complet

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

Prévoir le type et la valeur d'une expression
Lire un message d'OCaml et corriger le code
Calculer sans mélanger entiers et flottants
Écrire une fonction récursive sur un entier
Utiliser une fonction d'ordre supérieur et l'application partielle
Écrire une fonction récursive sur une liste par filtrage
Rendre un filtrage exhaustif et ordonner les motifs
Comparer à une valeur dans un filtrage
Construire une liste résultat
Utiliser un accumulateur quand il change le coût
Renvoyer plusieurs résultats
Déclarer un type somme et écrire les fonctions qui le filtrent
Utiliser 'a option pour un résultat qui peut manquer
Parcourir un tableau avec une boucle, et s'arrêter tôt
Créer une matrice sans alias et copier un tableau
Lever, rattraper et utiliser une exception
Choisir entre liste et tableau, fonctionnel et impératif
Écrire du code OCaml sur la copie

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Type, valeur ou erreur
Parenthèses et priorité de l'application
Portée, masquage et définitions simultanées
La signature d'une fonction mystère
Premières fonctions récursives sur les entiers
Des chaînes aux listes
Palindrome et doublons
Comparer des mots sur deux lettres
Retirer des éléments, extraire des clés
Le maximum d'un tableau, la plus petite arête
Compter les occurrences dans un tableau
Un chemin de cailloux
Références : échanger, accumuler

Entraînement (15)

Inférer le type de huit fonctions
Curryfier, décurryfier, itérer
Rang, préfixe, intervalle
De quadratique à linéaire
Associer, séparer, partager
Chercher sans être sûr de trouver
Comparer, décrémenter, Havel-Hakimi
Des boîtes et des objets
Un graphe dans un tableau de listes
Clauses et compteur binaire
Fractions et chemins
Une grille de pixels à deviner
Appartenance et sous-chaîne sans la bibliothèque
Occurrence et période d'un mot
Exceptions : somme des inverses, première occurrence

Approfondissement (5)

Expressions arithmétiques
Un dictionnaire de mots en arbre
Insérer dans un tableau de Young
Égalité, ordre et partage
Produit cartésien, préfixes, sous-listes

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Sélectionner un élément sans trier toute la liste
CCINP 2023, filière MP, option informatique, partie I, questions 1 à 8, complétées
Vérifier qu'une relation est une relation d'ordre
Mines-Ponts 2024, filière MP, option informatique, questions 1 à 7
La suite de Prouhet-Thue-Morse
CCINP 2026, filière MPI, informatique, partie II, questions 23 à 25, 29, 31, 32, 34 et 35
Des listes infinies sans débordement de pile
Mines-Ponts 2024, filière MPI, informatique 2, questions 1 à 5 et 7 à 11

Questions fréquentes

Quelle différence entre = et == en OCaml ?

= est l'égalité structurelle : elle compare deux valeurs du même type, composante par composante pour les listes et les n-uplets, et [1; 2] = [1; 2] vaut true. == est l'égalité physique : elle teste si les deux valeurs sont le même objet en mémoire, et [1; 2] == [1; 2] vaut false, car les deux listes sont construites séparément. == n'est pas dans l'annexe du programme : on compare toujours avec = et <>. Venant de Python, == s'écrit = et != s'écrit <>.

Pourquoi 1 + 2.5 est refusé en OCaml ?

+ additionne deux entiers, et 2.5 est un flottant : OCaml ne convertit jamais seul, et répond The constant "2.5" has type "float" but an expression was expected of type "int". Les flottants ont leurs opérateurs pointés, +., -., *., /., et des constantes du même type : 1. +. 2.5 vaut 3.5. Un entier se convertit par float_of_int : float_of_int total /. float_of_int n donne une moyenne avec ses décimales, alors que total / n tronque. ** ne s'applique qu'aux flottants, et le reste s'écrit mod.

Comment écrire une fonction récursive sur une liste en OCaml ?

On déclare la fonction avec let rec, puis on filtre les deux formes d'une liste, [] et x :: reste : let rec longueur l = match l with | [] -> 0 | _ :: reste -> 1 + longueur reste. On écrit d'abord la réponse pour la liste vide, puis le cas x :: reste en supposant connu le résultat sur reste. Chaque appel porte sur la queue, plus courte d'un élément : on atteint la liste vide, avec un appel par élément. Sans rec, OCaml répond Unbound value, car le nom n'existe pas encore dans le corps de sa propre définition.

Que veut dire Warning 8 this pattern-matching is not exhaustive en OCaml ?

Un cas possible n'est couvert par aucun motif du match. OCaml compile quand même et donne un exemple de cas oublié, souvent [] ; si ce cas se présente, l'exécution s'arrête sur l'exception Match_failure. Tout filtrage doit être exhaustif : un cas que la spécification interdit se traite quand même, par exemple | [] -> failwith "tete : liste vide". Les motifs sont essayés dans l'ordre, du plus particulier au plus général : [x] avant _ :: reste, sinon l'avertissement 11 signale une branche jamais utilisée.

Qu'est-ce que la curryfication et l'application partielle en OCaml ?

Une fonction à deux arguments s'écrit avec deux paramètres séparés par des espaces : let prix_caisse prix_kg poids_g = prix_kg * poids_g / 1000 a le type int -> int -> int, qui se lit int -> (int -> int). Elle reçoit un entier et renvoie une fonction qui attend le second : on dit qu'elle est curryfiée. prix_caisse 90 est donc une application partielle, de type int -> int, et List.map (prix_caisse 90) [12500; 9750] vaut [1125; 877]. Une virgule fabrique un n-uplet : on écrit min 3 5, et non min (3, 5).

Quelle différence entre une liste et un tableau en OCaml ?

Une liste ([1; 2; 3], de type 'a list) est immuable : x :: l construit une nouvelle liste en temps constant, et on la parcourt par filtrage ; atteindre le $i$ -ième élément demande de parcourir $i$ maillons. Un tableau ([|1; 2; 3|], de type 'a array) est mutable et de taille fixe : on lit t.(i) et on écrit t.(i) <- v en temps constant, et on le parcourt avec une boucle for. Construction et parcours de bout en bout : une liste ; beaucoup d'accès par indice ou de modifications : un tableau. La consigne du sujet passe avant : style imposé, fonctions interdites.

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.