- Type algébrique
-
Type algébrique de données
Un type algébrique de données est un type de données dont chacune des valeurs est une donnée d'un autre type enveloppée dans un des constructeurs du type. Toutes les données enveloppées sont des arguments du constructeur. Par contraste aux autres types de données, le constructeur n'est pas exécuté et la seule manière d'opérer sur les données est d'enlever le constructeur en utilisant le filtrage par motif.
Le type algébrique de données le plus répandu est une liste avec deux constructeurs :
Nil
et[]
pour une liste vide , etCons
(une abréviation pour constructor),::
, et:
pour la combinaison d'un élément avec une liste plus courte (par exemple(Cons 1 '(2 3 4))
et1:[2,3,4]
).Des cas spéciaux de types algébriques sont des types produit (un seul constructeur) et les types énumération (plusieurs constructeurs sans argument). Les types algébriques sont une forme de type composite; c’est-à-dire un type formé en combinant plusieurs autres types.
Un type algébrique de donnée peut être aussi un type abstrait de données (sigle anglais : ADT) s'il est exporté à partir d'un module sans ses constructeurs. Les valeurs d'un tel type peuvent être manipulées seulement avec des fonctions définies dans le même module que le type lui-même.
En théorie des ensembles l'équivalent d'un type algébrique de données est la réunion disjointe (ou somme ensembliste), une réunion dont les éléments communs sont en quelque sorte dupliqués. Formellement, les éléments dupliqués sont distingués par l’adjonction d’un marqueur (l'équivalent d'un constructeur) identifiant l’ensemble d’origine de l’élément. La construction est généralisée en rendant obligatoire le marqueur pour tous les éléments, même ceux dont le type pourrait être laissé implicite.
Un exemple
En Haskell on peut définir un nouveau type algébrique de données,
Tree
:data Tree = Empty | Leaf Int | Node Tree Tree
ou dans la syntaxe OCaml :
type tree = Empty | Leaf of int | Node of tree * tree
Ici,
Empty
,Leaf
etNode
sont des constructeurs. De manière similaire à une fonction, un constructeur est appliqué aux arguments du type approprié, donnant une instance du type de données auquel le constructeur appartient. Par exempleLeaf
a un type fonctionnelInt -> Tree
. Cela signifie qu'étant donné un entier comme argument àLeaf
produit une valeur de typeTree
. CommeNode
prend deux arguments dy typeTree
lui-même, le type est type récursif.Les opérations sur les types algébriques de données peuvent être définies par le filtrage par motif pour retrouver les arguments. Par exemple, considérons une fonction pour calculer la profondeur d'une
Tree
:depth :: Tree -> Int depth Empty = 0 depth (Leaf n) = 1 depth (Node l r) = 1 + max (depth l) (depth r)
Donc, un
Tree
donné à la fonctiondepth
peut être aussi construit pour chacun d'eux pour traiter tous les cas. Dans les cas deNode
, le motif extrait les sous-arbresl
andr
pout un traitement ultérieur.Voir aussi
Référence
- Algebraic data type in The Free On-line Dictionary of Computing, Editor Denis Howe.
- Portail de l’informatique
Catégories : Programmation fonctionnelle | Théorie des types
Wikimedia Foundation. 2010.