Itérables

Un itérable est un objet dont on peut parcourir les valeurs, à l’aide d’un for par exemple. La liste que nous venons d’implémenter est un exemple d’itérable.

Les types str, tuple, list, dict et set sont d’autres itérables bien connus. Un grand nombre d’outils Python que nous verrons par la suite travaillent avec des itérables, il est donc intéressant d’en tirer profit.

L’objectif de ce chapitre va être de comprendre ce qu’est un itérable, et comment en implémenter un.

for for lointain

Les itérables et le mot-clef for sont intimement liés. C’est à partir de ce dernier que nous itérons sur les objets.

Mais comment cela fonctionne en interne ? Je vous propose de regarder ça pas à pas, en nous aidant d’un objet de type list.

1
>>> numbers = [1, 2, 3, 4, 5]

La première opération réalisée par le for est d’appeler la fonction iter avec notre objet. iter retourne un itérateur. L’itérateur est l’objet qui va se déplacer le long de l’itérable.

1
2
>>> iter(numbers)
<list_iterator object at 0x7f26896c0940>

Puis, pas à pas, le for appelle next en lui précisant l’itérateur.next fait avancer l’itérateur et retourne la nouvelle valeur découverte à chaque pas.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
>>> iterator = iter(numbers)
>>> next(iterator)
1
>>> next(iterator)
2
>>> next(iterator)
3
>>> next(iterator)
4
>>> next(iterator)
5
>>> next(iterator)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Qu’est-ce que ce StopIteration ? Il s’agit d’une exception, levée par l’itérateur quand il arrive à sa fin, qui signifie que nous en sommes arrivés au bout, et donc que la boucle doit cesser. for attrape cette exception pour nous, ce qui explique que nous ne la voyons pas survenir dans une boucle habituelle.

Ainsi, le code suivant :

1
2
for number in numbers:
    print(number)

Peut se remplacer par celui-ci :

1
2
3
4
5
6
7
iterator = iter(numbers)
while True:
    try:
        number = next(iterator)
    except StopIteration:
        break
    print(number)

En interne, iter fait habituellement appel à la méthode __iter__ de l’itérable, et next à la méthode __next__ de l’itérateur. Ces deux méthodes ne prennent aucun paramètre. Ainsi :

  • Un itérable est un objet possédant une méthode __iter__1 retournant un itérateur ;
  • Un itérateur est un objet possédant une méthode __next__ retournant la valeur suivante à chaque appel, et levant une exception de type StopIteration en fin de course.

La documentation Python indique aussi qu’un itérateur doit avoir une méthode __iter__ où il se retourne lui-même, les itérateurs étant ainsi des itérables à part entièe.

Le cas des indexables

En début du chapitre, j’ai indiqué que notre liste Deque était aussi un itérable. Pourtant, nous ne lui avons pas implémenté de méthode __iter__ permettant de la parcourir.

Il s’agit en fait d’une particularité des indexables, et de la fonction iter qui est capable de créer un itérateur à partir de ces derniers. Cet itérateur se contentera d’appeler __getitem__ sur notre objet avec des indices successifs, partant de 0 et continuant jusqu’à ce que la méthode lève une IndexError.

Dans notre cas, ça nous évite donc d’implémenter nous-même __iter__, mais ça complexifie aussi les traitements. Souvenez-vous de notre méthode __getitem__ : elle parcourt la liste jusqu’à l’élément voulu.

Ainsi, pour accéder au premier maillon, on parcourt un élément, on en parcourt deux pour accéder au second, etc. Donc pour itérer sur une liste de 5 éléments, on va devoir parcourir 1 + 2 + 3 + 4 + 5 soit 15 maillons, là où 5 seraient suffisants. C’est pourquoi nous reviendrons sur Deque en fin de chapitre pour lui intégrer sa propre méthode __iter__.

  1. À une approximation près, comme détaillé dans « Le cas des indexables ». ↩

Utilisation des iterables

Python et les itérables

Ce concept d’itérateurs est utilisé par Python dans une grande partie des ses builtins. Plutôt que de vous forcer à utiliser une liste, Python vous permet de fournir un objet itérable, pour sum, max ou map par exemple.

Je vous propose de tester cela avec un itérable basique, qui nous permettra de réaliser un range simplifié.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class MyRange:
    def __init__(self, size):
        self.size = size

    def __iter__(self):
        return MyRangeIterator(self)

class MyRangeIterator:
    def __init__(self, my_range):
        self.current = 0
        self.max = my_range.size

    def __iter__(self):
        return self

    def __next__(self):
        if self.current >= self.max:
            raise StopIteration
        ret = self.current
        self.current += 1
        return ret

Maintenant, testons notre objet, en essayant d’itérer dessus à l’aide d’un for.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
>>> MyRange(5)
<__main__.MyRange object at 0x7fcf3b0e8f28>
>>> for i in MyRange(5):
...     print(i)
...
0
1
2
3
4

Voilà pour l’itération, mais testons ensuite quelques autres builtins dont je parlais plus haut.

1
2
3
4
5
6
>>> sum(MyRange(5)) # sum réalise la somme de tous les éléments, soit 0 + 1 + 2 + 3 + 4
10
>>> max(MyRange(5)) # max retourne la plus grande valeur
4
>>> map(str, MyRange(5)) # Ici, map retournera chaque valeur convertie en str
<map object at 0x7f8b81226cf8>

Mmmh, que s’est-il passé ? En fait, map ne retourne pas une liste, mais un nouvel itérateur. Si nous voulons en voir le contenu, nous pouvons itérer dessus… ou plus simplement, convertir le résultat en liste :

1
2
>>> list(map(str, MyRange(5))
['0', '1', '2', '3', '4']

Vous l’aurez compris, list prend aussi n’importe quel itérable en argument, tout comme zip ou str.join par exemple.

1
2
3
4
5
6
>>> list(MyRange(5))
[0, 1, 2, 3, 4]
>>> list(zip(MyRange(5), 'abcde')) # Les chaînes sont aussi des itérables
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]
>>> ', '.join(map(str, MyRange(5)))
'0, 1, 2, 3, 4'

J’en resterai là pour les exemples, sachez seulement que beaucoup de fonctions sont compatibles. Seules celles nécessitant des propriétés spécifiques de l’objet ne le seront pas par défaut, comme la fonction reversed.

Retour sur iter

Je voudrais ici revenir sur la fonction iter, qui crée un itérateur à partir d’un itérable. Sachez que ce n’est pas sa seule utilité. Elle peut aussi créer un itérateur à partir d’une fonction et d’une valeur de fin. C’est-à-dire que la fonction sera appelée tant que la valeur de fin n’a pas été retournée, par exemple :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
>>> n = 0
>>> def iter_func():
...     global n
...     n += 1
...     return n
...
>>> for i in iter(iter_func, 10):
...     print(i)
...
1
2
3
4
5
6
7
8
9

Utilisation avancée : le module itertools

Nous l’avons vu, les itérables sont au cœur des fonctions élémentaires de Python. Je voudrais maintenant vous présenter un module qui vous sera propablement très utile : itertools.

Ce module met à disposition de nombreux itérables plutôt variés, dont :

  • chain(p, q, ...) — Met bout à bout plusieurs itérables ;
  • islice(p, start, stop, step) — Fait un travail semblable aux slices, mais en travaillant avec des itérables (nul besoin de pouvoir indexer notre objet) ;
  • combinations(p, r) — Retourne toutes les combinaisons de r éléments possibles dans p ;
  • zip_longest(p, q, ...) — Similaire à zip, mais s’aligne sur l’itérable le plus grand plutôt que le plus petit (en permettant de spécifier une valeur de remplissage).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
>>> import itertools
>>> itertools.chain('abcd', [1, 2, 3])
<itertools.chain object at 0x7f757b508c88>
>>> list(itertools.chain('abcd', [1, 2, 3]))
['a', 'b', 'c', 'd', 1, 2, 3]
>>> list(itertools.islice(itertools.chain('abcd', [1, 2, 3]), 1, None, 2))
['b', 'd', 2]
>>> list(itertools.combinations('abc', 2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]
>>> list(itertools.zip_longest('abcd', [1, 2, 3]))
[('a', 1), ('b', 2), ('c', 3), ('d', None)]

Je tiens enfin à attirer votre attention sur les recettes (recipes), un ensemble d’exemples qui vous sont proposés mettant à profit les outils présents dans itertools.

L'unpacking

Une fonctionnalité courante de Python, liée aux itérables, est celle de l’unpacking. Il s’agit de l’opération qui permet de décomposer un itérable en plusieurs variables.

Prenons values une liste de 3 valeurs, il est possible en une ligne d’assigner chaque valeur à une variable différente.

1
2
3
4
5
6
7
8
>>> values = [1, 3, 5]
>>> a, b, c = values
>>> a
1
>>> b
3
>>> c
5

J’utilise ici une liste values, mais tout type d’itérable est accepté, on pourrait avoir un range ou un set par exemple. L’itérable n’a pas besoin d’être une séquence comme la liste.

1
2
>>> a, b, c = range(1, 6, 2)
>>> a, b, c = {1, 3, 5} # l'ordre n'est pas assuré dans ce dernier cas

C’est aussi cette fonctionnalité qui est à l’origine de l’assignement multiple et de l’échange de variables.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
>>> x, y = 10, 20
>>> x
10
>>> y
20
>>> x, y = y, x
>>> x
20
>>> y
10

En effet, nous avons dans ces deux cas, à gauche comme à droite du signe =, des tuples. Et celui de droite est décomposé pour correspondre aux variables de gauche.

Je parle de tuples, mais on retrouve la même chose avec des listes. Les assignations suivantes sont d’ailleurs équivalentes.

1
2
3
>>> x, y = 10, 20
>>> (x, y) = (10, 20)
>>> [x, y] = [10, 20]

Structures imbriquées

Ces cas d’unpacking sont les plus simples : nous avons un itérable à droite et un ensemble « plat » de variables à gauche. Je dis « plat » parce qu’il n’y a qu’un niveau, aucune imbrication.

Mais il est possible de faire bien plus que cela, en décomposant aussi des itérables imbriqués les uns dans les autres.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
>>> a, ((b, c, d), e), (f, g) = [0, (range(1, 4), 5), '67']
>>> a
0
>>> b
1
>>> c
2
>>> d
3
>>> e
5
>>> f
'6'
>>> g
'7'

Opérateur splat

Mais on peut aller encore plus loin avec l’opérateur splat. Cet opérateur est représenté par le caractère *.

À ne pas confondre avec la multiplication, opérateur binaire entre deux objets, il s’agit ici d’un opérateur unaire : c’est-à-dire qu’il n’opère que sur un objet, en se plaçant devant.

Utilisé à gauche lors d’une assignation, il permet de récupérer plusieurs éléments lors d’une décomposition.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
>>> head, *tail = range(10)
>>> head
0
>>> tail
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> head, *middle, last = range(10)
>>> head
0
>>> middle
[1, 2, 3, 4, 5, 6, 7, 8]
>>> last
9
>>> head, second, *middle, last = range(10)
>>> head
0
>>> second
1
>>> middle
[2, 3, 4, 5, 6, 7, 8]
>>> last
9

Vous l’avez compris, la variable précédée du splat devient une liste, dont la taille s’ajuste en fonction du nombre d’éléments.

Il est donc impossible d’avoir deux variables précédées d’un splat, cela mènerait à une ambigüité. Ou plutôt, devrais-je préciser, une seul par niveau d’imbrication.

1
2
3
4
5
6
7
>>> *a, (b, *c) = (0, 1, 2, (3, 4, 5))
>>> a
[0, 1, 2]
>>> b
3
>>> c
[4, 5]

Encore du splat

Nous avons vu l’opérateur splat utilisé à gauche de l’assignation, mais il est aussi possible depuis Python 3.51 de l’utiliser à droite. Il aura simplement l’effet inverse, et décomposera un itérable comme si ses valeurs avaient été entrées une à une.

1
2
3
>>> values = *[0, 1, 2], 3, 4, *[5, 6], 7
>>> values
(0, 1, 2, 3, 4, 5, 6, 7)

Il est bien sûr possible de combiner les deux.

1
2
3
4
5
6
7
>>> first, *middle, last = *[0, 1, 2], 3, 4, *[5, 6], 7
>>> first
0
>>> middle
[1, 2, 3, 4, 5, 6]
>>> last
7

  1. Pour plus d’informations sur les possibilités étendues de l’opérateur splat offertes par Python 3.5 : <https://zestedesavoir.com/articles/175/sortie-de-python-3-5/#2-principales-nouveautes> ↩

TP : Itérateur sur listes chaînées

Revenons sur nos listes chaînées afin d’y implémenter le protocole des itérables. Notre classe Deque a donc besoin d’une méthode __iter__ retournant un itérateur, que nous appellerons simplement DequeIterator.

1
2
def __iter__(self):
    return DequeIterator(self)

Cet itérateur contiendra une référence vers un maillon, puis, à chaque appel à __next__, renverra la valeur du maillon courant, tout en prenant soin de passer au maillon suivant pour le prochain appel. StopIteration sera levée si le maillon courant vaut None.

On ajoutera aussi __iter__ dans l’itérateur, comme vu plus tôt, dans le cas où cet itérateur serait utilisé comme itérable.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class DequeIterator:
    def __init__(self, deque):
        self.current = deque.first

    def __next__(self):
        if self.current is None:
            raise StopIteration
        value = self.current.value
        self.current = self.current.next
        return value

    def __iter__(self):
        return self

Testons maintenant notre implémentation…

1
2
3
4
5
6
7
8
>>> for i in Deque([1, 2, 3, 4, 5]):
...     print(i)
...
1
2
3
4
5

… Ça marche !

Passons enfin aux ressources de la documentation concernant les itérables et itérateurs.

Les PEP, propositions et descriptions de nouvelles fonctionnalités, sont aussi des sources d’informations intéressantes.

Et pour finir, quelques ressources annexes sur ces sujets :