Liste en compréhension

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Compréhension de liste)
Aller à : navigation, rechercher

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ématiques :

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

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

Historique[modifier | modifier le code]

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) 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[modifier | modifier le code]

En 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Phil Trinder, « Comprehensions, a query notation for DBPLs », DBPL3 Proceedings of the third international workshop on Database programming languages,‎ 1992, p. 55–68 (lire en ligne)
  2. Limsoon Wong, « The functional guts of the Kleisli query system », Proceedings of the fifth ACM SIGPLAN international conference on Functional programming,‎ 2000 (lire en ligne)
  3. La compréhension de liste en Python, une syntaxe moderne pour map() et filter()
  • List Comprehension 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:

Python:

Common Lisp

Axiom:

  • Exemples de stream Axiom: [1]