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 compréhension. Comme cette construction offre des avantages de lisibilité et de concision, certains langages de programmation 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. C'est l'analogue de la définition d'un ensemble par compréhension que l'on note généralement ainsi:

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 x où x est un item de la liste des nombres naturels et x a son carré plus grand que 3."

Sommaire 1 Historique 2 Formes de compréhension 3 Compréhension de monade 4 Compréhension parallèle de liste 5 Voir aussi 6 Références 7 Liens externes

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 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 indéfini de qualifiants après le caractère pipe |. Un qualifiant peut être un générateur qui extrait des items d'une liste, tandis qu'une garde les filtre 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 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 de la théorie des ensembles et de l'algèbre relationnelle.

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 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.

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

• (en) Implantion d'une macro de compréhension en Lisp par Guy Lapalme

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

• Portail de l’informatique