Liste en compréhension
# 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 :

    $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 x où x est un élément 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) 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 et ont été implantées dans le langage de requête de base de données Kleisli.

## Formes de compréhension

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 :

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, ainsi l'exemple précédent s'exprime de manière presque équivalente :

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

    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.

