Le cours
Résumé en cinq points
- OCaml est typé statiquement avec inférence. Les fonctions sont curryfiées, éventuellement polymorphes et d'ordre supérieur. Portée lexicale, passage par valeur, mémoire automatique.
- Types de base :
int,floataux opérateurs pointés,boolà évaluation paresseuse,char,stringimmuable. Les entiers débordent sans prévenir. - Les données se construisent par n-uplets, listes immuables où
@coûte la longueur de la première liste, options et types somme récursifs, puis s'analysent par filtrage ordonné. - L'impératif passe par des expressions de type
unit: références, tableaux mutables à copie superficielle, séquence, boucleswhileetfor. - Les exceptions se lèvent par
raiseoufailwithet se rattrapent partry … with. Après rappel : enregistrements mutables, fonctions deListetArray,Stack,QueueetHashtbl.
Pourquoi ce chapitre
OCaml est l'un des deux langages de la filière, avec C. Il sert toute l'année pour les listes, les arbres, les graphes, les automates et la logique. Ce chapitre fixe le noyau exigible du langage. Le programme distingue deux niveaux. Ce qui relève de B.1 se maîtrise sans aide, même à l'écrit sans ordinateur. Ce qui relève de B.2 s'utilise après un rappel, avec la documentation fournie. Aux concours, on écrit de l'OCaml à la main, on donne le type de ses fonctions, on justifie leur terminaison et on évalue leur complexité.
Remarque de forme : cette fiche n'emploie jamais le point-virgule. Là où l'on écrirait e1, un point-virgule, puis e2, les codes utilisent l'équivalent let () = e1 in e2.
Fin de l'aperçu gratuit
Encore 13 parties de cours et 10 corrigés.
Méthodes et exercices
Exercices classiques corrigés
Rangés par thème, du plus simple au plus exigeant. Difficulté et durée indicatives.
Typage et portée 2
Exercice 1. Typer des expressions ★
Application du cours · 10 min · Khôlle
Donner le type de chaque expression, ou dire pourquoi elle est refusée.
-
fun f x -> f (f x) -
fun x y -> if x then y else 0 -
fun a -> (a, a) -
(fun a b -> a +. b) 1. -
fun x -> x + 1.
Voir l'indice
Technique poser des types inconnus et résoudre les contraintes.
Voir le corrigé offert
- f s'applique à x puis à f x : argument et résultat ont le même type. Type
('a -> 'a) -> 'a -> 'a. - x est testé, donc
bool. Les branches ont le type de 0. Typebool -> int -> int. - Rien ne contraint a. Type
'a -> 'a * 'a. +.imposefloat. Il restefloat -> float.- Refusé :
+attend deuxint, et1.est unfloat.
piège : Répondre ('a -> 'b) -> 'a -> 'b à la question 1. Le résultat de f repasse dans f, donc les types coïncident.
Exercice 2. Liaison ou contenu ★
Application du cours · 10 min · Khôlle
On évalue dans l'ordre les définitions suivantes.
let n = 5
let f x = x + n
let n = 100
let r = ref 1
let g x = x + !r
let () = r := 50
Que valent f 0 et g 0 ? Expliquer la différence.
Voir le début du corrigé
- f a été définie quand n valait 5. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Listes et filtrage 2
Exercice 3. Maximum d'une liste ★
Application du cours · 10 min · Khôlle
Écrire une fonction qui renvoie le plus grand élément d'une liste, ou None si elle est vide. Donner son type et son coût.
Voir le début du corrigé
- Idée : on calcule le maximum de la queue, puis on le compare à la tête.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 4. Supprimer les doublons consécutifs ★★
Classiques de khôlle et concours · 15 min · Khôlle
Écrire compresse, qui remplace chaque suite d'éléments égaux consécutifs par un seul exemplaire.
La liste 1, 1, 2, 2, 2, 1 devient 1, 2, 1.
Voir le début du corrigé
- Idée : si les deux premiers éléments sont égaux, on oublie le premier.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Arbres et types somme 2
Exercice 5. Hauteur et parcours infixe ★★
Classiques de khôlle et concours · 20 min · Niveau écrit CCINP
On reprend le type 'a arbre de la fiche. L'arbre vide a pour hauteur −1.
-
Écrire
hauteur. -
Écrire
infixe, liste des étiquettes dans l'ordre gauche, racine, droite, en temps linéaire. -
Pourquoi la version avec
@peut-elle être quadratique ?
Voir le début du corrigé
Videdonne −1, etNoeud (g, _, d)donne 1 plus le maximum des hauteurs de g et d, calculé par unif. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 6. Évaluer une expression arithmétique ★★
Classiques de khôlle et concours · 15 min · Niveau écrit CCINP
Déclarer un type d'expressions entières avec constantes, somme, produit et division.
Écrire eval, puis une version sûre qui renvoie None en cas de division par zéro.
Voir le début du corrigé
- Une branche par constructeur. La division entière lève déjà
Division_by_zero, on la rattrape une seule fois, à l'extérieur.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Récursivité et complexité 1
Exercice 7. Exponentiation rapide ★★
Classiques de khôlle et concours · 15 min · Khôlle
Écrire puissance x n, pour n ≥ 0, avec O(log n) multiplications.
Prouver terminaison et correction.
Que se passe-t-il pour 3 puissance 40 ?
Voir le début du corrigé
- Idée : avec n = 2q + r et r reste de n par 2, x puissance n vaut (x puissance q)² fois x puissance r.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Programmation impérative 3
Exercice 8. Recherche dichotomique impérative ★★
Classiques de khôlle et concours · 20 min · Niveau écrit CCINP
Dans un tableau d'entiers trié par ordre croissant, renvoyer un indice où se trouve x, ou lever Not_found.
Donner un invariant, un variant et le coût.
Voir le début du corrigé
- Idée : on maintient une zone d'indices g à d hors de laquelle x ne peut pas être, et on la coupe en deux.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 9. Triangle de Pascal ★★
Classiques de khôlle et concours · 15 min · Khôlle, après rappel
On rappelle que Array.init n f crée le tableau des f i pour i de 0 à n − 1.
-
Construire le triangle de Pascal jusqu'à la ligne n, la ligne i ayant i + 1 cases.
-
Pourquoi
Array.make (n + 1) (Array.make (n + 1) 1)ne convient pas ?
Voir le début du corrigé
- Chaque ligne est créée à part, remplie de 1, puis les cases intérieures suivent la relation de Pascal.
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Exercice 10. Compter les occurrences ★★
Classiques de khôlle et concours · 20 min · Niveau écrit Mines, après rappel
On rappelle les fonctions create, add, remove, find_opt et iter du module Hashtbl.
-
Construire une table qui associe à chaque élément d'une liste son nombre d'occurrences.
-
En déduire l'élément le plus fréquent d'une liste non vide.
Voir le début du corrigé
- Pour chaque élément, on lit son compte. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Ordre supérieur 1
Exercice 11. Réduire une liste ★★★
Approfondissement · 20 min · Type oral Centrale
On définit la fonction suivante.
let rec reduire f acc l = match l with
| [] -> acc
| x :: q -> reduire f (f acc x) q
-
Inférer son type en justifiant.
-
Exprimer longueur, somme et miroir avec
reduire, sans autre récursion. -
Montrer que
reduire f a ltermine et fait n appels de f.
Voir le début du corrigé
- Notons a le type de acc et b celui des éléments. …
La suite du corrigé dans Sup et Spé+ : essai gratuit 7 jours.
Fiche rédigée à partir du programme officiel de MP2I (2021), informatique, annexe B « Langage OCaml », sous-sections B.1 « Traits et éléments techniques à connaître » et B.2 « Éléments techniques devant être reconnus et utilisables après rappel ».