Compréhension de liste - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

Une liste, comme un ensemble, peut-être définie par la donnée d'une propriété caractéristique de ses éléments, on dit qu'on l'a définie en compréhension. Comme cette construction offre des avantages de lisibilité et de concision, certains langages de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).) proposent donc la possibilité de définir une liste par une propriété caractéristique et l'on appelle cela la compréhension de liste (Une liste, comme un ensemble, peut-être définie par la donnée d'une propriété caractéristique de ses éléments, on dit qu'on l'a définie en...). C'est l'analogue de la définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) par compréhension que l'on note généralement ainsi:

S=\{x|x \in \mathbb{N}, x^2>3\}

En langage Haskell, la syntaxe de compréhension de liste est :

 
 S = [ x | x<-[0..], x^2>3 ] 
 

La liste [0..] représente la liste des entiers naturels et x^2>3 répresente la propriété caractéristique de la liste. Cela peut être lu comme suit : "S est la liste de tous les xx est un item de la liste des nombres (Ceci est une liste d'articles concernant les nombres.) naturels et x a son carré (Un carré est un polygone régulier à quatre côtés. Cela signifie que ses quatre côtés ont la même longueur et ses quatre angles la même mesure. Un carré est à la...) plus grand que 3."

Historique

Le premier langage de programmation (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine, généralement un ordinateur. Le code source subit...) à proposer des définitions par compréhension est SETL. La première référence à la définition par compréhension appliquée aux listes est due à Rod Burstall et John Darlington dans la description de leur langage de programmation NPL en 1977. Dans le système de calculs algébriques AXIOM (voir l'article en anglais sur AXIOM), une construction du même genre gère les streams qui peuvent être vus comme des listes infinies.

Les compréhensions ont été proposées comme une notation de requête (Le mot requête, synonyme de demande, est employé dans les domaines suivants :) de base de données (En informatique, une base de données (Abr. : « BD » ou « BDD ») est un lot d'informations stockées dans un dispositif informatique. Les technologies existantes permettent...) (lien) et ont été implantées dans le langage de requête de base de données Kleisli (lien).

Formes de compréhension

En Haskell, les compréhensions de liste peuvent être aussi écrites comme des expressions contenant les fonctions d'ordre supérieur map et filter. Ainsi, S peut être aussi écrit ainsi :

 
 S = filter (\x -> x^2 > 3) [0..] 
 

Néanmoins, en Haskell la syntaxe de compréhension de liste permet un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) indéfini de qualifiants après le caractère pipe (La pipe est un objet servant à fumer (tabac, opium...). Elle est en général composée de deux parties : le fourneau (il contient le tabac) et le tuyau....) |. Un qualifiant peut être un générateur qui extrait des items d'une liste, tandis qu'une garde les filtre (Un filtre est un système servant à séparer des éléments dans un flux.) ou il peut être une déclaration locale avec let.

Le langage Python propose aussi une syntaxe pour exprimer la compréhension de liste, ainsi l'exemple précédent s'exprime de manière presque équivalente :

 
 L = range(100) #  Les listes en Python doivent être finies à cause de l'absence d'évaluation paresseuse. Donc la liste va de  0 à 99 
 S = [x for x in L if x**2 > 3] 
 

Une expression génératrice peut être utilisée en Python 2.4 pour achever une équivalent fonctionnelle (En mathématiques, le terme fonctionnelle se réfère à certaines fonctions. Initialement, le terme désignait les fonctions qui en prennent d'autres en argument. Aujourd'hui, le terme a...) avec S par un générateur pour itérer sur une liste infinie :

 
 from itertools import count 
 S = [x for x in count() if x**2 > 3] 
 

Compréhension de monade

Comme une liste est une monade particulière, il est naturel de généraliser la compréhension à une monade quelconque, ce que fait Haskell.

Compréhension parallèle de liste

Une extension du Glasgow Haskell Compiler est la compréhension parallèle de liste (appelée aussi compréhension zip). elle permet plusieurs branches indépendantes de qualifiants. Là où les qualifiants séparés par des virgules sont dépendants, les branches séparées par des pipes sont évaluées en parallèle. Considérons d'abord la compréhension de liste avec les qualifiants dépendants conventionnels :

 
 [(x,y) | x <- a, y <- b] 
 

Cela prend des items des listes a et bet produit une liste de paires d'items. Pour chaque item de a, chaque item de b est utilisé à son tour pour obtenir toutes les combinaisons d'items. Le cas particulier est le produit cartésien (En mathématiques, le produit cartésien de deux ensembles X et Y est l'ensemble de tous les couples, dont la première composante appartient à X et la seconde à Y. On généralise facilement la notion de produit cartésien binaire à...) de la théorie des ensembles (La théorie des ensembles est une branche des mathématiques créée initialement par le mathématicien allemand Georg Cantor à la fin du...) et de l'algèbre relationnelle (L'algèbre relationnelle est un concept mathématique de relation de la théorie des ensembles.).

Maintenant, considérons la compréhension de liste avec des qualifiants différents fournis par l'extension :

 
 [(x,y) | x <- a | y <- b] 
 

La différence est que cela ne fournit pas toutes les combinaisons. Au lieu de cela, la première branche produit un item à partir de a et la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La...) branche à partir de b, et le résultat est l'appariement de chaque item de a et de chaque item de b. Cela ressemble à un zipper qui aligne les items des deux listes.

Considérant une réécriture de fonctions d'ordre supérieur, une compréhension parallèle ajoute zipwith aux mapet filter précédents. L'exemple de compréhension parallèle pourrait être simplement réécrit comme suit :

 
 zipWith (,) a b 
 

Dans le cas général, chaque branche parallèle peut être réécrite en une compréhension de liste séparée. Le résultat est zippé en une liste alignée, et les autres compréhensions de liste la transforment en la liste résultat.

Cet article vous a plus ? Partagez-le sur les réseaux sociaux avec vos amis !
Page générée en 0.066 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique