- Liste en compréhension
-
En programmation informatique, la syntaxe de certains langages de programmation permet de définir des listes en compréhension, c'est-à-dire des listes dont le contenu est défini par filtrage du contenu d'une autre liste selon un principe analogue à celui de la définition par compréhension de la théorie des ensembles. Cette construction syntaxique se distingue de la construction la plus courante dans les langages de programmation qui est de définir les listes par énumération de ses éléments.
Cette construction syntaxique offre des avantages de lisibilité et de concision et se rapproche de la notation utilisée en mathématique:
En langage de programmation Haskell, la syntaxe est la suivante :
- S = [ x | x←[0..], x^2>3 ]
La liste
[0..]représente la liste des entiers naturels etx^2>3répresente la propriété caractéristique de la liste. Cela peut être lu comme suit : "S est la liste de tous les x où x est un item de la liste des nombres naturels et x a son carré plus grand que 3."Sommaire
Historique
Le premier langage de programmation à 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 de base de données [1] et ont été implantées dans le langage de requête de base de données Kleisli [2].
Formes de compréhension
En langage de programmation Haskell, les compréhensions de liste sont des expressions qui peuvent contenir les fonctions d'ordre supérieur
mapetfilter.Par exemple :
s = filter (\x -> x^2 > 3) [0..] -- ou s = [x | x <- [0..], x^2 > 3]
Dans ce langage, la syntaxe de la compréhension de liste utilise après la barre verticale
|une suite de qualifiants. Un qualifiant a deux parties:- un générateur qui extrait des éléments d'une liste,
- une garde qui filtre les éléments extraits.
Le langage de programmation 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) # A cause de l'évaluation stricte (c'est-à-dire non paresseuse) les listes en Python doivent être finies, par exemple la liste de 0 à 99 s = [x for x in L 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 compilateur 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 barres "|" 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]
La liste résultante contiendra des paires, composées d'éléments des listes a et b. Pour chaque élément de a, un élément de b est utilisé à son tour pour obtenir toutes les combinaisons possibles de a et de b (produit cartésien).
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 la liste résultante ne contiendra pas toutes les combinaisons. Au lieu de cela, la première branche produit un élément à partir de a et la seconde branche à partir de b. Le résultat est alors une suite de paires composées chacune d'une moitié a et une moitié b, comme si les deux listes a et b avaient été juxtaposées.
Considérant une réécriture de fonctions d'ordre supérieur, une compréhension parallèle ajoute zipwith aux map et filter précédents. L'exemple de compréhension parallèle pourrait être simplement réécrit comme suit :[précision nécessaire]
- 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.[précision nécessaire]
Voir aussi
- Générateur (informatique) pour d'autres constructions gérant des séquences.
- Monade (informatique) pour les monades et leur notation en général.
- pour d'autres constructions de langage informatique :
- Garde (informatique)
- Filtrage par motif
- Opérateur (programmation)
Références
- List Comprehension dans The Free On-line Dictionary of Computing, Éditeur Denis Howe.
- Philip Wadler [3] Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming langages : bulk types & persistent data: bulk types & persistent data, Nafplion, Greece, Pages 55–68, 1992.
- Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
- Limsoon Wong [4] The Functional Guts of the Kleisli Query System, International Conference on Functional Programming, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, Pages 1–10, 2000.
Haskell:
- (en) Le rapport Haskell 98, chapitre 3.11 List Comprehensions.
- (en) The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions.
- (en) Le manuel utilisateur de Hugs 98, chaptitre 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions).
Python:
- (en) Python Reference Manual, chapitre 5.2.4 List displays.
- (en) Python Enhancement Proposal PEP 202: List Comprehensions.
- (en) Python Reference Manual, chapitre 5.2.5 Generator expressions.
- (en) Python Enhancement Proposal PEP 289: Generator Expressions.
Common Lisp
Axiom:
- Exemples de stream Axiom: [5]
Liens externes
- (en) Opérations d'ensemble à la SQL avec des unilignes de compréhension de liste dans Python Cookbook
Wikimedia Foundation. 2010.
