Type algébrique

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 , et Cons (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)) et 1:[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 et Node 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 exemple Leaf a un type fonctionnel Int -> Tree. Cela signifie qu'étant donné un entier comme argument à Leaf produit une valeur de type Tree. Comme Node prend deux arguments dy type Tree 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 fonction depth peut être aussi construit pour chacun d'eux pour traiter tous les cas. Dans les cas de Node, le motif extrait les sous-arbres l and r pout un traitement ultérieur.

Voir aussi

Référence


  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Type alg%C3%A9brique de donn%C3%A9es ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Type algébrique de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Type algebrique de donnees — 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… …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • Algebrique — Algébrique Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Type recursif — Type récursif Dans un langage de programmation, un type récursif ou type inductif est un type de données pour des valeurs qui contiennent d autres valeurs du même type. Un exemple est le type liste en Haskell : data List a = Nil | Cons a… …   Wikipédia en Français

  • Algébrique — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Algébrique », sur le Wiktionnaire (dictionnaire universel) Courbe algébrique Clôture algébrique Type… …   Wikipédia en Français

  • Type récursif — Dans un langage de programmation, un type récursif ou type inductif est un type de données pour des valeurs qui contiennent d autres valeurs du même type. Cette notion s applique naturellement dans l étude des listes et des arbres. Sommaire 1… …   Wikipédia en Français

  • GÉOMÉTRIE ALGÉBRIQUE — Sous sa forme actuelle, la géométrie algébrique est une branche de l’algèbre relativement récente (cf. ALGÈBRE, DEDEKIND). Pour «comprendre» les phénomènes d’intersection des courbes et des surfaces, il s’est révélé nécessaire d’élaborer des… …   Encyclopédie Universelle

  • Groupe algébrique — En géométrie algébrique, la notion de groupe algébrique est un équivalent des groupes de Lie en géométrie différentielle ou complexe. Un groupe algébrique est une variété algébrique munie d une loi de groupe compatible avec sa structure de… …   Wikipédia en Français

  • TOPOLOGIE - Topologie algébrique — Inventée au début du XXe siècle pour résoudre des problèmes géométriques, la topologie algébrique connut un grand développement grâce à l’introduction de constructions algébriques de plus en plus abstraites. Pour clarifier l’exposé, on a… …   Encyclopédie Universelle

  • Groupe Algébrique — En géométrie algébrique, la notion de groupe algébrique est un équivalent des groupes de Lie en géométrie différentielle ou complexe. Un groupe algébrique est une variété algébrique munie d une loi de groupe compatible avec sa structure de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”