I. Définition inductive d'un ensemble

Idée : définir un ensemble d'objets "par récurrence".

En français : on peut appliquer les constructeurs autant de fois que nécessaire (en se limitant à un nombre fini de fois) à partir des cas de base, pour obtenir tous les éléments de .

Par exemple :

• on peut définir les listes d'entiers inductivement comme :
  • soit la liste vide [] ;
  • soit x::q, où x est un entier et q une liste ;
• on peut définir les arbres comme :
  • soit une feuille F ;
  • soit un nœud, composé de deux arbres ou plus !

II. L'équivalent OCaml : les types récursifs

a) Types énumération

On peut écrire des types énumération en OCaml :

type classe =
    | MPSI_1
    | MPSI_2
    | MP_1
    | MP_2
    | MP_ET;;

Une valeur de type classe peut alors prendre une des 5 valeurs définies (et rien d'autre !). Par exemple :

let ma_classe: classe = MPSI_1;;

On peut également stocker des données arbitraires dans une des options :

type classe =
    | MPSI_1
    | MPSI_2
    | MP_1
    | MP_2
    | MP_ET
    | Autre of string;;

let ma_classe: classe = Autre "BCPST";;

La construction match est alors très utile, car elle permet de traiter séparément chaque cas du type énumération.

let nb_eleves (c: classe): int = match c with
    | MPSI_1 -> 49
    | MPSI_2 -> 43
    | MP_1 -> 38
    | MP_2 -> 36
    | MP_ET -> 40
    | Autre nom -> failwith ("classe inconnue : " ^ nom);;

nb_eleves MP_1;;
nb_eleves MPSI_2;;

b) Types récursifs

On peut également faire des types récursifs, c'est-à-dire utiliser le type classe dans sa propre définition !

Bien sûr, il faut que certains variants n'utilisent pas de type récursif, pour qu'on puisse "s'arrêter".

type classe = MP | MPSI | PCSI | PC | Autre of string | DoubleNiveau of classe * classe;;

let classe4 = DoubleNiveau (MP, PC);;

let classe5 = DoubleNiveau (DoubleNiveau (MP, PC), Autre "MPI");;

III. Petit point sur les listes

En OCaml, on pourrait définir nous-mêmes un type de liste :

type liste = Vide | El of int * liste;;

Par exemple, la liste [1; 2; 3] s'écrit alors :

let l : liste = El (1, El (2, El (3, Vide)));;

(* la longueur d'une liste, par récurrence sur sa structure *)
let rec longueur (l: liste): int = match l with
    | Vide -> 0
    | El (_, q) -> 1 + longueur q;;

longueur l;;

Exercices

let rec somme (l : liste) : int = match l with
    | Vide -> 0
    | El (x, q) -> x + somme q;;

let rec vers_liste (l : liste) : int list = match l with
    | Vide -> []
    | El (x, q) -> x :: vers_liste q;;

type couleur = Pique | Coeur | Carreau | Trefle;;
type valeur = Nombre of int | Valet | Dame | Roi | As;;
type carte = valeur * couleur;;

let points ((v, _) : carte) : int = match v with
    | As -> 11
    | Valet | Dame | Roi -> 10
    | Nombre n -> n;;

points (Dame, Coeur);;

let rec nb_niveaux (c : classe) : int = match c with
    | DoubleNiveau (c1, c2) -> nb_niveaux c1 + nb_niveaux c2
    | _ -> 1;;