La compréhension de liste en Python, une syntaxe moderne pour map() et filter()

La compréhension de liste est un syntactic sugar pour les fonctions classiques de la programmation fonctionnelle que sont map() et filter(). Disponible depuis Python 2.0, la compréhension de liste devrait à terme amener à la disparition des fonctions map() et filter() du langage Python, ce que Guido van Rossum avait déjà envisagé pour Python 3.

Ainsi, si vous avez du “vieux code” utilisant ces fonctions, je vous encourage à le porter vers cette nouvelle syntaxe beaucoup plus lisible et plus pythonique. J’espère que cet article pourra aider certains à éviter les pièges qui pourraient apparaître devant eux lors de cette démarche.

map()
Commençons d’abord par la fonction map(), dont la syntaxe est map(fonction, liste). Prenons un exemple très simple, avec une fonction anonyme lambda qui à tout x élément de la liste des chiffres de 0 à 9 associe 2 fois x.

>>> map(lambda x: 2*x, range(10))
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

On obtient l’équivalent de la fonction map() avec une compréhension de liste de la forme [fonction(x) for x in liste], ce qui donne pour notre exemple :

>>> [2*x for x in range(10)]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

filter()
La syntaxe de la fonction filter() est filter(fonction, liste). Prenons ici aussi un exemple très simple, avec une fonction anonyme lambda qui n’est Vrai pour chaque x élément de la liste des chiffres de 0 à 9 que s’il est strictement supérieur à 5.

>>> filter(lambda x: x>5, range(10))
[6, 7, 8, 9]

On obtient l’équivalent de la fonction filter() avec une compréhension de liste de la forme [x for x in liste if fonction(x)], et donc notre exemple devient :

>>> [x for x in range(10) if x>5]
[6, 7, 8, 9]

Un des grands intérêts des fonctions est de pouvoir être composées. Cependant, cette opération de composition n’est pas anodine, et il faut bien envisager les différents cas pour ne pas commettre d’erreur.

map o filter()
La composition notée map o filter() revient à map(filter()), c’est-à-dire à appliquer d’abord la fonction filter(), puis la fonction map(). Si nous combinons nos deux premiers exemples, nous obtenons :

>>> map(lambda x: 2*x, filter(lambda x: x>5, range(10)))
[12, 14, 16, 18]


On obtient l’équivalent de la composition de fonction map o filter() avec une compréhension de liste de la forme [fonction_map(x) for x in liste if fonction_filter(x)], ce qui donne ici :

>>> [2*x for x in range(10) if x>5]
[12, 14, 16, 18]

La composition de fonction map o filter() ne pose pas de problème.

On remarque que plus l’on compose des fonctions map() et filter(), plus l’avantage syntaxique de lisibilité et de compréhensibilité des compréhensions de liste augmente.

filter o map()
Mais qu’en est-il de la composition notée filter o map(), qui revient à filter(map()), c’est-à-dire à appliquer d’abord la fonction map(), puis la fonction filter(). Si nous combinons ici aussi nos deux premiers exemples, nous obtenons :

>>> filter(lambda x: x>5, map(lambda x: 2*x, range(10)))
[6, 8, 10, 12, 14, 16, 18]

Le résultat retourné est différent de celui obtenu à l’exemple précédent avec une compréhension de liste de la forme [fonction_map(x) for x in liste if fonction_filter(x)]. En fait, la bonne compréhension de liste est :

>>> [2*x for x in range(10) if 2*x>5]
[6, 8, 10, 12, 14, 16, 18]

Nous voyons que la composition de fonction filter o map() pose des problèmes, et qu’il faudra y porter une attention particulière en cas de conversion de vieux code fonctionnel en compréhensions de liste.

filter o filter()
La composition notée filter o filter() revient à filter(filter()), c’est-à-dire à appliquer deux fois de suite la fonction filter(). Nous allons donc rajouter une deuxième condition à notre premier exemple de filter(), qui sera que chaque élément x devra en plus être strictement inférieur à 8.

>>> filter(lambda x: x<8, filter(lambda x: x>5, range(10)))
[6, 7]

Le même résultat est obtenu en inversant l’ordre des deux conditions :

>>> filter(lambda x: x>5, filter(lambda x: x<8, range(10)))
[6, 7]

La composition filter o filter() est commutative, et peut en fait facilement se factoriser sous la forme :

>>> filter(lambda x: x>5 and x<8, range(10))
[6, 7]

On obtient l’équivalent de la composition de fonction filter o filter() avec une compréhension de liste de la forme [x for x in liste if fonction_filter_1(x) and fonction_filter_2(x)], ce qui donne ici :

>>> [x for x in range(10) if x>5 and x<8]
[6, 7]

La composition de fonction filter o filter() ne pose pas de problème.

map o map()
Mais qu’en est-il de la composition notée map o map(), qui revient à map(map()), c’est-à-dire à appliquer deux fois de suite la fonction map() ? Rajoutons une deuxième fonction à notre premier exemple de map(), qui à chaque x associera x plus 1.

>>> map(lambda x: x+1, map(lambda x: 2*x, range(10)))
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et

>>> map(lambda x: 2*x, map(lambda x: x+1, range(10)))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

ne donnent pas les mêmes résultats. La composition map o map() n’est pas commutative. On obtient l’équivalent de la composition de fonction map o map() avec une compréhension de liste de la forme [fonction_map_2(x) for x in [fonction_map_1(x) for x in liste]], ce qui donne ici :

>>> [x+1 for x in [2*x for x in range(10)]]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et

>>> [2*x for x in [x+1 for x in range(10)]]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Il est possible de factoriser les deux fonctions map() comme nous l’avons fait pour les fonctions filter(), mais il faut faire très attention à l’ordre de composition des fonctions. Dans le premier cas on a (2*x)+1 = 2*x+1 qui donne :

>>> [2*x+1 for x in range(10)]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

et dans le deuxième cas on obtient 2*(x+1) = 2*x+2 qui produit :

>>> [2*x+2 for x in range(10)]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Nous voyons que la composition de fonction map o map() pose des problèmes.

Pour ne pas tomber dans des pièges, il suffit de retenir que toutes les compositions de fonctions qui commencent par une fonction map() sont dangereuses, alors que celles commençant par une fonction filter() sont sans danger.

Pour mon plus grand bonheur, la syntaxe de compréhension de liste rend particulièrement pythonique et centrale au langage Python une partie de la sémantique de la programmation fonctionnelle qui y était jusqu’à présent mal intégrée et mal aimée. Encore une fois, et même si certains de mes professeurs d’informatique ne l’ont jamais accepté, sans une bonne syntaxe, une sémantique géniale n’est rien.

Tags: , , ,

6 Responses to “La compréhension de liste en Python, une syntaxe moderne pour map() et filter()”

  1. À propos de la commutativité de la composition de deux “filter()” : oui et non. En fait, la liste produite sera toujours la même, mais pas forcément au même coût. Si l’un des deux tests est plus coûteux que l’autre, il faut le faire dans le filter “externe” pour l’appliquer sur une liste déjà réduite.

    • Yoko says:

      Pas forcément, le and de python est paresseux donc il suffit de trier les tests du moins couteux au plus couteux de gauche à droite dans le if.

      Il faut aussi tenir compte de la probabilité des tests en mettant le test qui filtre le plus (qui retire le plus d’éléments) à gauche d’un test de même coût qui filtre moins.

      Un exemple qui na pas de sens mais qui illustre ça :

      [x for x in range(1000) if x%2==0 and sha1(x)%8 != 1]

      Le premier test enlève la moitié des éléments (statistiquement parlant) alors que le second en enlève 1 / 10. Par contre le premier test est très léger alors que le second est très lourd.

      Note : Je ne connais pas les API python le code n’est qu’un exemple pour donner une idée.

      • Oui, c’est ce que je disais : ça mimique exactement la construction du double filter. Autrement dit, ce n’est pas commutatif si on prend en compte la complexité qui change.

  2. Yoko says:

    Merci pour cet article intéressant néanmoins je trouve que la technique pour remplacer filter(map()) n’est pas bonne. En effet elle demande à dupliquer l’application de la lambda fonction du map à 2 endroits (une fois dans la condition et une fois dans le “renvoie” de la variable).

    Ça pose des problèmes de maintenabilité important et ça brise le “don’t repeat your self”. Je préfère encore utiliser une méthode map avec une compréhension de liste ou deux compréhension de listes.

  3. Carl Chenet says:

    Article très intéressant qui a le mérite d’expliquer clairement une notion-clé du langage Python qu’est la compréhension de liste.

  4. […] compréhension de liste est une syntaxe moderne remplaçant les classiques fonctions map() et filter() de la programmation fonctionnelle. Ce sucre […]

Leave a Reply