Liste en intension – comprehension list

La définition de listes en intension en sciences informatique – et plus précisément en programmation –  est une manière de construire des listes, des tableaux, des sets, des tuples ou tout autres types de séquences itérables à la façon dont sont définis les ensembles en compréhension en mathématique.

L’avantage principal de cette technique réside dans son aspect fonctionnel. Elle apporte aussi une écriture plus simple, plus courte et facilement lisible par un humain pour construire des séquences plus ou moins complexes.

La définition d’un ensemble par compréhension en mathématiques

Il s’agit d’une opération de construction d’un set à partir d’un autre set pour lequel une propriété est définie sur l’ensemble des ces éléments.

Formellement il s’agit de la description d’un ensemble sous la forme [1] :

\{x \in E\ |\ P(x) \}

Avec E un ensemble déjà existant et P(x) une propriété définie sur tout les éléments de E.

Cette notation se nomme Set Builder notation[1] en anglais.

Plus simplement, il s’agit de convenir d’un ensemble et d’en extraire des éléments – ou éventuellement une image de ces éléments – qui respectent un prédicat (la propriété) pour construire un nouvel ensemble.

Application en programmation

Ce principe peut être utilisé pour créer des listes ou tout autre type de séquences rapidement et efficacement en une seule ligne de code. Même si la syntaxe diffère selon le langage de programmation choisi, elle est généralement assez semblable à la syntaxe mathématique. Cette fonctionnalité assure qu’aucune des variables entré en paramètre ne sera mutée durant le processus de construction.

La syntaxe générale correspond à :

<mapping> for <element> in <sequence> <predicat>

Ce qui se lit : Dans une séquence on applique une transformation aux éléments qui respectent le prédicat.

Création d’un ensemble fini

Python

L’ensemble en compréhension

\{ x \in \mathbb{N}\ |\ 0 \leq x < 10, x\ pair\}

est défini par (pour créer une liste)

[x for x in range(10) if x % 2 == 0]

Ce qui donne

[0, 2, 4, 6, 8]

ou par (pour créer un ensemble)

{x for x in range(10) if x % 2 == 0}

Ce qui donne

{0, 2, 4, 6, 8}

ou par (pour créer un générateur)

(x for x in range(10) if x % 2 == 0)

L’exemple ci-dessus produit un générateur ce qui permettra une évaluation pas à pas lors de l’itération. Les valeurs sont ainsi produites au fur et à mesure lors de l’itération, il s’agit d’un moyen de faire de l’évaluation différé.

Haskell

Non défini

C#

L’ensemble en compréhension

\{ x \in \mathbb{N}\ |\ 0 \leq x < 10, x\ pair\}

est défini par

Première notation

Enumerable.Range(0, 10).Where((x) => x % 2 == 0).Select((x) => x);

Deuxième notation

from x in Enumerable.Range(0, 10) where x % 2 == 0 select x;

Ce qui donne

[0, 2, 4, 6, 8]

Création d’un ensemble infini

Dans les exemples précédents les ensembles sont bornés, en d’autre mots, les ensembles auxquels on extrait des valeurs sont des ensembles finis. Il est possible de réaliser une compréhension sur un ensemble infini à condition que celle-ci soit évaluée tardivement (lazy evaluation), par exemple grâce à la création d’un générateur. Dans le cas contraire, le programme se bloquerait dans un cycle infini.

Python

On désire construire l’ensemble suivant

\{ x \in \mathbb{N}\ |\ x\ pair\}

qui est défini par

e = (x*2 for x in itertools.count())

les valeurs sont extraites ainsi

ex = itertools.islice(e, 10) #extraction des 10 premières valeurs de notre séquence infinie
print(list(ex)) #conversion en liste et affichage

Ce qui donne

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Ainsi itertools.count() représente l’ensemble \mathbb{N} des entiers naturels positifs. La variable e représente – à travers son itérateur – l’ensemble des nombres pairs de 0 à +\infty .

L’utilisation des compréhensions appliqués à la programmation est une manière élégante et simple de représenter et de construire une séquence à partir d’une autre séquence.

Références :

[1] Set-builder notation : https://en.wikipedia.org/wiki/Set-builder_notation

A voir :

Nombres premiers : http://www.python-course.eu/list_comprehension.php

 


Laisser un commentaire