Types sommes: unions

        Les types sommes sont une généralisation des types énumérés: au lieu de définir des constantes, on définit des constructeurs qui prennent des arguments pour définir une valeur du nouveau type. Considérons par exemple un type d'expressions contenant des constantes (définies par leur valeur entière), des variables (définies par leur nom), des additions et des multiplications (définies par le couple de leurs deux opérandes), et des exponentiations définies par le couple d'une expression et de son exposant. On définira le type expression par:

 
type expression =
 | Const of int
 | Var of string
 | Add of expression * expression
 | Mul of expression * expression
 | Exp of expression * int;;

On crée des valeurs de type somme en appliquant leurs constructeurs à des arguments du bon type. Par exemple le polynôme 1 + 2x³ est représenté par l'expression:

let p = Add (Const 1, Mul (Const 2, Exp (Var "x", 3)));;

Les types somme permettent de faire du filtrage (pattern matching), afin de distinguer les cas en fonction d'une valeur filtrée. Ainsi la dérivation par rapport à une variable x se définirait simplement par:

 
let rec dérive x e =
 match e with
 | Const _ -> Const 0
 | Var s -> if x = s then Const 1 else Const 0
 | Add (e1, e2) -> Add (dérive x e1, dérive x e2) 
 | Mul (Const i, e2) -> Mul (Const i, dérive x e2)
 | Mul (e1, e2) -> Add (Mul (dérive x e1, e2), Mul (e1, dérive x e2))
 | Exp (e, i) -> Mul (Const i, Mul (dérive x e, Exp (e, i - 1)));;

Nous ne donnerons ici que la signification intuitive du filtrage sur notre exemple particulier. La construction match du corps de dérive signifie qu'on examine la valeur de l'argument e et selon que c'est:

• Const _ : une constante quelconque (_), alors on retourne la valeur .
• Var s : une variable que nous nommons s, alors on retourne 1 ou selon que c'est la variable par rapport à laquelle on dérive.
• Add (e1, e2) : une somme de deux expressions que nous nommons respectivement e1 et e2, alors on retourne la somme des dérivée des deux expressions e1 et e2.
• les autres cas sont analogues au cas de la somme.

On constate sur cet exemple la puissance et l'élégance du mécanisme. Combiné à la récursivité, il permet d'obtenir une définition de dérive qui se rapproche des définitions mathématiques usuelles.On obtient la dérivée du polynôme p = 1 + 2x³ en évaluant:

 
#dérive "x" p;;
- : expression =
 Add
  (Const 0,
   Mul (Const 2, Mul (Const 3, Mul (Const 1, Exp (Var "x", 2)))))

On constate que le résultat obtenu est grossièrement simplifiable. On écrit alors un simplificateur (nai"f) par filtrage sur les expressions:

 
let rec puissance i j =
 match j with
 | 0 -> 1
 | 1 -> i
 | n -> i * puissance i (j - 1);;

let rec simplifie e =
 match e with
 | Add (Const 0, e) -> simplifie e
 | Add (Const i, Const j) -> Const (i + j)
 | Add (e, Const i) -> simplifie (Add (Const i, e))
 | Add (e1, e2) -> Add (simplifie e1, simplifie e2)
 | Mul (Const 0, e) -> Const 0
 | Mul (Const 1, e) -> simplifie e
 | Mul (Const i, Const j) -> Const (i * j)
 | Mul (e, Const i) -> simplifie (Mul (Const i, e))
 | Mul (e1, e2) -> Mul (simplifie e1, simplifie e2)
 | Exp (Const 0, j) -> Const 0
 | Exp (Const 1, j) -> Const 1
 | Exp (Const i, j) -> Const (puissance i j)
 | Exp (e, 0) -> Const 1
 | Exp (e, 1) -> simplifie e
 | Exp (e, i) -> Exp (simplifie e, i)
 | e -> e;;

Pour comprendre le filtrage de la fonction simplifie, il faut garder à l'esprit que l'ordre des clauses est significatif puisqu'elles sont essayées dans l'ordre. Un exercice intéressant consiste aussi à prouver formellement que la fonction simplifie termine toujours.

On obtient maintenant la dérivée du polynôme p = 1 + 2x³ en évaluant:

 
#simplifie (dérive "x" p);;
- : expression = Mul (Const 2, Mul (Const 3, Exp (Var "x", 2)))