Type algébrique de données

Untype algébriqueest une forme detype de donnéescomposite,qui combine les fonctionnalités destypes produits(n‐uplets ou enregistrements) et destypes sommes(union disjointe). Combinée à larécursivité,elle permet d’exprimer les données structurées telles que les listes et les arbres.

Définitions

Type produit

Letype produitde deux typesAetBest l’analogue enthéorie des typesduproduit cartésienensemblisteet est notéA×B.C’est le type des couples dont la première composante est de typeAet la seconde de typeB.Deuxfonctionscanoniques lui sont associées, appeléesprojections,donnant la valeur de chaque composante.

Exemple: type produit enOCaml:

On peut définir en langage OCaml le type d’une entrée dedictionnaire:

typedict_entry=string*int

letentry=("clé",37)

(* get_value: dict_entry -> int *)
letget_value(key,value)=value

Le produit se généralise naturellement à un nombre quelconque d’opérandes, pour donner des types den‐uplets. Dans le cas particulier duproduit vide,le type des 0‐uplets est nommétype unitéet noté1:c’est l’élément neutredu produit et il contient une unique valeur, souvent notée().

Des considérations pratiques amènent souvent à nommer les composantes.Dans ce contexte, le type est souvent appeléstructureet ses valeurs desenregistrements;les composantes sont appeléesmembres,et la projection selon le membrems’écrit avec une notation suffixe.m.

Exemple: structure en OCaml:

Toujours en OCaml, l’exemple précédent s’adapte ainsi:

typedict_entry={
key:string;
value:int;
}

letentry={key="clé";value=37}

(* get_value: dict_entry -> int *)
letget_valueentry=entry.value

Exemple: structure enlangage C:

Cette fonctionnalité se traduit en langage C parle mot‐cléstruct(en):

typedefstruct{
char*key;
intvalue;
}dict_entry;

dict_entryentry={.key="clé",.value=37};

intget_value(dict_entryentry){
returnentry.value;
}

Type somme

Letype sommede deux typesAetBest l’analogue en théorie des types de l’union disjointeensembliste et est notéA+B.Il représente un type contenant toutes les valeurs de chacun des deux typesAetB,de telle sorte qu’une valeur issue deAne puisse pas être confondue avec une valeur issue deB(même siA=B).

En théorie des ensembles, on représenterait la somme par l’ensemble{1}×A∪ {2}×B;la première composante (1 ou 2) d’un tel objet est une étiquette qui indique si cet objet se trouve dans le bras de gauche (A) ou dans le bras de droite (B) de la somme. Les analogues en théorie des types des expressions(1,a)et(2,b)sont souvent notésι₁aetι₂b(ιest la lettre grecqueiota). Ces notationsι₁etι₂peuvent être vues comme des fonctionsinjectives,respectivement deAdansA+Bet deBdansA+B,qui permettent de construire les valeurs de la somme, d’où leur nom deconstructeurs.Dansι₁a,la valeuraest appelée l’argumentdu constructeurι₁.

Traiter des valeurs d’un type somme requiert un raisonnement par cas, nommé dans ce contextefiltrage par motif.Chaque bras — qu’on reconnaît par son constructeur et dont on peut récupérer la valeur puisque ce constructeur est injectif — fait l’objet d’un cas séparé.

Exemple: type somme en OCaml:

On peut définir on OCaml l’union disjointe des nombres entiers et des nombres flottants et définir par filtrage une fonction sur cette union:

typesum=Intofint|Floatoffloat

(* print: sum -> unit *)
letprint=function
|Inti->Printf.printf"%i"i
|Floatf->Printf.printf"%f"f

Ici, les constructeurs sont nommésIntetFloat.

Exemple: type « union » en langage C:

Cette fonctionnalité s’approxime en langage C avecle mot cléunion(en)à condition d’y adjoindre une étiquette, mais cela n’offre pas les mêmes garanties (on peut lire et modifier un objet du type somme en faisant fi de son étiquette — quitte à provoquer desbugs):

typedefstruct{
enum{INT,FLOAT}tag;
union{
inti;
floatf;
};
}sum_t;

voidprint(sum_tx){
if(x.tag==INT)
printf("%i",x.i);
elseif(x.tag==FLOAT)
printf("%f",x.f);
}

La somme se généralise naturellement à un nombre quelconque d’opérandes. Dans le cas particulier de lasomme vide,le type est nommétype videet noté0:c’est l’élément neutre de la somme (etélément absorbantdu produit) et il ne contient aucune valeur.

Type énuméré

Untype énuméréreprésente unensemble fini,dont les éléments sont les différents constructeurs. Définir une fonction dessus revient à définir l’image de chaque élément, individuellement.

Exemple: type énuméré en OCaml:

On peut par exemple coder l’ensemble des quatrecouleurs d’un jeu de cartes classique:

typecouleur=Coeur|Carreau|Trefle|Pique

(* nom_de_la_couleur: couleur -> string *)
letnom_de_la_couleur=function
|Coeur->"♥ cœur"
|Carreau->"♦ carreau"
|Trefle->"♣ trèfle"
|Pique->"♠ pique"

Exemple: type énuméré en langage C:

Cette fonctionnalité se traduit en langage C par le mot‐cléenum:

typedefenum{COEUR,CARREAU,TREFLE,PIQUE}couleur;

char*nom_de_la_couleur(couleurc){
switch(c){
caseCOEUR:return"♥ cœur";
caseCARREAU:return"♦ carreau";
caseTREFLE:return"♣ trèfle";
casePIQUE:return"♠ pique";
}
}

Type algébrique

Untype algébriqueest une somme de produits, et généralise donc ces deux notions.

Ainsi, des cas spéciaux de types algébriques sont les types produits (un seul constructeur), les types sommes (un seul argument pour chaque constructeur) et les types énumérations (plusieurs constructeurs sans argument).

Exemple: type option et type résultat:

Lestypes options(en)sont des applications courantes de types algébriques. Ils permettent d’ajouter à un type donné une valeur spéciale, considérée comme « indéfinie » ou comme valeur d’erreur (l’équivalent denulldans certains langages de programmation), ce qui permet de définir des fonctions partielles de façon contrôlée.

La valeur spéciale est représentée par un constructeurNonequi ne prend aucun argument, tandis que les valeurs du type à compléter sont enveloppées dans un constructeurSome(qui prend donc un argument de ce type).

typeint_option=None|Someofint

(* division: int -> int -> int_option *)
letdivisionxy=
ify=0then
None
else
Some(x/y)

On peut perfectionner le mécanisme en agrémentant le cas d’erreur d’un message de description (donnée de typestring).

typeint_result=Resultofint|Errorofstring

(* division: int -> int -> int_result *)
letdivisionxy=
ify=0then
Error"division by zero"
else
Result(x/y)

Polymorphisme

Dans leslangagesqui les supportent, les types algébriques peuvent être(paramétriquement) polymorphes,ce qui permet laprogrammation générique.Ainsi, la définition d’un type algébrique peut être paramétrée par des variables de types.

On peut alors définir des fonctions génériques agissant sur de tels types polymorphes.

Exemple: type option polymorphe:

On peut rendre polymorphe la définition du type option vue précédemment. Ça s’écrit ainsi en langage OCaml (où'adénote une variable de type):

type'aoption=None|Someof'a

(** Utilisation d’instances du type polymorphe: **)

(* int_division: int -> int -> int option *)
letint_divisionxy=
ify=0then
None
else
Some(x/y)

(* float_division: float -> float -> float option *)
letfloat_divisionxy=
ify=0.0then
None
else
Some(x/.y)

(** Définition d’une fonction générique: **)

(* get_value: 'a -> 'a option -> 'a *)
letget_valuedefault_valueoptional_value=
matchoptional_valuewith
|None->default_value
|Somevalue->value

Récursivité

Listes

Un des exemples les plus importants de type algébrique est le typeliste,défini de façon récursive par deux constructeurs:

• Nil,aussi noté[],qui désigne la liste vide,
• etCons(abréviation de « constructeur »), aussi noté::ou:,qui désigne la combinaison d’un élément et d’une liste plus courte.

Par exemple,Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil))),aussi noté1:: 2:: 3:: 4:: [],est la liste constituée des quatre éléments 1, 2, 3, 4, dans cet ordre.

Toutes les opérations sur les listes se définissent alors par récurrence, en utilisant le filtrage par motif. Par exemple, pour calculer la longueur d’une liste:

• la longueur de la liste vide (Nil) est zéro,
• et la longueur d’une liste de la formeConsxsuiteest un plus la longueur de la listesuite.

Exemple: type liste en OCaml:

Cette définition se traduit ainsi en langage OCaml:

type'alist=
|Nil
|Consof'a*'alist

letlist1234=Cons1(Cons2(Cons3(Cons4Nil)))

letreclength=function
|Nil->0
|Consxs->1+lengths

Arbres

Les types algébriques permettent également de définir des structures d’arbres.Unarbre binairepeut se construire au moyen de deux constructeurs:

• Leafequi désigne une feuille d’étiquettee,
• etNodeegdqui désigne un nœud interne d’étiquettee,de fils gaucheget de fils droitd.

Par exemple,

Node 1
(Node 2
(Leaf 4)
(Node 5
(Leaf 6)
(Leaf 7)
)
)
(Leaf 3)

est l’arbre suivant:

1
/ \
2 3
/ \
4 5
/ \
6 7

Comme pour les listes, les opérations sur les arbres se définissent par récurrence. Par exemple, pour calculer la hauteur d’un arbre:

• la hauteur d’une feuille est un,
• et la hauteur d’un nœud interne est un plus le maximum de la hauteur de ses deux fils.

Exemple: type arbre binaire en OCaml:

Cette définition se traduit ainsi en langage OCaml:

typetree=
|Leafofint
|Nodeoftree*int*tree

letmy_tree=Node1(Node2(Leaf4)(Node5(Leaf6)(Leaf7)))(Leaf3)

letrecheight=function
|Leafe->1
|Nodeelr->1+max(heightl)(heightr)

Abstraction

Un type algébrique peut êtreabstrait:il suffit pour ça de ne pas exposer sa structure interne (ses constructeurs et leurs divers champs). Ainsi, il ne peut être manipulé que par les fonctions prévues à cet effet, et son implémentation peut être changée.

C’est une technique fréquente car les types algébriques permettent de réaliser des structures de données complexes.

Voir aussi

• Type
• Type récursif
• Filtrage par motif
• Enregistrement
• Énumération
• Type option(en)
• Liste
• Arbre

Notes & références

Références

• (en)Algebraic data typedansThe Free On-line Dictionary of Computing,rédacteur en chef Denis Howe.