Enregistrements et types mutuellement récursifs

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>7.1 Introduction et motivation

Le chapitre 3 a montré les types sommes : une valeur est l'une de plusieurs formes. Il manque leur complément, les types produits nommés : une valeur qui regroupe plusieurs champs à la fois — un point a une abscisse et une ordonnée, un étudiant a un nom et une note. Le n-uplet (chapitre 1) le faisait déjà, mais par position : dans (0.0, 1.0), lequel est l'abscisse ? L'enregistrement répond en nommant les champs.

Ce chapitre présente les enregistrements (immuables et mutables), puis les types mutuellement récursifs (déclarés ensemble avec and), qui permettent de modéliser des structures où deux notions se renvoient l'une à l'autre — un arbre et la forêt de ses sous-arbres, un système de fichiers et son contenu. Tout cela relève du niveau A.2 (utilisable après rappel).

7.2 Les enregistrements

Un enregistrement (record) regroupe plusieurs valeurs, chacune désignée par un nom de champ.

type point = { x : float; y : float }

let origine = { x = 0.0; y = 0.0 }
let abscisse p = p.x

# let p = { x = 3.0; y = 4.0 };;
val p : point = {x = 3.; y = 4.}
# p.x;;
- : float = 3.

let translate_x p dx = { p with x = p.x +. dx }

7.3 Champs mutables

Par défaut, un enregistrement est immuable. On peut rendre un champ modifiable en le déclarant mutable : on l'affecte alors par la notation pointée et <-.

type compteur = { mutable valeur : int }

let incremente c = c.valeur <- c.valeur + 1

# let c = { valeur = 0 };;
val c : compteur = {valeur = 0}
# incremente c; incremente c; c.valeur;;
- : int = 2

type 'a ref = { mutable contents : 'a }

7.4 Types mutuellement récursifs

Deux types peuvent se référer l'un à l'autre : on les déclare ensemble avec and. C'est le pendant, pour les types, du let rec … and … qui liait deux fonctions mutuellement récursives (chapitre 1).

type 'a arbre = Noeud of 'a * 'a foret
and 'a foret = 'a arbre list

Les fonctions qui parcourent ces types sont elles aussi mutuellement récursives : une sur l'arbre, une sur la forêt.

let rec taille_arbre a =
  match a with
  | Noeud (_, f) -> 1 + taille_foret f
and taille_foret f =
  match f with
  | [] -> 0
  | a :: reste -> taille_arbre a + taille_foret reste

taille_arbre compte le nœud courant plus la taille de sa forêt ; taille_foret additionne les tailles des arbres de la liste. Chacune appelle l'autre : le and les rend mutuellement visibles.

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>7.5 Exercices résolus

Niveau $\star$ (application directe du cours)

type point = { x : float; y : float }

let distance_carree p = p.x *. p.x +. p.y *. p.y

type etudiant = { nom : string; note : float }

let est_recu e = e.note >= 10.0

type compteur = { mutable valeur : int }

let incremente c = c.valeur <- c.valeur + 1
let remet_a_zero c = c.valeur <- 0

Niveau $\star \star$ (raisonnement intermédiaire)

let milieu p1 p2 =
  { x = (p1.x +. p2.x) /. 2.0;
    y = (p1.y +. p2.y) /. 2.0 }

type compte = { mutable solde : int }

let depose c m = c.solde <- c.solde + m

let retire c m =
  if m <= c.solde then begin
    c.solde <- c.solde - m;
    true
  end
  else false

type bulletin = { nom : string; notes : float list }

let rec somme l =
  match l with
  | [] -> 0.0
  | x :: reste -> x +. somme reste

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

let moyenne b = somme b.notes /. float_of_int (longueur b.notes)

let augmente e =
  let nouvelle = if e.note +. 1.0 > 20.0 then 20.0 else e.note +. 1.0 in
  { e with note = nouvelle }

Niveau $\star \star \star$ (approfondissement)

let rec taille_arbre a =
  match a with
  | Noeud (_, f) -> 1 + taille_foret f
and taille_foret f =
  match f with
  | [] -> 0
  | a :: reste -> taille_arbre a + taille_foret reste

let rec hauteur_arbre a =
  match a with
  | Noeud (_, f) -> 1 + hauteur_foret f
and hauteur_foret f =
  match f with
  | [] -> 0
  | a :: reste ->
      let h = hauteur_arbre a and hr = hauteur_foret reste in
      if h > hr then h else hr

type element =
  | Fichier of fichier
  | Dossier of dossier
and fichier = { nom_f : string; taille : int }
and dossier = { nom_d : string; contenu : element list }

let rec taille_totale e =
  match e with
  | Fichier f -> f.taille
  | Dossier d -> taille_contenu d.contenu
and taille_contenu l =
  match l with
  | [] -> 0
  | e :: reste -> taille_totale e + taille_contenu reste

7.6 Exercices d'entraînement

Légende : $\star$ application directe, $\star \star$ raisonnement intermédiaire, $\star \star \star$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Enregistrements immuables.

• [11.] $\star$ Déclarer rectangle (largeur, hauteur flottantes) et écrire aire et perimetre.
• [12.] $\star \star$ Avec point, écrire symetrique_origine p (le point opposé) sans champ mutable.
• [13.] $\star \star$ $⧫$ Déclarer date (jour, mois, annee) et écrire avant d1 d2 (ordre chronologique).

Thème B — Champs mutables.

• [14.] $\star$ Avec compteur, écrire ajoute c n (ajoute n à la valeur).
• [15.] $\star \star$ Déclarer pile avec un champ mutable contenu : int list et écrire empile et depile (avec failwith si vide).
• [16.] $\star \star \star$ Expliquer la différence d'effet entre let d = c et la création d'un nouvel enregistrement, pour un compteur c.

Thème C — Sommes, enregistrements, listes.

• [17.] $\star \star$ Déclarer forme (variant Cercle/Rectangle) où chaque cas porte un enregistrement de dimensions, et écrire aire.
• [18.] $\star \star \star$ Avec bulletin, écrire meilleur l qui, d'une bulletin list non vide, renvoie le nom de l'étudiant de meilleure moyenne.
• [19.] $\star \star \star$ Déclarer un type json simplifié (nul, booléen, nombre, chaîne, liste, objet) — un bel usage de somme récursive — et écrire profondeur.

Thème D — Types mutuellement récursifs.

• [20.] $\star \star$ Sur arbre / foret, écrire somme_etiquettes (arbre d'entiers).
• [21.] $\star \star \star$ $⧫$ Sur le système de fichiers, écrire nb_fichiers e (nombre de fichiers contenus, récursivement).
• [22.] $\star \star \star$ Sur le système de fichiers, écrire contient_nom e s : un fichier ou dossier nommé s existe-t-il quelque part dans e ?