Modélisation de données avec types algébriques

1. Les types produits : Avoir "ceci" ET "cela"

Commençons par le cas où une donnée est un agrégat de plusieurs autres. Par exemple, un étudiant a un nom et une année de diplôme. Un point dans un plan a une abscisse et une ordonnée. On parle de types produits, car ils correspondent mathématiquement au produit cartésien des types de leurs composantes.

OCaml nous offre deux manières principales de construire ces types : les records (enregistrements) et les tuples (n-uplets).

Les enregistrements (records)

Un enregistrement regroupe plusieurs valeurs en leur donnant un nom (un champ). C'est l'équivalent des struct en C ou des objets simples en Python. Ils sont particulièrement utiles lorsque les champs ont une sémantique claire.

La vidéo suivante vous montrera la syntaxe pour définir un type record, créer une valeur de ce type, et accéder à ses champs.

La syntaxe est donc type nom_du_type = { champ1: type1; champ2: type2; ... }.

Les n-uplets (tuples)

Un n-uplet est une structure plus légère qui agrège un nombre fixe de valeurs sans nommer les champs. On y accède par position.

Reprenez la vidéo précédente pour voir comment ils fonctionnent.

Alors, quand utiliser l'un ou l'autre ?

Pour formaliser l'idée de "type produit", regardez ce court extrait.

2. Les types sommes : Avoir "ceci" OU "cela"

Passons maintenant au cas où une donnée peut prendre l'une de plusieurs formes possibles. Par exemple, une forme géométrique est un cercle ou un rectangle. Un moyen de paiement est une carte de crédit ou un virement ou du liquide. Ces types sont appelés types sommes ou variants.

C'est là que la véritable puissance du système de types d'OCaml et du filtrage par motif commence à se manifester. Un type variant est défini par une liste de constructeurs.

Un variant peut faire plus que simplement énumérer des constantes. Chaque constructeur peut également "transporter" des données. C'est ce qui nous permet de modéliser des structures complexes.

Le document en français suivant, issu d'un cours de l'École Polytechnique, présente cela sous le nom de "types construits".

Conceptuellement, ces types correspondent à une union disjointe (ou "union étiquetée" - tagged union) en mathématiques.

3. La puissance des types algébriques : combiner sommes et produits

La véritable expressivité vient de la capacité à combiner et imbriquer types sommes et types produits. Un exemple canonique, fondamental en informatique, est l'arbre binaire.

Comment modéliser un arbre binaire en OCaml ?

• Un arbre est soit vide, soit un nœud. (-> type somme / variant)
• Un nœud contient une valeur, et un sous-arbre gauche, et un sous-arbre droit. (-> type produit / tuple ou record)

Cela se traduit directement en OCaml :

Cette seule définition est une synthèse parfaite de tout ce que nous avons vu : variants, produits (ici un tuple implicite) et récursivité.

Pour aller plus loin et voir comment ces concepts sont utilisés dans un contexte de conception logicielle plus vaste, la lecture suivante est très instructive.

4. Exercice de synthèse

Pour consolider ces notions, vous allez modéliser et évaluer des expressions arithmétiques simples.

Énoncé :

1. Définissez un type expr pour représenter une expression arithmétique. Une expression peut être :

   • Une constante entière.
   • L'addition de deux expressions.
   • La soustraction de deux expressions.
   • La multiplication de deux expressions.

   Indice : vous aurez besoin d'un constructeur pour chaque cas. Trois d'entre eux porteront des données.

2. Écrivez une fonction récursive evalue : expr -> int qui prend une expression et retourne le résultat de son évaluation. Vous devrez utiliser le filtrage par motif sur votre type expr.

Prenez le temps nécessaire pour réfléchir à la structure du type, puis à celle de la fonction.

(* 1. Définition du type algébrique pour les expressions *)
type expr =
  | Const of int
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

(* 2. Fonction d'évaluation récursive *)
let rec evalue e =
  match e with
  | Const n -> n (* Cas de base : la valeur d'une constante est elle-même *)
  | Add (e1, e2) -> (evalue e1) + (evalue e2) (* Cas récursifs *)
  | Sub (e1, e2) -> (evalue e1) - (evalue e2)
  | Mul (e1, e2) -> (evalue e1) * (evalue e2)

(* Quelques tests pour vérifier *)
let () =
  (* Crée l'expression (3 * (5 + 2)) *)
  let my_expr = Mul (Const 3, Add (Const 5, Const 2)) in
  assert (evalue my_expr = 21);

  (* Crée l'expression (10 - 4) *)
  let another_expr = Sub (Const 10, Const 4) in
  assert (evalue another_expr = 6);
  
  print_endline "Tests passés avec succès !"

Conclusion

Cette leçon vous a doté d'un outil d'une puissance considérable : la capacité de créer vos propres types de données pour modéliser précisément un problème. C'est le cœur de la programmation en OCaml.

Points clés à retenir :

• Les types produits (records, tuples) servent à agréger des données qui doivent toutes être présentes (une relation ET). Les records sont préférables lorsque les champs ont une sémantique claire.
• Les types sommes (variants) servent à représenter un choix parmi plusieurs formes possibles (une relation OU).
• La combinaison des deux, souvent de manière récursive, permet de créer des types algébriques de données (TAD) très expressifs, comme les arbres ou les langages formels.
• Le filtrage par motif est le mécanisme idiomatique et sûr pour manipuler les valeurs de ces types, en garantissant que tous les cas sont traités.

Dans notre prochaine leçon, nous explorerons un autre pilier de la programmation fonctionnelle : les fonctions d'ordre supérieur. Nous verrons comment écrire des fonctions qui prennent d'autres fonctions en argument, comme map, filter et fold, ce qui nous permettra d'écrire du code encore plus général et réutilisable.