Types sommes et arbres

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

Jusqu'ici nous avons utilisé les types qu'OCaml fournit : entiers, booléens, n-uplets, listes, option. La puissance du langage vient de ce qu'on peut définir les siens, taillés sur mesure pour le problème traité. Modéliser un jeu de cartes, une expression arithmétique, un arbre généalogique : à chaque fois, un type bien choisi rend le code plus clair, et surtout permet au compilateur de vérifier qu'on a traité tous les cas.

Ce chapitre présente les types sommes (aussi appelés types énumérés, ou unions) : un type dont une valeur est l'une parmi plusieurs formes, chacune introduite par un constructeur. Le filtrage du chapitre précédent s'y applique directement et y prend tout son sens : un match sur un type somme est exhaustif exactement quand il couvre tous les constructeurs — et le compilateur le vérifie. On découvrira enfin les types récursifs, qui se définissent à partir d'eux-mêmes : les arbres, structure aussi fondamentale que la liste, et qui se traite par le même réflexe de récursion.

3.2 Déclarer un type

Le mot-clé type introduit un nouveau nom de type. Dans le cas le plus simple, un synonyme pour un type existant, qui documente l'intention :

type point = float * float
type chemin = point list

Un type peut être polymorphe : il dépend d'un (ou plusieurs) type(s) paramètre(s), notés 'a, 'b, …, écrits avant le nom.

type 'a paire = 'a * 'a          (* paire homogène *)

3.3 Les types sommes

3.3.1 Types énumérés

La forme la plus simple d'un type somme énumère un nombre fini de constructeurs constants :

type couleur = Trefle | Carreau | Coeur | Pique

Une valeur de type couleur s'examine par filtrage : un match est exhaustif s'il couvre les quatre constructeurs.

let est_rouge c =
  match c with
  | Coeur | Carreau -> true
  | Trefle | Pique -> false

3.3.2 Constructeurs porteurs de données

Un constructeur peut transporter des valeurs, déclarées après le mot-clé of :

type forme =
  | Point
  | Cercle of float                 (* rayon *)
  | Rectangle of float * float      (* largeur, hauteur *)

Ainsi Cercle 2.0 et Rectangle (3.0, 4.0) sont deux valeurs du même type forme. Le filtrage récupère au passage les données portées par chaque constructeur :

let aire f =
  match f with
  | Point -> 0.0
  | Cercle r -> 3.14159 *. r *. r
  | Rectangle (l, h) -> l *. h

3.3.3 Deux vieilles connaissances

Les types du chapitre précédent ne sont, en réalité, que des types sommes. Le type option est défini dans la bibliothèque standard par :

type 'a option = None | Some of 'a

None est un constructeur constant, Some porte une valeur de type 'a : c'est exactement le type somme polymorphe à deux cas qu'on filtrait au chapitre 2.

3.4 Les types récursifs : les arbres

Un type somme peut se référer à lui-même : il est alors récursif. C'est ainsi qu'on définit les structures de taille non bornée. La liste en est un exemple ; on pourrait la redéfinir nous-mêmes :

type 'a maliste = Vide | Cons of 'a * 'a maliste

Cons porte une tête et… une maliste (la queue) : la définition s'appuie sur le type en cours de définition. C'est exactement [] / ::, sans le sucre syntaxique.

3.4.1 Les arbres binaires

La structure récursive reine, après la liste, est l'arbre binaire : un arbre est vide, ou bien un nœud portant une valeur (l'étiquette) et deux sous-arbres.

type 'a arbre =
  | Vide
  | Noeud of 'a arbre * 'a * 'a arbre   (* sous-arbre gauche, étiquette, droit *)

let a =
  Noeud (Noeud (Vide, 1, Vide),
         2,
         Noeud (Vide, 3, Vide))

3.4.2 Récursion sur les arbres

Le réflexe est le même que sur les listes — un filtrage sur les deux formes — mais le cas récursif comporte deux appels, un par sous-arbre.

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

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

Niveau $\star$ (application directe du cours)

type jour = Lundi | Mardi | Mercredi | Jeudi | Vendredi | Samedi | Dimanche

let est_weekend j =
  match j with
  | Samedi | Dimanche -> true
  | _ -> false

let aire f =
  match f with
  | Point -> 0.0
  | Cercle r -> 3.14159 *. r *. r
  | Rectangle (l, h) -> l *. h

let est_plus_grande f g = aire f > aire g

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

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

let rec hauteur a =
  match a with
  | Vide -> 0
  | Noeud (g, _, d) ->
      let hg = hauteur g and hd = hauteur d in
      1 + (if hg > hd then hg else hd)

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

let rec miroir a =
  match a with
  | Vide -> Vide
  | Noeud (g, x, d) -> Noeud (miroir d, x, miroir g)

type expr =
  | Const of int
  | Plus of expr * expr
  | Fois of expr * expr

let rec evalue e =
  match e with
  | Const n -> n
  | Plus (a, b) -> evalue a + evalue b
  | Fois (a, b) -> evalue a * evalue b

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

let rec appartient x a =
  match a with
  | Vide -> false
  | Noeud (g, v, d) ->
      if x = v then true
      else if x < v then appartient x g
      else appartient x d

let rec insere x a =
  match a with
  | Vide -> Noeud (Vide, x, Vide)
  | Noeud (g, v, d) ->
      if x = v then a
      else if x < v then Noeud (insere x g, v, d)
      else Noeud (g, v, insere x d)

let rec infixe a =
  match a with
  | Vide -> []
  | Noeud (g, x, d) -> infixe g @ [x] @ infixe d

3.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 — Types énumérés et sommes simples.

• [11.] $\star$ Déclarer type feu = Vert | Orange | Rouge et écrire suivant : feu -> feu (le cycle d'un feu tricolore).
• [12.] $\star \star$ Avec forme, écrire perimetre : forme -> float.
• [13.] $\star \star$ $⧫$ Déclarer type 'a resultat = Ok of 'a | Erreur of string et écrire division_sure : int -> int -> int resultat (Erreur si le diviseur est nul).

Thème B — Mesures sur les arbres.

• [14.] $\star$ Écrire somme_arbre : int arbre -> int (somme des étiquettes).
• [15.] $\star \star$ $⧫$ Écrire appartient_general x a (sans hypothèse d'ABR : parcourir tout l'arbre).
• [16.] $\star \star \star$ Écrire est_equilibre a : en tout nœud, les hauteurs des deux sous-arbres diffèrent d'au plus $1$.

Thème C — Transformer des arbres.

• [17.] $\star \star$ Écrire incremente_arbre : int arbre -> int arbre (chaque étiquette $+1$, nouvel arbre).
• [18.] $\star \star \star$ Sur le type expr, écrire nb_operations : expr -> int (nombre de Plus et Fois).
• [19.] $\star \star \star$ Étendre expr avec Moins of expr * expr et adapter evalue ; vérifier que le compilateur signale le match devenu non exhaustif avant correction.

Thème D — Arbres binaires de recherche.

• [20.] $\star \star$ Écrire de_liste : 'a list -> 'a arbre qui insère successivement les éléments d'une liste dans un ABR (initialement Vide).
• [21.] $\star \star \star$ $⧫$ En déduire trie : 'a list -> 'a list (construire un ABR puis le parcourir en infixe). Quel tri reconnaît-on ?
• [22.] $\star \star \star$ Écrire minimum_abr : 'a arbre -> 'a option renvoyant la plus petite étiquette d'un ABR (descendre toujours à gauche).