Comprehension de liste


Comprehension de liste

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:

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

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:

Python:

Common Lisp

Axiom:

  • Exemples de stream Axiom: [5]

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Compr%C3%A9hension de liste ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Comprehension de liste de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • Liste De Prénoms Arabes — Les noms et prénoms arabes ont tous une signification. Contrairement aux langues latines, il n’existe pas en arabe de distinctions entre noms communs et noms propres ; un prénom et un nom sont en arabe des mots sans catégorisation… …   Wikipédia en Français

  • Liste de prenoms arabes — Liste de prénoms arabes Les noms et prénoms arabes ont tous une signification. Contrairement aux langues latines, il n’existe pas en arabe de distinctions entre noms communs et noms propres ; un prénom et un nom sont en arabe des mots sans… …   Wikipédia en Français

  • Liste des prénoms arabes — Liste de prénoms arabes Les noms et prénoms arabes ont tous une signification. Contrairement aux langues latines, il n’existe pas en arabe de distinctions entre noms communs et noms propres ; un prénom et un nom sont en arabe des mots sans… …   Wikipédia en Français

  • Liste Chaînée — Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque élément permet …   Wikipédia en Français

  • Liste chainee — Liste chaînée Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque… …   Wikipédia en Français

  • Liste chainée — Liste chaînée Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque… …   Wikipédia en Français

  • Liste doublement chaînée — Liste chaînée Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque… …   Wikipédia en Français