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 en 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ématiques :
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 et x^2>3
représente 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 élément de la liste des nombres naturels et x a son carré plus grand que 3. »
Historique
modifierLe 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) en 1977.
Dans le système de calcul formel AXIOM, une construction du même genre gère les flux (ou 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
modifierEn langage de programmation Haskell, les compréhensions de liste sont des expressions qui peuvent contenir les fonctions d'ordre supérieur map
et filter
.
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[3], ainsi l'exemple précédent s'exprime de manière presque équivalente :
# À cause de l'évaluation stricte (c'est-à-dire non paresseuse),
# les listes en Python doivent être finies,
# par exemple ici la liste de 0 à 99:
L = range(100)
s = [x for x in L if x**2 > 3]
Compréhension de monade
modifierComme 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
modifierUne 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
modifierArticles connexes
modifier- 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 :
Liens externes
modifier- (en) Opérations d'ensemble à la SQL avec des unilignes de compréhension de liste dans Python Cookbook
Références
modifier- Phil Trinder, « Comprehensions, a query notation for DBPLs », DBPL3 Proceedings of the third international workshop on Database programming languages, , p. 55–68 (lire en ligne)
- Limsoon Wong, « The functional guts of the Kleisli query system », Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, (lire en ligne)
- « La compréhension de liste en Python, une syntaxe moderne pour map() et filter() », Florent Gallaire's Blog, 5 décembre 2011.
- « List Comprehension »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le ) dans The Free On-line Dictionary of Computing, Éditeur Denis Howe.
- Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
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 »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le ).
- (en) Le manuel utilisateur de Hugs 98, chaptitre « 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions) »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le ).
Python:
- (en) Python Reference Manual, chapitre 5.1.4. List Comprehensions.
- (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: « http://page.axiom-developer.org/zope/mathaction/Streams »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le )