Compréhension de liste - Définition

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

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 (lien) et ont été implantées dans le langage de requête de base de données Kleisli (lien).

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.