OCaml : programmation fonctionnelle, types et récursivité

OCaml est le second langage du programme MP2I. Il impose un style fonctionnel : on calcule des valeurs plutôt que de modifier des variables, le compilateur infère les types et vérifie l'exhaustivité des cas. Cette fiche fixe la syntaxe et les idées qui reviennent dans toutes les épreuves.

En OCaml, tout est expression et possède une valeur et un type. let x = 3 crée une liaison immuable ; let x = e in e' lie x uniquement dans e'. On ne « change » jamais x : une nouvelle liaison de même nom masque l'ancienne.

let carre x = x * x                   (* int -> int *)
let rec fact n = if n <= 1 then 1 else n * fact (n - 1)
let ajoute x y = x + y                (* int -> int -> int *)
let succ = ajoute 1                   (* application partielle : int -> int *)

• let rec est obligatoire pour qu'une fonction se voie elle-même ; and lie des fonctions mutuellement récursives.
• Le type int -> int -> int se lit int -> (int -> int) : toute fonction est curryfiée, d'où l'application partielle.
• fun x -> 2 x est une fonction anonyme ; un opérateur s'utilise comme fonction avec ( + ), ( ).
• if c then e1 else e2 est une expression : les deux branches ont le même type ; sans else, la branche vaut ().

Le compilateur infère le type de chaque expression ; une erreur de type bloque la compilation. Conséquences pratiques :

## Listes et filtrage par motif

Une liste est soit vide [], soit x :: q (tête x, queue q). Les listes sont immuables : x :: q crée un maillon en O(1) sans copier q. [1; 2; 3] abrège 1 :: 2 :: 3 :: [] ; @ concatène en O(longueur de gauche).

let rec longueur l = match l with
  | [] -> 0
  | _ :: q -> 1 + longueur q

let rec appartient x l = match l with
  | [] -> false
  | y :: q -> y = x || appartient x q

Le match compare la valeur aux motifs dans l'ordre ; _ capture n'importe quoi. Le compilateur signale un filtrage non exhaustif (risque de Match_failure) et les cas redondants.

Fonctions de la bibliothèque List à connaître : map, filter, fold_left, fold_right, exists, for_all, mem, rev, length, nth, assoc, iter.

• List.map f [x1; ...; xn] = [f x1; ...; f xn].
• List.fold_left f a [x1; x2; x3] = f (f (f a x1) x2) x3 (récursif terminal).
• List.fold_right f [x1; x2; x3] a = f x1 (f x2 (f x3 a)).

type forme = Cercle of float | Rectangle of float * float | Point
type 'a option = None | Some of 'a          (* prédéfini *)
type point = { x : float; mutable y : float } (* enregistrement *)
type arbre = Vide | Noeud of arbre * int * arbre

let rec hauteur a = match a with
  | Vide -> 0
  | Noeud (g, _, d) -> 1 + max (hauteur g) (hauteur d)

• Un type somme énumère des constructeurs, éventuellement porteurs de données ; on le déconstruit par match, ce qui garantit que tous les cas sont traités.
• 'a option remplace les valeurs sentinelles : une recherche renvoie None ou Some v.
• Les tuples (1, "a") ont un type produit int * string ; déconstruction let (a, b) = p.
• Un type récursif (listes, arbres) appelle une fonction récursive dont la structure suit celle du type : c'est l'induction structurelle.

Un appel est terminal s'il est la dernière opération : son résultat est renvoyé sans calcul supplémentaire. OCaml transforme un tel appel en saut, donc la pile ne grandit pas. x + somme q n'est pas terminal (l'addition reste à faire) ; sur une liste d'un million d'éléments, Stack_overflow guette.

let somme l =
  let rec aux acc l = match l with
    | [] -> acc
    | x :: q -> aux (acc + x) q   (* appel terminal *)
  in aux 0 l

La transformation passe par un accumulateur qui porte le résultat partiel. Pour une fonction qui construit une liste, on accumule à l'envers puis on applique List.rev (O(n)).

exception Vide
let tete l = match l with [] -> raise Vide | x :: _ -> x
let essai = try tete [] with Vide -> 0

raise lève une exception, try ... with la rattrape ; failwith "msg" lève Failure. Exceptions prédéfinies à reconnaître : Not_found (List.assoc, Hashtbl.find), Invalid_argument (indice hors bornes), Division_by_zero, Stack_overflow. Une exception peut aussi servir à sortir d'une boucle (raise Exit).

• let c = ref 0 crée une case mutable ; lecture !c, écriture c := !c + 1, raccourci incr c.
• Array.make n 0, accès t.(i) en O(1), modification t.(i) <- v, Array.length. Un indice invalide lève Invalid_argument.
• Boucles : for i = 0 to n - 1 do ... done, while cond do ... done, corps de type unit.
• Champ mutable d'un enregistrement : p.y <- 2.0.

1. 1Donner le type d'une expression avant de la calculer : c'est souvent demandé et cela détecte les erreurs (int vs float, oubli de rec).
2. 2Pour une fonction récursive, préciser le cas de base, l'appel récursif sur une structure strictement plus petite (terminaison) et l'hypothèse d'induction (correction).
3. 3Savoir transformer une récursion naïve en version terminale avec accumulateur et justifier l'intérêt (pile constante).
4. 4Préférer match à des if enchaînés sur les listes et les types somme : l'exhaustivité est vérifiée.
5. 5Connaître les coûts : :: et List.hd en O(1), List.nth, @, List.length en O(n), accès tableau en O(1).
6. 6Indiquer explicitement les parenthèses dans les match imbriqués et les arguments d'appel : la plupart des erreurs de syntaxe en viennent.