---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.16.0
kernelspec:
  name: python3
  display_name: Python 3
---

# Itérateurs et générateurs

```{code-cell} python
:tags: [hide-input]

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np
import seaborn as sns

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)
```

## Le protocole itérable

L'une des idées les plus fondatrices de Python est que la boucle `for` ne connaît pas les listes — elle connaît les **itérables**. Un itérable est tout objet capable de livrer ses éléments un par un, dans un ordre défini. Les listes, tuples, chaînes de caractères, dictionnaires, ensembles, fichiers ouverts, et même des objets de vos propres classes peuvent tous être des itérables, dès lors qu'ils implémentent le protocole adéquat.

Ce protocole repose sur deux méthodes spéciales distinctes, ce qui introduit une séparation nette entre deux concepts souvent confondus par les débutants : l'**itérable** et l'**itérateur**.

```{prf:definition} Itérable et itérateur
:label: definition-10-01
- Un **itérable** est un objet qui implémente `__iter__(self)`. Cette méthode doit retourner un **itérateur**. Les listes, tuples, chaînes, dictionnaires sont tous des itérables.
- Un **itérateur** est un objet qui implémente à la fois `__iter__(self)` (qui retourne `self`) et `__next__(self)`. La méthode `__next__` retourne l'élément suivant, ou lève `StopIteration` lorsqu'il n'y a plus d'éléments. Un itérateur est toujours un itérable, mais un itérable n'est pas nécessairement un itérateur.
```

Cette distinction est subtile mais essentielle. Une liste est un itérable : on peut en créer autant d'itérateurs que l'on souhaite, chacun conservant sa propre position de lecture. Un fichier ouvert, lui, est directement un itérateur : il maintient un curseur interne et avance ligne par ligne.

```{code-cell} python
# Une liste est un itérable, pas un itérateur
ma_liste = [10, 20, 30]
print(hasattr(ma_liste, '__iter__'))   # True
print(hasattr(ma_liste, '__next__'))   # False

# iter() crée un itérateur à partir d'un itérable
it = iter(ma_liste)
print(hasattr(it, '__next__'))         # True

# next() avance l'itérateur
print(next(it))   # 10
print(next(it))   # 20
print(next(it))   # 30

try:
    next(it)
except StopIteration:
    print("StopIteration : plus d'éléments")
```

```{code-cell} python
# La boucle for est du sucre syntaxique sur iter() / next()
# Ce code :
for x in [1, 2, 3]:
    print(x)

# Est équivalent à :
it = iter([1, 2, 3])
while True:
    try:
        x = next(it)
        print(x)
    except StopIteration:
        break
```

La fonction built-in `iter()` peut aussi accepter un deuxième argument, appelé **sentinelle** : dans ce cas, le premier argument doit être un callable, et `iter()` l'appellera répétitivement jusqu'à ce qu'il retourne la valeur sentinelle.

```{code-cell} python
import random

# iter(callable, sentinelle) : appelle callable() jusqu'à obtenir la sentinelle
random.seed(42)
lancers = list(iter(lambda: random.randint(1, 6), 6))   # Lancer jusqu'à obtenir 6
print(f"Lancers avant d'obtenir 6 : {lancers}")
```

## Implémenter un itérateur personnalisé

Construire ses propres itérateurs permet de créer des séquences de données sophistiquées, paresseuses, et potentiellement infinies. L'implémentation du protocole itérable s'effectue en définissant `__iter__` et `__next__` dans vos classes.

```{code-cell} python
class CompteARebours:
    """Itérateur qui compte à rebours depuis n jusqu'à 1."""

    def __init__(self, debut: int) -> None:
        if debut < 0:
            raise ValueError("Le point de départ doit être positif")
        self._valeur = debut

    def __iter__(self) -> "CompteARebours":
        return self   # Un itérateur retourne toujours self

    def __next__(self) -> int:
        if self._valeur <= 0:
            raise StopIteration
        valeur = self._valeur
        self._valeur -= 1
        return valeur


for n in CompteARebours(5):
    print(n, end=" ")
print()

# Utilisation avec les fonctions de la bibliothèque standard
print(list(CompteARebours(8)))
print(sum(CompteARebours(10)))
```

```{prf:remark}
:label: remark-10-01
Notez que `CompteARebours` est à la fois un itérable et un itérateur : il implémente `__iter__` (retournant `self`) et `__next__`. Cette conception est courante pour les itérateurs simples, mais elle présente une limitation : une fois épuisé, l'objet ne peut pas être réutilisé dans une nouvelle boucle. Pour permettre plusieurs itérations indépendantes, il vaut mieux séparer la classe itérable (qui garde les données) de la classe itérateur (qui garde la position).
```

```{code-cell} python
class Intervalle:
    """Itérable séparé de son itérateur — permet plusieurs itérations."""

    def __init__(self, debut: int, fin: int, pas: int = 1) -> None:
        self.debut = debut
        self.fin = fin
        self.pas = pas

    def __iter__(self) -> "IntervalleIterateur":
        return IntervalleIterateur(self)


class IntervalleIterateur:
    """Itérateur associé à Intervalle."""

    def __init__(self, intervalle: Intervalle) -> None:
        self._intervalle = intervalle
        self._courant = intervalle.debut

    def __iter__(self) -> "IntervalleIterateur":
        return self

    def __next__(self) -> int:
        if self._courant >= self._intervalle.fin:
            raise StopIteration
        valeur = self._courant
        self._courant += self._intervalle.pas
        return valeur


iv = Intervalle(0, 10, 2)
print("Première itération :", list(iv))
print("Deuxième itération :", list(iv))   # Fonctionne aussi, contrairement à un itérateur simple
```

## Générateurs avec `yield`

Implémenter manuellement `__iter__` et `__next__` peut devenir verbeux. Python offre une abstraction élégante : le **générateur**. Une fonction génératrice est une fonction ordinaire qui contient au moins une instruction `yield`. Lorsqu'elle est appelée, elle ne s'exécute pas immédiatement : elle retourne un **objet générateur**, qui est un itérateur.

```{prf:definition} Générateur
:label: definition-10-02
Une **fonction génératrice** est une fonction contenant au moins une instruction `yield`. Son appel retourne un **objet générateur** qui implémente le protocole itérateur (`__iter__` et `__next__`). À chaque appel de `next()`, l'exécution reprend là où elle s'était suspendue (au dernier `yield`) jusqu'au prochain `yield` ou jusqu'à la fin de la fonction. Lorsque la fonction se termine, `StopIteration` est levée automatiquement.
```

```{code-cell} python
def compte_a_rebours(debut: int):
    """Générateur équivalent à CompteARebours, en bien plus concis."""
    while debut > 0:
        yield debut
        debut -= 1


for n in compte_a_rebours(5):
    print(n, end=" ")
print()

# Même comportement qu'avant
gen = compte_a_rebours(3)
print(next(gen))   # 3
print(next(gen))   # 2
print(next(gen))   # 1
try:
    next(gen)
except StopIteration:
    print("Générateur épuisé")
```

```{code-cell} python
def fibonacci():
    """Générateur infini de la suite de Fibonacci."""
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b


# On ne peut pas convertir un générateur infini en liste directement !
# On prend les 15 premiers termes avec islice
from itertools import islice

premiers_termes = list(islice(fibonacci(), 15))
print(f"15 premiers termes de Fibonacci : {premiers_termes}")
```

L'avantage majeur des générateurs sur les listes est la **paresse** (*laziness*) : les valeurs sont produites à la demande, une par une, sans jamais stocker l'intégralité de la séquence en mémoire. Un générateur qui produit un million de valeurs consomme à peu près la même mémoire qu'un générateur qui en produit dix.

```{code-cell} python
import sys

# Comparaison mémoire : liste vs générateur
liste_million = [x**2 for x in range(1_000_000)]
gen_million = (x**2 for x in range(1_000_000))

print(f"Taille de la liste    : {sys.getsizeof(liste_million):>12,} octets")
print(f"Taille du générateur  : {sys.getsizeof(gen_million):>12,} octets")
```

### `yield from`

L'instruction `yield from` permet à un générateur de **déléguer** à un autre itérable. Elle est plus concise et plus efficace que d'itérer manuellement sur le sous-itérable pour re-yielder ses éléments.

```{code-cell} python
def aplatir(imbriqué):
    """Aplatit récursivement une structure imbriquée de listes."""
    for élément in imbriqué:
        if isinstance(élément, list):
            yield from aplatir(élément)   # Délégation récursive
        else:
            yield élément


données = [1, [2, 3], [4, [5, 6]], 7, [8, [9, [10]]]]
print(list(aplatir(données)))
```

```{code-cell} python
def chaîne(*iterables):
    """Concatène plusieurs itérables — imitation de itertools.chain."""
    for it in iterables:
        yield from it


print(list(chaîne([1, 2], "abc", range(3))))
```

`yield from` prend également en charge le passage de valeurs dans les deux sens lorsque l'on utilise la méthode `.send()` des générateurs avancés, ce qui est au cœur des coroutines — un sujet traité dans le chapitre sur la programmation asynchrone.

## Expressions génératrices

Tout comme les listes ont leurs compréhensions, les générateurs ont leurs **expressions génératrices** (*generator expressions*). La syntaxe est identique à celle des compréhensions de listes, mais avec des **parenthèses** au lieu des crochets. Le résultat est un objet générateur paresseux.

```{code-cell} python
# Compréhension de liste : calcule tout immédiatement
carrés_liste = [x**2 for x in range(10)]

# Expression génératrice : calcule à la demande
carrés_gen = (x**2 for x in range(10))

print(type(carrés_liste))   # <class 'list'>
print(type(carrés_gen))     # <class 'generator'>

# Dans un appel de fonction, les parenthèses supplémentaires ne sont pas nécessaires
total = sum(x**2 for x in range(100))
print(f"Somme des carrés de 0 à 99 : {total}")

# Filtrage dans une expression génératrice
pairs_carrés = list(x**2 for x in range(20) if x % 2 == 0)
print(f"Carrés des pairs : {pairs_carrés}")
```

La règle pratique : préférez les expressions génératrices aux compréhensions de listes lorsque vous n'avez pas besoin d'accéder plusieurs fois aux résultats ou de les indexer. Si vous construisez une liste pour immédiatement la passer à `sum()`, `max()`, `min()`, `any()`, `all()` ou `list()`, une expression génératrice est plus appropriée.

## Le module `itertools`

Le module `itertools` de la bibliothèque standard est une boîte à outils d'itérateurs hautement optimisés, écrits en C. Maîtriser `itertools` permet d'écrire des traitements de données à la fois concis, expressifs, et très efficaces en mémoire.

```{prf:definition} `itertools`
:label: definition-10-03
Le module `itertools` regroupe des fonctions de construction d'itérateurs qui s'inspirent de la programmation fonctionnelle et des langages APL, Haskell et SML. Ses fonctions se déclinent en trois familles : les **itérateurs infinis** (`count`, `cycle`, `repeat`), les **itérateurs de terminaison** (`chain`, `islice`, `compress`, `dropwhile`, `takewhile`, `zip_longest`…) et les **itérateurs combinatoires** (`product`, `permutations`, `combinations`, `combinations_with_replacement`).
```

```{code-cell} python
import itertools

# ─── Itérateurs infinis ───
print("=== count ===")
for x in itertools.islice(itertools.count(10, 2), 5):
    print(x, end=" ")
print()

print("=== cycle ===")
jours = itertools.cycle(["lun", "mar", "mer"])
print([next(jours) for _ in range(7)])

print("=== repeat ===")
print(list(itertools.repeat("Python", 3)))
```

```{code-cell} python
# ─── Itérateurs de terminaison ───
print("=== chain ===")
print(list(itertools.chain([1, 2], [3, 4], [5])))

print("=== islice ===")
print(list(itertools.islice(range(100), 2, 12, 3)))   # début=2, fin=12, pas=3

print("=== takewhile / dropwhile ===")
données = [1, 3, 5, 2, 4, 6, 1]
print(list(itertools.takewhile(lambda x: x % 2 != 0, données)))  # Prend tant qu'impair
print(list(itertools.dropwhile(lambda x: x % 2 != 0, données)))  # Saute tant qu'impair

print("=== compress ===")
masque = [1, 0, 1, 1, 0, 1]
print(list(itertools.compress("ABCDEF", masque)))

print("=== zip_longest ===")
print(list(itertools.zip_longest([1, 2, 3], ["a", "b"], fillvalue="?")))
```

```{code-cell} python
# ─── Itérateurs combinatoires ───
print("=== product ===")
print(list(itertools.product([0, 1], repeat=3)))   # Toutes les chaînes binaires de longueur 3

print("=== permutations ===")
print(list(itertools.permutations("ABC", 2)))

print("=== combinations ===")
print(list(itertools.combinations(range(5), 3)))

print("=== combinations_with_replacement ===")
print(list(itertools.combinations_with_replacement("AB", 3)))
```

```{code-cell} python
# ─── groupby : regrouper des éléments consécutifs ───
print("=== groupby ===")
# IMPORTANT : les données doivent être triées par la clé avant groupby
mots = ["pomme", "poire", "prune", "abricot", "ananas", "banane"]
mots_triés = sorted(mots, key=lambda m: m[0])

for lettre, groupe in itertools.groupby(mots_triés, key=lambda m: m[0]):
    print(f"  {lettre} : {list(groupe)}")
```

```{prf:example} Pipeline de traitement de données avec `itertools`
:label: example-10-01
Imaginons un flux de transactions financières. On souhaite filtrer les transactions positives, les regrouper par catégorie, et calculer le total de chaque groupe — sans jamais charger tout le flux en mémoire.

```python
import itertools
from collections import defaultdict

transactions = [
    ("alimentation", 45.0),
    ("alimentation", -5.0),   # remboursement
    ("transport", 30.0),
    ("loisirs", 120.0),
    ("alimentation", 80.0),
    ("transport", 15.0),
    ("loisirs", -10.0),
    ("loisirs", 55.0),
]

# Filtrer, trier, grouper — tout en mode itérateur
positives = ((cat, montant) for cat, montant in transactions if montant > 0)
triées = sorted(positives, key=lambda t: t[0])

totaux = {
    catégorie: sum(m for _, m in groupe)
    for catégorie, groupe in itertools.groupby(triées, key=lambda t: t[0])
}
print(totaux)
# {'alimentation': 125.0, 'loisirs': 175.0, 'transport': 45.0}
```
```

```{code-cell} python
import itertools
from collections import defaultdict

transactions = [
    ("alimentation", 45.0),
    ("alimentation", -5.0),
    ("transport", 30.0),
    ("loisirs", 120.0),
    ("alimentation", 80.0),
    ("transport", 15.0),
    ("loisirs", -10.0),
    ("loisirs", 55.0),
]

positives = ((cat, montant) for cat, montant in transactions if montant > 0)
triées = sorted(positives, key=lambda t: t[0])

totaux = {
    catégorie: sum(m for _, m in groupe)
    for catégorie, groupe in itertools.groupby(triées, key=lambda t: t[0])
}
print(totaux)
```

## Itérateurs infinis et gestion de la terminaison

Un générateur infini ne pose aucun problème en Python, à condition de ne jamais tenter de le convertir en une structure de données finie sans le tronquer au préalable. Les outils de terminaison d'`itertools` (`islice`, `takewhile`) sont les bons compagnons des générateurs infinis.

```{code-cell} python
def nombres_premiers():
    """Générateur infini des nombres premiers (crible naïf)."""
    def est_premier(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for i in range(3, int(n**0.5) + 1, 2):
            if n % i == 0:
                return False
        return True

    n = 2
    while True:
        if est_premier(n):
            yield n
        n += 1


# Premiers 20 nombres premiers
print(list(itertools.islice(nombres_premiers(), 20)))

# Premiers nombres premiers inférieurs à 50
print(list(itertools.takewhile(lambda p: p < 50, nombres_premiers())))
```

## Avantages mémoire et performance

La valeur principale des itérateurs et des générateurs est la **consommation mémoire constante** pour le traitement de flux de données potentiellement illimités. Un pipeline d'itérateurs n'alloue jamais qu'un nombre fixe d'objets en mémoire, quelle que soit la taille des données.

```{code-cell} python
:tags: [hide-input]

import time

def mesurer_temps(fn):
    debut = time.perf_counter()
    résultat = fn()
    return time.perf_counter() - debut, résultat

N = 5_000_000

# Version liste : crée N éléments en mémoire
t_liste, r_liste = mesurer_temps(lambda: sum([x**2 for x in range(N) if x % 3 == 0]))

# Version génératrice : traite un élément à la fois
t_gen, r_gen = mesurer_temps(lambda: sum(x**2 for x in range(N) if x % 3 == 0))

assert r_liste == r_gen

fig, axes = plt.subplots(1, 2, figsize=(11, 5))
fig.suptitle("Compréhension de liste vs expression génératrice", fontsize=14, fontweight='bold')

palette = sns.color_palette("muted", 2)

# Temps
axes[0].bar(["Liste", "Générateur"], [t_liste * 1000, t_gen * 1000],
            color=palette, edgecolor='white', linewidth=1.5)
axes[0].set_ylabel("Temps (ms)")
axes[0].set_title(f"Durée d'exécution (N = {N:,})")
for i, t in enumerate([t_liste, t_gen]):
    axes[0].text(i, t * 1000 + 5, f"{t*1000:.1f} ms", ha='center', fontsize=11,
                 fontweight='bold', color=palette[i])

# Mémoire (illustrative)
taille_liste = sys.getsizeof([x**2 for x in range(10_000) if x % 3 == 0])
taille_gen = sys.getsizeof(x**2 for x in range(10_000) if x % 3 == 0)

axes[1].bar(["Liste\n(10 000 élts)", "Générateur"], [taille_liste / 1024, taille_gen / 1024],
            color=palette, edgecolor='white', linewidth=1.5)
axes[1].set_ylabel("Mémoire (ko)")
axes[1].set_title("Empreinte mémoire")
for i, t in enumerate([taille_liste, taille_gen]):
    axes[1].text(i, t / 1024 + 1, f"{t / 1024:.1f} ko", ha='center', fontsize=11,
                 fontweight='bold', color=palette[i])

plt.tight_layout()
plt.show()
```

## Résumé

Ce chapitre a exposé le protocole itérable de Python, mécanisme central qui unifie toutes les structures de données et tous les outils de traitement séquentiel :

- Le **protocole itérable** repose sur `__iter__` (qui retourne un itérateur) et `__next__` (qui retourne l'élément suivant ou lève `StopIteration`). Les fonctions `iter()` et `next()` permettent d'interagir manuellement avec ce protocole.
- Un **itérable** peut produire plusieurs itérateurs indépendants ; un **itérateur** maintient un état de progression unique et ne peut être parcouru qu'une fois.
- Les **fonctions génératrices** (contenant `yield`) créent des objets générateurs de façon concise. L'exécution se suspend à chaque `yield` et reprend au `next()` suivant.
- `yield from` délègue à un sous-itérable, simplifie les générateurs récursifs et prend en charge la communication bidirectionnelle pour les coroutines.
- Les **expressions génératrices** offrent une syntaxe compacte pour créer des générateurs paresseux à la volée.
- Le module `itertools` fournit une palette d'itérateurs optimisés : itérateurs infinis (`count`, `cycle`, `repeat`), de terminaison (`chain`, `islice`, `compress`, `takewhile`, `dropwhile`, `zip_longest`) et combinatoires (`product`, `permutations`, `combinations`). `groupby` regroupe des éléments consécutifs selon une clé.
- L'avantage décisif des itérateurs est leur **consommation mémoire constante** : ils traitent les données au fil de l'eau, sans jamais matérialiser la séquence complète.

Dans le chapitre suivant, nous explorerons les **décorateurs** — un mécanisme élégant qui s'appuie sur les fonctions de première classe et les fermetures pour transformer et enrichir des fonctions ou des classes.