Compréhensions de listes et récursion

Les listes de Python sont très versatiles ; elles sont beaucoup utilisées dans des situations dont le point commun est de nécessiter le stockage d’élements en séquence, c’est-à-dire avec un ordre donné.

On rappelle que les listes de Python sont des objets mutable (à l’opposé des tuples que l’on note avec une parenthèse) qui possèdent un grand nombre de méthodes de classe. Il existe de plus une manière très expressive de manipuler les listes : les compréhensions de listes (« list comprehension » en anglais).

Les schémas de manipulations les plus fréquents pour les listes sont:

• schémas de construction de liste de manière algorithmique, c’est-à-dire pas à partir d’une autre liste
• schémas de transformation en appliquant à chaque élement de la liste une fonction à un argument
• schémas de filtrage en sélectionnant les élements d’une liste avec une condition donnée agissant sur chaque élement de la liste (voir Logique, structures de contrôle et filtrage)
• schémas de réduction en réduisant l’information disponible dans la liste par une procédure algorithmique

Les compréhensions de liste permettent d’appliquer les trois premiers schémas de manière élégante, et surtout très intuitive à la lecture. Les schémas de réductions peuvent eux être généralisés à l’aide des fonctionnelles.

Schéma de construction

On peut créer une liste à partir d’un intervalle d’entiers en définissant la fonction suivante:

# definition de la fonction naturelsFor
def naturelsFor(a, b):
    ''' retourne une liste d'entiers [a,b[ '''
    listRes = []
    for k in range(a, b):
        listRes.append(k)
    return listRes

Pour vérifier le fonctionnement de la fonction, on peut utiliser l’instruction assert. Cette instruction vérifie que la fonction produit bien le résultat attendu. Si ce n’est pas le cas elle renvoie un message d’erreur, sinon elle ne renvoie rien:

assert naturelsFor(2,8) == [2, 3, 4, 5, 6, 7]
assert naturelsFor(-3,1) == [-3, -2, -1, 0]

Exercice

On rappelle que l’objet de type range est différent d’une liste (vu par ici). Pour le convertir en liste, on peut utiliser la fonction list(). Proposez un test de la fonction naturelsFor() avec assert, en comparant son résultat au résultat d’une liste construite avec range().

assert naturelsFor(-3,1) == list(range(-3,1))

Compréhension de liste

La fonction naturelsFor n’est pas optimisée du tout, et sa lecture est plutôt lourde. Elle peut se réduire à la simple ligne:

# definition de la fonction naturelsFor2
def naturelsFor2(a, b):
    ''' retourne une liste d'entiers [a,b[ '''
    return [k for k in range(a, b)]

# appel de la fonction
print(naturelsFor2(-3,1))

[-3, -2, -1, 0]

Ce qui est entre crochet [...] est une compréhension de liste. Elle peut se lire:

« Construit la liste des \(k\) pour \(k\) dans l’intervalle \([a, b[\) »

On dit que les compréhensions de liste ont un caractère déclaratif.

La syntaxe générale d’une compréhension de liste est la suivante:

[ <elem> for <var> in <seq> ]

où <var> est la variable de compréhension, <elem> est une expression appliquée aux valeurs successives de la variable <var> et <seq> est une expression qui retourne une séquence.

Exercice

Notez que <seq> peut être n’importe quelle séquence, ce qui inclue donc les chaînes de caractères str. A vous de faire des essais.

mot = "ABCDEFG"

Grâce à une compréhension de liste, créer une liste de chaîne de caractères à partir de la variable mot de la forme ['A0', 'B0', 'C0', ...]

[s+'0' for s in mot]

['A0', 'B0', 'C0', 'D0', 'E0', 'F0', 'G0']

Schéma de transformation

On a plusieurs choix pour utiliser un schéma de transformation. Ainsi, si l’on a défini la fonction

# definition de la fonction carre
def carre(x):
    ''' retourne le carre de x '''
    return x*x

alors, on peut écrire

[carre(k) for k in range(1, 7)]

[1, 4, 9, 16, 25, 36]

afin d’appliquer la fonction carre() à chaque entier compris dans \([1,7[\).

Exercice

Il est possible d’avoir une écriture encore plus compacte en utilisant les formes lambda. Proposez une alternative à la question précédente avec une forme lambda.

[(lambda x: x*x)(x) for x in range(1, 7)]

[1, 4, 9, 16, 25, 36]

Cependant, ce n’est pas optimal car dans ce cas, vous aller créer à la volée 6 formes lambda qui sont en fait les mêmes. Mais vous faites l’économie de nommer la fonction, ce qui peut-être le but.

La fonction map()

La fonction générique map() offre une alternative aux compréhensions de liste pour exprimer de façon concise des transformations de listes.

La fonction map() applique une fonction sur un objet, par exemple sur une liste:

map(lambda x : x*x, [1, 2, 3, 4, 5])

<map at 0x7fc07005d1d0>

map() renvoie un itérateur et non pas une liste. Un itérateur est une notion avancée de python que nous ne traiterons pas en détail ici. Afin de le transformer en liste, on peut utiliser la fonction list():

list(map(lambda x : x*x, [1, 2, 3, 4, 5]))

[1, 4, 9, 16, 25]

La forme lambda est bien adaptée dans ce cas.

Schéma de filtrage

On peut ajouter la possibilité de faire du filtrage sur les élements sur lesquels on itère dans <seq>. La syntaxe est la suivante:

[ <elem> for <var> in <seq> if <condition> ]

où <condition> est une expression booléenne portant sur la variable de compréhension, ici <var>. Dans cet exemple, on prend le carré de chaque élément de la liste, à condition que l’élément de la liste soit pair:

[k*k for k in range(1, 7) if k%2 == 0]

[4, 16, 36]

On peut donner une instruction alternative si la condition n’est pas remplie avec else. Par exemple, on applique la fonction carre pour les éléments pairs, et la fonction cube pour les éléments impairs:

[k*k if k%2 == 0 else k*k*k for k in range(1, 7)]

[1, 4, 27, 16, 125, 36]

Attention: dans ce cas les instruction if ... else sont placées avant l’instruction for.

Exercice

mot = "vwsxyazvxlwyzuvwxtxv wxycv'wxezyvxyszwtxyz zywvcvwzoywzovxlwzy"

A l’aide d’une compréhension de liste conditionnelle, créer une liste de toutes les lettres strictement inférieures à 'v' de la variable mot.

print([s for s in mot if s < 'v'])

['s', 'a', 'l', 'u', 't', ' ', 'c', "'", 'e', 's', 't', ' ', 'c', 'o', 'o', 'l']

Compréhension multiple

Pour achever cette présentation, on peut utiliser des compréhensions multiples. Par exemple:

[(i, j) for i in range(1, 4) for j in range(i, 4)]

[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

Récursion

Une fonction peut en appeler une autre, et peut donc s’appeler elle-même! C’est ce que l’on appelle une fonction récursive, et cela permet de créer des fonctions très ingénieuse.

Regardez par exemple cette fonction de signature compte-à-rebours(n):

# definition de la fonction de compte-a-rebours
def compte_a_rebours(n):
    ''' affiche un compte-a-rebours a partir de n '''
    if n <= 0:
        print('Partez !')
    else:
        print(n)
        compte_a_rebours(n-1)

Si la variable n est inférieur ou égale à 0, la fonction affiche Partez !, sinon elle affiche la valeur de n et elle appelle la fonction compte_a_rebours, c’est-à-dire elle-même, avec l’argument n-1.

Par exemple:

compte_a_rebours(3)

3
2
1
Partez !