Types de Données Algébriques

1. Introduction

Dans le cours précédent, on a vu comment tout construire à partir de fun. C'était pur, c'était beau, c'était minimaliste. Mais avouons-le : quand on a codé les booléens de Church, on s'est dit "c'est génial… mais est-ce qu'on peut pas avoir des vrais booléens ?"

La réponse est oui, et c'est là qu'interviennent les Types de Données Algébriques (Algebraic Data Types ou ADT). Inventés dans les années 70 par le langage ML (Meta-Language), les ADT sont le cœur battant d'OCaml. Un ADT, c'est une façon de dire au compilateur : "voici la forme de mes données, et voici toutes les façons possibles de les construire".

Concrètement, un ADT c'est :

• un nom de type,
• un ou plusieurs constructeurs séparés par |,
• chaque constructeur peut porter des arguments (des valeurs d'autres types).

La magie des ADT, c'est qu'ils sont fermés : il n'y a que les constructeurs que vous avez déclarés, pas de surprise. Le compilateur peut vérifier que vous avez traité tous les cas. Adieu les bugs !

Ce cours va construire progressivement des ADT de plus en plus complexes :

1. Booléens — le plus simple des ADT (deux constructeurs sans arguments).
2. Entiers de Peano — le premier ADT récursif, pour la culture.
3. Listes — l'ADT récursif le plus utile, d'abord d'entiers puis génériques.
4. Arbres — des structures plus complexes, avec plusieurs branches récursives.

Ensuite, on généralisera avec le schéma fold (catamorphisme) et on verra comment écrire des fonctions de façon élégante et prouver des propriétés. Enfin, on découvrira l'opérateur pipe |>, passerelle vers le prochain cours sur les monades.

2. Booléens (enfin !)

Dans le cours précédent, on avait encodé les booléens à la Church : true_c = fun t f -> t. C'était élégant, mais pas très pratique. Avec les ADT, on a de vrais booléens :

type bool =
  | True
  | False

Note : en OCaml, le type booléen existe déjà (true et false en minuscules). On définit ici le nôtre pour la pédagogie. Appelons-le mybool si on veut coexister avec celui d'OCaml.

(* Notre propre type booléen *)
type mybool =
  | True
  | False

(* Testons *)
True  (* c'est une valeur de type mybool *)
False (* aussi *)

Déjà, c'est plus clair que fun t f -> t, non ?

Avec le pattern matching (vu à la fin du cours précédent), on peut maintenant écrire des fonctions sur nos booléens :

(*) Négation *)
let neg b =
  match b with
  | True  -> False
  | False -> True

(* Conjonction *)
let andb b1 b2 =
  match b1 with
  | True  -> b2
  | False -> False

(* Disjonction *)
let orb b1 b2 =
  match b1 with
  | True  -> True
  | False -> b2

Regardez comme le pattern matching rend le code évident : chaque ligne correspond à un cas possible. Pas de if tordu, pas de bordel logique. Et le compilateur vérifie qu'on a bien traité tous les cas.

On peut aussi convertir vers les vrais booléens OCaml (pour interagir avec le reste du monde) :

let to_bool b =
  match b with
  | True  -> true
  | False -> false

let of_bool b =
  if b then True else False

Ce qu'il faut retenir des booléens comme ADT :

• Un type avec deux constructeurs sans arguments : c'est le plus simple des ADT.
• Le pattern matching énumère tous les cas — on ne peut pas en oublier un.
• On peut déjà voir le schéma général : chaque constructeur donne un cas dans le match.

3. Entiers de Peano

Dans le cours précédent, on avait triché : on avait utilisé les entiers natifs d'OCaml sans les construire nous-mêmes. Il est temps de se rattraper avec les entiers de Peano, un encodage des naturels sous forme d'ADT récursif.

L'idée est simple comme les mathématiques :

• Zéro est un entier naturel.
• Si n est un entier naturel, alors Succ n (le successeur de n) est aussi un entier naturel.

Traduit en OCaml, ça donne :

type peano =
  | Zero
  | Succ of peano

C'est tout ! Ce type dit : "un peano est soit Zero, soit Succ d'un autre peano". C'est un ADT récursif : le constructeur Succ contient une valeur du type qu'on est en train de définir.

Avec ça, 0 = Zero, 1 = Succ Zero, 2 = Succ (Succ Zero), etc.

(* Les premiers entiers naturels *)
let zero  = Zero
let un    = Succ zero
let deux  = Succ (Succ zero)
let trois = Succ (Succ (Succ zero))

3.1 Opérations sur les Peano

Maintenant qu'on a nos entiers, on peut faire des opérations. Chaque opération suit la même recette :

1. On fait un match sur l'argument récursif.
2. Cas Zero : on retourne le cas de base.
3. Cas Succ n : on fait un appel récursif sur n et on construit le résultat.

(* Convertir un peano en entier OCaml *)
let rec to_int n =
  match n with
  | Zero      -> 0
  | Succ p   -> 1 + to_int p

(* Addition *)
let rec add n m =
  match n with
  | Zero      -> m
  | Succ p   -> Succ (add p m)

(* Multiplication *)
let rec mul n m =
  match n with
  | Zero      -> Zero
  | Succ p   -> add m (mul p m)

Testons :

to_int (add deux trois)  (* = 5 *)
to_int (mul deux trois)  (* = 6 *)

4. Listes d'entiers

Les listes sont le type récursif le plus important en programmation fonctionnelle. Commençons par des listes d'entiers (on généralisera après) :

type intlist =
  | Nil
  | Cons of int * intlist

On retrouve la même structure qu'avec Peano :

• Un constructeur de base : Nil (la liste vide, comme Zero).
• Un constructeur récursif : Cons (h, t) qui ajoute h en tête de t (comme Succ ajoute 1).

Note : en OCaml, les listes natives utilisent [] (Nil) et h :: t (Cons), et le constructeur :: est infixe pour plus de lisibilité.

(* Quelques listes d'entiers *)
let vide  = Nil
let lst1  = Cons (1, Nil)
let lst3  = Cons (1, Cons (2, Cons (3, Nil)))

4.1 Fonctions sur les listes d'entiers

Le pattern est toujours le même : un match avec deux cas.

(* Longueur d'une liste *)
let rec length lst =
  match lst with
  | Nil              -> 0
  | Cons (_, t)       -> 1 + length t

(* Somme des éléments *)
let rec sum lst =
  match lst with
  | Nil              -> 0
  | Cons (h, t)       -> h + sum t

(* Concaténer deux listes *)
let rec append l1 l2 =
  match l1 with
  | Nil              -> l2
  | Cons (h, t)       -> Cons (h, append t l2)

(* Inverser une liste *)
let rec rev lst =
  match lst with
  | Nil              -> Nil
  | Cons (h, t)       -> append (rev t) (Cons (h, Nil))

Vous remarquez que append est en O(n) où n est la taille de l1 : on doit recopier toute la première liste. C'est le prix à payer pour une liste simplement chaînée. En OCaml, l'opérateur @ fait la même chose.

5. Listes génériques (polymorphes)

Avoir une intlist, c'est bien. Mais si on veut une liste de string, de float, ou de paires ? On va devoir recopier tout le code ?

Heureusement, OCaml supporte le polymorphisme (les types génériques). On peut définir un type de liste qui marche pour n'importe quel type d'éléments :

(* Une liste générique : 'a list *)
type 'a list =
  | []
  | :: of 'a * 'a list

Note : en OCaml, les constructeurs [] et :: sont prédéfinis et le constructeur :: est infixe. La définition ci-dessus est exactement celle de la bibliothèque standard. Le 'a est une variable de type : elle peut être remplacée par n'importe quel type.

Du coup, on peut écrire les fonctions de façon générique :

(* Longueur générique *)
let rec length lst =
  match lst with
  | []      -> 0
  | _ :: t  -> 1 + length t

(* Concaténation générique *)
let rec append l1 l2 =
  match l1 with
  | []      -> l2
  | h :: t  -> h :: append t l2

La magie du polymorphisme : length marche sur des listes d'entiers, de chaînes, de listes… tout ce qui se présente !

length [1; 2; 3]
length ["a"; "b"]
length [[1]; [2; 3]; []]

5.1 map, filter, fold

Voici trois fonctions fondamentales sur les listes, qu'on retrouve dans tous les langages fonctionnels :

(* map : appliquer une fonction à chaque élément *)
let rec map f lst =
  match lst with
  | []      -> []
  | h :: t  -> f h :: map f t

(* filter : garder les éléments qui satisfont un prédicat *)
let rec filter p lst =
  match lst with
  | []      -> []
  | h :: t  -> if p h then h :: filter p t else filter p t

(* fold_right (ou reduce) : plier une liste avec un accumulateur *)
let rec fold_right f lst acc =
  match lst with
  | []      -> acc
  | h :: t  -> f h (fold_right f t acc)

Ces trois fonctions sont tellement importantes qu'elles sont dans la bibliothèque standard d'OCaml (et de tous les langages fonctionnels).

(*) Exemples d'utilisation *)

(* map : doubler chaque élément *)
map (fun x -> x * 2) [1; 2; 3]
(* = [2; 4; 6] *)

(* filter : garder les pairs *)
filter (fun x -> x mod 2 = 0) [1; 2; 3; 4]
(* = [2; 4] *)

(* fold_right : somme des éléments *)
fold_right (fun x acc -> x + acc) [1; 2; 3] 0
(* = 6 *)

(* On peut réécrire sum avec fold_right *)
let sum lst = fold_right (fun x acc -> x + acc) lst 0

5.2 Applications inspirantes

Avec map, filter et fold, on peut exprimer une grande variété de traitements de listes de façon élégante :

(* Produit scalaire de deux vecteurs *)
let dot v1 v2 =
  sum (map (fun (a, b) -> a * b) (List.combine v1 v2))

(* Nombres pairs au carré *)
let square_even lst =
  map (fun x -> x * x) (filter (fun x -> x mod 2 = 0) lst)

(* Vérifier si tous les éléments sont pairs *)
let all_even lst =
  fold_right (fun x acc -> (x mod 2 = 0) && acc) lst true

6. Arbres & expressions arithmétiques

On a vu les types récursifs linéaires (Peano, listes). Passons aux arbres, où chaque nœud peut avoir plusieurs branches. L'exemple classique, ce sont les expressions arithmétiques :

type expr =
  | Const of int           (* constante entière *)
  | Add   of expr * expr   (* addition *)
  | Mul   of expr * expr   (* multiplication *)
  | Sub   of expr * expr   (* soustraction *)
  | Div   of expr * expr   (* division *)

Ce type représente un arbre de syntaxe abstraite (AST). Au lieu d'une chaîne de caractères comme "(3 + 4) * 2", on a une structure de données qu'on peut manipuler avec OCaml.

Exemples d'expressions :

(* 3 + 4 *)
let e1 = Add (Const 3, Const 4)

(* (3 + 4) * 2 *)
let e2 = Mul (Add (Const 3, Const 4), Const 2)

(* 10 / (5 - 3) *)
let e3 = Div (Const 10, Sub (Const 5, Const 3))

6.1 Évaluation et simplification

Le vrai pouvoir des AST, c'est qu'on peut écrire des fonctions qui les transforment. Voici un évaluateur (qui calcule la valeur de l'expression) :

let rec eval e =
  match e with
  | Const n      -> n
  | Add (e1, e2) -> eval e1 + eval e2
  | Mul (e1, e2) -> eval e1 * eval e2
  | Sub (e1, e2) -> eval e1 - eval e2
  | Div (e1, e2) -> eval e1 / eval e2

Testons :

eval e1  (* = 7 *)
eval e2  (* = 14 *)
eval e3  (* = 5 *)

Et maintenant, un simplificateur qui applique des règles de simplification :

let rec simpl e =
  match e with
  | Const _          -> e
  | Add (e1, e2)    ->
      (match (simpl e1, simpl e2) with
      | (Const 0, e) -> e          (* 0 + x = x *)
      | (e, Const 0) -> e          (* x + 0 = x *)
      | (e1, e2)    -> Add (e1, e2))
  | Mul (e1, e2)    ->
      (match (simpl e1, simpl e2) with
      | (Const 0, _) -> Const 0  (* 0 * x = 0 *)
      | (_, Const 0) -> Const 0  (* x * 0 = 0 *)
      | (Const 1, e) -> e          (* 1 * x = x *)
      | (e, Const 1) -> e          (* x * 1 = x *)
      | (e1, e2)    -> Mul (e1, e2))
  | Sub (e1, e2)    ->
      (match (simpl e1, simpl e2) with
      | (e, Const 0) -> e          (* x - 0 = x *)
      | (e1, e2)    -> Sub (e1, e2))
  | Div (e1, e2)    ->
      (match (simpl e1, simpl e2) with
      | (e, Const 1) -> e          (* x / 1 = x *)
      | (e1, e2)    -> Div (e1, e2))

On peut aussi ajouter des variables et un environnement pour faire du calcul symbolique !

Variation : on peut ajouter des constructeurs pour les variables et les fonctions lambda :

(* Un AST pour le lambda-calcul *)
type term =
  | Var   of string
  | Abs   of string * term
  | App   of term * term

(* (fun x -> x) 1  s'écrit : *)
let ex = App (Abs ("x", Var "x"), Var "1")

Ceci fait le pont avec le premier cours de la série !

7. Le schéma fold (catamorphisme)

Vous avez peut-être remarqué un pattern qui se répète dans toutes nos fonctions récursives :

(* Schéma général d'une fonction sur un ADT *)
let rec ma_fonction data =
  match data with
  | Constructeur_sans_récursion -> valeur_de_base
  | Constructeur_avec_récursion sous_parties ->
      combiner (ma_fonction sous_partie1) ...

Ce pattern, c'est le fold (ou catamorphisme). L'idée : on "plie" la structure de données en remplaçant chaque constructeur par une fonction.

7.1 Fold sur les listes

On a déjà vu fold_right sur les listes. En voici une version générale, écrite par mimétisme avec le type liste :

-- fold_right : (h -> acc -> acc) -> list -> acc -> acc *)
-- c'est le catamorphisme des listes *)
let rec fold_right f lst acc =
  match lst with
  | []      -> acc                 (* remplace [] par acc *)
  | h :: t  -> f h (fold_right f t acc)   (* remplace :: par f *)

-- Grâce à fold_right, on peut réécrire toutes nos fonctions :

let length lst = fold_right (fun _ n -> n + 1) lst 0
let sum   lst = fold_right (fun x acc -> x + acc) lst 0
let map   f lst = fold_right (fun h acc -> f h :: acc) lst []
let filter p lst =
  fold_right (fun h acc -> if p h then h :: acc else acc) lst []
let append l1 l2 = fold_right (fun h acc -> h :: acc) l1 l2
let rev lst = fold_right (fun h acc -> acc @ [h]) lst []

Regardez comme c'est puissant : toutes nos fonctions sur les listes s'expriment comme des cas particuliers de fold_right. Le squelette récursif est factorisé une fois pour toutes.

7.2 Fold sur les arbres

Le même schéma s'applique aux arbres. Voici un fold pour notre type expr :

(* Catamorphisme pour les expressions arithmétiques *)
let rec fold_expr fconst fadd fmul fsub fdiv e =
  match e with
  | Const n      -> fconst n
  | Add (e1, e2) -> fadd (fold_expr fconst fadd fmul fsub fdiv e1)
                             (fold_expr fconst fadd fmul fsub fdiv e2)
  | Mul (e1, e2) -> fmul (fold_expr fconst fadd fmul fsub fdiv e1)
                             (fold_expr fconst fadd fmul fsub fdiv e2)
  | Sub (e1, e2) -> fsub (fold_expr fconst fadd fmul fsub fdiv e1)
                             (fold_expr fconst fadd fmul fsub fdiv e2)
  | Div (e1, e2) -> fdiv (fold_expr fconst fadd fmul fsub fdiv e1)
                             (fold_expr fconst fadd fmul fsub fdiv e2)

Avec ce fold, on peut réécrire eval en une ligne :

let eval2 e =
  fold_expr
    (fun n -> n)           (* Const : retourne la valeur *)
    (fun x y -> x + y)    (* Add : additionne *)
    (fun x y -> x * y)    (* Mul : multiplie *)
    (fun x y -> x - y)    (* Sub : soustrait *)
    (fun x y -> x / y)    (* Div : divise *)
    e

Et on peut aussi calculer la hauteur de l'arbre, le nombre de nœuds, l'afficher… tout ça avec la même fonction fold_expr en changeant les paramètres !

7.3 Raisonner avec fold

Un des avantages majeurs du fold, c'est qu'il permet de prouver des propriétés sur les programmes par récurrence structurelle.

Par exemple, prouvons que length (append l1 l2) = length l1 + length l2 :

(* On veut montrer : length (append l1 l2) = length l1 + length l2 *)

-- Cas l1 = [] :
--   length (append [] l2) = length l2 = 0 + length l2 = length [] + length l2 ✓

-- Cas l1 = h :: t (par hypothèse de récurrence, la propriété est vraie pour t) :
--   length (append (h :: t) l2)
--   = length (h :: append t l2)
--   = 1 + length (append t l2)
--   = 1 + (length t + length l2)        (par HR)
--   = (1 + length t) + length l2
--   = length (h :: t) + length l2 ✓

Les lois de fusion des folds permettent même de transformer des programmes pour les rendre plus efficaces ! Par exemple :

(* Avant fusion : on parcourt deux fois la liste *)
fold_right f (map g lst) acc

(* Après fusion (si les conditions sont remplies) : un seul parcours *)
fold_right (fun x acc -> f (g x) acc) lst acc

Cette optimisation s'appelle la déforestation ou fusion de folds. Les compilateurs modernes (comme GHC pour Haskell) l'appliquent automatiquement.

8. L'opérateur |>

Quand on enchaîne plusieurs transformations sur une liste, ça devient vite illisible :

(* Prendre les pairs, les doubler, et les additionner *)
fold_right (fun x acc -> x + acc)
  (map (fun x -> x * 2)
    (filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5]))
  0

Les parenthèses s'imbriquent, on lit de l'intérieur vers l'extérieur… le cerveau humain n'aime pas ça.

La solution : l'opérateur pipe |>, aussi appelé "forward pipe" ou "opérateur de flux". Sa définition est ridiculement simple :

// L'opérateur pipe : prendre x, l'appliquer à f *)
let (|>) x f = f x

C'est tout ! x |> f c'est juste f x. Mais l'ordre d'écriture change tout pour la lisibilité :

// Avec pipe, on lit de gauche à droite comme un flux :
// "prends la liste, filtre les pairs, double chaque, puis somme"
[1; 2; 3; 4; 5]
  |> filter (fun x -> x mod 2 = 0)
  |> map (fun x -> x * 2)
  |> fold_right (fun x acc -> x + acc) 0

C'est beaucoup plus lisible ! Chaque étape du traitement est sur sa propre ligne, et on lit dans l'ordre naturel : données → transformation 1 → transformation 2 → résultat.

8.1 Flots de données

Le pipe est au cœur du style de programmation par flots de données (dataflow). C'est la même idée que les pipes Unix (|) : chaque programme transforme des données et les passe au suivant.

En OCaml, le pipe est utilisé massivement :

// Traitement plus complexe *)
let result =
  donnees
  |> List.filter critere
  |> List.map transformation
  |> List.sort comparateur
  |> List.fold_left combine initial
  |> afficher

Le pipe est aussi une porte d'entrée vers les monades – le sujet du prochain cours. En effet, les monades généralisent l'idée du pipe à des contextes d'exécution plus riches (options, erreurs, asynchrone, etc.).

// Exemple d'anticipation : le bind de l'option monad *)
// (On verra ça en détail dans le cours 3) *)
let (>>=) opt f =
  match opt with
  | Some x -> f x
  | None   -> None

// Chaîner des calculs qui peuvent échouer *)
Some 3 >>= (fun x -> Some (x + 1)) >>= (fun x -> Some (x * 2))

Vous voyez le parallèle ? |> chaîne des transformations simples, >>= chaîne des transformations qui peuvent échouer. La monade, c'est le pipe en mieux.

9. Conclusion

On a parcouru un sacré chemin !

Les ADT sont l'un des piliers de la programmation fonctionnelle. Combinés au pattern matching, ils permettent d'écrire du code concis, sûr (le compilateur vérifie tout), et expressif.

Dans le prochain cours, on généralisera l'idée du pipe avec les monades : on verra comment chaîner des calculs avec effets (options, erreurs, état, asynchrone) de façon élégante et compositionnelle. On parlera de Option, Result, List comme monades, et on construira une petite monade nous-mêmes.

Fait avec ❤️, beaucoup de λ, et des ADT bien rangés