“Subgenerators with yield from” grew from one to six pages. It now includes simpler experiments demonstrating the behavior of generators with yield from, and an example of traversing a tree data structure, developed step-by-step.

The last major section of this chapter, “Classic Coroutines”, is a 9-page introduction to a topic that filled a 40-page chapter in the first edition. I updated and moved the “Classic Coroutines” chapter to a post in the companion website because it was the most challenging chapter for readers, but its subject matter is less relevant after Python 3.5 introduced native coroutines—which we’ll study in Chapter 21.

We’ll get started studying how the iter() built-in function makes sequences iterable.

A Sequence of Words

We’ll start our exploration of iterables by implementing a Sentence class: you give its constructor a string with some text, and then you can iterate word by word. The first version will implement the sequence protocol, and it’s iterable because all sequences are iterable—as we’ve seen since Chapter 1. Now we’ll see exactly why.

Example 17-1 shows a Sentence class that extracts words from a text by index.

import re
import reprlib

RE_WORD = re.compile(r'\w+')


class Sentence:

    def __init__(self, text):
        self.text = text
        self.words = RE_WORD.findall(text)  

    def __getitem__(self, index):
        return self.words[index]  

    def __len__(self):  
        return len(self.words)

    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.text)  

.findall returns a list with all nonoverlapping matches of the regular expression, as a list of strings.

self.words holds the result of .findall, so we simply return the word at the given index.

To complete the sequence protocol, we implement __len__ although it is not needed to make an iterable.

reprlib.repr is a utility function to generate abbreviated string representations of data structures that can be very large.²

By default, reprlib.repr limits the generated string to 30 characters. See the console session in Example 17-2 to see how Sentence is used.

>>> s = Sentence('"The time has come," the Walrus said,')  
>>> s
Sentence('"The time ha... Walrus said,')  
>>> for word in s:  
...     print(word)
The
time
has
come
the
Walrus
said
>>> list(s)  
['The', 'time', 'has', 'come', 'the', 'Walrus', 'said']

A sentence is created from a string.

Note the output of __repr__ using ... generated by reprlib.repr.

Sentence instances are iterable; we’ll see why in a moment.

Being iterable, Sentence objects can be used as input to build lists and other iterable types.

In the following pages, we’ll develop other Sentence classes that pass the tests in Example 17-2. However, the implementation in Example 17-1 is different from the others because it’s also a sequence, so you can get words by index:

>>> s[0]
'The'
>>> s[5]
'Walrus'
>>> s[-1]
'said'

Python programmers know that sequences are iterable. Now we’ll see precisely why.

Whenever Python needs to iterate over an object x, it automatically calls iter(x).

As mentioned in “Python Digs Sequences”, this is an extreme form of duck typing: an object is considered iterable not only when it implements the special method __iter__, but also when it implements __getitem__. Take a look:

>>> class Spam:
...     def __getitem__(self, i):
...         print('->', i)
...         raise IndexError()
...
>>> spam_can = Spam()
>>> iter(spam_can)
<iterator object at 0x10a878f70>
>>> list(spam_can)
-> 0
[]
>>> from collections import abc
>>> isinstance(spam_can, abc.Iterable)
False

If a class provides __getitem__, the iter() built-in accepts an instance of that class as iterable and builds an iterator from the instance. Python’s iteration machinery will call __getitem__ with indexes starting from 0, and will take an IndexError as a signal that there are no more items.

Note that although spam_can is iterable (its __getitem__ could provide items), it is not recognized as such by an isinstance against abc.Iterable.

In the goose-typing approach, the definition for an iterable is simpler but not as flexible: an object is considered iterable if it implements the __iter__ method. No subclassing or registration is required, because abc.Iterable implements the __subclasshook__, as seen in “Structural Typing with ABCs”. Here is a demonstration:

>>> class GooseSpam:
...     def __iter__(self):
...         pass
...
>>> from collections import abc
>>> issubclass(GooseSpam, abc.Iterable)
True
>>> goose_spam_can = GooseSpam()
>>> isinstance(goose_spam_can, abc.Iterable)
True

Explicitly checking whether an object is iterable may not be worthwhile if right after the check you are going to iterate over the object. After all, when the iteration is attempted on a noniterable, the exception Python raises is clear enough: TypeError: 'C' object is not iterable. If you can do better than just raising TypeError, then do so in a try/except block instead of doing an explicit check. The explicit check may make sense if you are holding on to the object to iterate over it later; in this case, catching the error early makes debugging easier.

The iter() built-in is more often used by Python itself than by our own code. There’s a second way we can use it, but it’s not widely known.

>>> def d6():
...     return randint(1, 6)
...
>>> d6_iter = iter(d6, 1)
>>> d6_iter
<callable_iterator object at 0x10a245270>
>>> for roll in d6_iter:
...     print(roll)
...
4
3
6
3

from functools import partial

with open('mydata.db', 'rb') as f:
    read64 = partial(f.read, 64)
    for block in iter(read64, b''):
        process_block(block)

From the explanation in “Why Sequences Are Iterable: The iter Function” we can extrapolate a definition:

iterable

Any object from which the iter built-in function can obtain an iterator. Objects implementing an __iter__ method returning an iterator are iterable. Sequences are always iterable, as are objects implementing a __getitem__ method that accepts 0-based indexes.

It’s important to be clear about the relationship between iterables and iterators: Python obtains iterators from iterables.

Here is a simple for loop iterating over a str. The str 'ABC' is the iterable here. You don’t see it, but there is an iterator behind the curtain:

>>> s = 'ABC'
>>> for char in s:
...     print(char)
...
A
B
C

If there was no for statement and we had to emulate the for machinery by hand with a while loop, this is what we’d have to write:

>>> s = 'ABC'
>>> it = iter(s)  
>>> while True:
...     try:
...         print(next(it))  
...     except StopIteration:  
...         del it  
...         break  
...
A
B
C

Build an iterator it from the iterable.

Repeatedly call next on the iterator to obtain the next item.

The iterator raises StopIteration when there are no further items.

Release reference to it—the iterator object is discarded.

Exit the loop.

StopIteration signals that the iterator is exhausted. This exception is handled internally by the iter() built-in that is part of the logic of for loops and other iteration contexts like list comprehensions, iterable unpacking, etc.

Python’s standard interface for an iterator has two methods:

__next__

Returns the next item in the series, raising StopIteration if there are no more.

__iter__

Returns self; this allows iterators to be used where an iterable is expected, for example, in a for loop.

That interface is formalized in the collections.abc.Iterator ABC, which declares the __next__ abstract method, and subclasses Iterable—where the abstract __iter__ method is declared. See Figure 17-1.

Figure 17-1. The Iterable and Iterator ABCs. Methods in italic are abstract. A concrete Iterable.__iter__ should return a new Iterator instance. A concrete Iterator must implement __next__. The Iterator.__iter__ method just returns the instance itself.

The source code for collections.abc.Iterator is in Example 17-3.

class Iterator(Iterable):

    __slots__ = ()

    @abstractmethod
    def __next__(self):
        'Return the next item from the iterator. When exhausted, raise StopIteration'
        raise StopIteration

    def __iter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):  
        if cls is Iterator:
            return _check_methods(C, '__iter__', '__next__')  
        return NotImplemented

__subclasshook__ supports structural type checks with isinstance and issubclass. We saw it in “Structural Typing with ABCs”.

_check_methods traverses the __mro__ of the class to check whether the methods are implemented in its base classes. It’s defined in that same Lib/_collections_abc.py module. If the methods are implemented, the C class will be recognized as a virtual subclass of Iterator. In other words, issubclass(C, Iterable) will return True.

The Lib/types.py module source code in Python 3.9 has a comment that says:

# Iterators in Python aren't a matter of type but of protocol.  A large
# and changing number of builtin types implement *some* flavor of
# iterator.  Don't check the type!  Use hasattr to check for both
# "__iter__" and "__next__" attributes instead.

In fact, that’s exactly what the __subclasshook__ method of the abc.Iterator ABC does.

Back to our Sentence class from Example 17-1, you can clearly see how the iterator is built by iter() and consumed by next() using the Python console:

>>> s3 = Sentence('Life of Brian')  
>>> it = iter(s3)  
>>> it  # doctest: +ELLIPSIS
<iterator object at 0x...>
>>> next(it)  
'Life'
>>> next(it)
'of'
>>> next(it)
'Brian'
>>> next(it)  
Traceback (most recent call last):
  ...
StopIteration
>>> list(it)  
[]
>>> list(iter(s3))  
['Life', 'of', 'Brian']

Create a sentence s3 with three words.

Obtain an iterator from s3.

next(it) fetches the next word.

There are no more words, so the iterator raises a StopIteration exception.

Once exhausted, an iterator will always raise StopIteration, which makes it look like it’s empty.

To go over the sentence again, a new iterator must be built.

Because the only methods required of an iterator are __next__ and __iter__, there is no way to check whether there are remaining items, other than to call next() and catch StopIteration. Also, it’s not possible to “reset” an iterator. If you need to start over, you need to call iter() on the iterable that built the iterator in the first place. Calling iter() on the iterator itself won’t help either, because—as mentioned—Iterator.__iter__ is implemented by returning self, so this will not reset a depleted iterator.

That minimal interface is sensible, because in reality not all iterators are resettable. For example, if an iterator is reading packets from the network, there’s no way to rewind it.³

The first version of Sentence from Example 17-1 was iterable thanks to the special treatment the iter() built-in gives to sequences. Next, we will implement Sentence variations that implement __iter__ to return iterators.

The next variations of Sentence implement the standard iterable protocol, first by implementing the Iterator design pattern, and then with generator functions.

import re
import reprlib

RE_WORD = re.compile(r'\w+')


class Sentence:

    def __init__(self, text):
        self.text = text
        self.words = RE_WORD.findall(text)

    def __repr__(self):
        return f'Sentence({reprlib.repr(self.text)})'

    def __iter__(self):  
        return SentenceIterator(self.words)  


class SentenceIterator:

    def __init__(self, words):
        self.words = words  
        self.index = 0  

    def __next__(self):
        try:
            word = self.words[self.index]  
        except IndexError:
            raise StopIteration()  
        self.index += 1  
        return word  

    def __iter__(self):  
        return self

import re
import reprlib

RE_WORD = re.compile(r'\w+')


class Sentence:

    def __init__(self, text):
        self.text = text
        self.words = RE_WORD.findall(text)

    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.text)

    def __iter__(self):
        for word in self.words:  
            yield word  
        

# done! 

>>> def gen_123():
...     yield 1  
...     yield 2
...     yield 3
...
>>> gen_123  # doctest: +ELLIPSIS
<function gen_123 at 0x...>  
>>> gen_123()   # doctest: +ELLIPSIS
<generator object gen_123 at 0x...>  
>>> for i in gen_123():  
...     print(i)
1
2
3
>>> g = gen_123()  
>>> next(g)  
1
>>> next(g)
2
>>> next(g)
3
>>> next(g)  
Traceback (most recent call last):
  ...
StopIteration

>>> def gen_AB():
...     print('start')
...     yield 'A'          
...     print('continue')
...     yield 'B'          
...     print('end.')      
...
>>> for c in gen_AB():     
...     print('-->', c)    
...
start     
--> A     
continue  
--> B     
end.      
>>>       

The final variations of Sentence are lazy, taking advantage of a lazy function from the re module.

import re
import reprlib

RE_WORD = re.compile(r'\w+')


class Sentence:

    def __init__(self, text):
        self.text = text  

    def __repr__(self):
        return f'Sentence({reprlib.repr(self.text)})'

    def __iter__(self):
        for match in RE_WORD.finditer(self.text):  
            yield match.group()  

>>> def gen_AB():  
...     print('start')
...     yield 'A'
...     print('continue')
...     yield 'B'
...     print('end.')
...
>>> res1 = [x*3 for x in gen_AB()]  
start
continue
end.
>>> for i in res1:  
...     print('-->', i)
...
--> AAA
--> BBB
>>> res2 = (x*3 for x in gen_AB())  
>>> res2
<generator object <genexpr> at 0x10063c240>
>>> for i in res2:  
...     print('-->', i)
...
start      
--> AAA
continue
--> BBB
end.

import re
import reprlib

RE_WORD = re.compile(r'\w+')


class Sentence:

    def __init__(self, text):
        self.text = text

    def __repr__(self):
        return f'Sentence({reprlib.repr(self.text)})'

    def __iter__(self):
        return (match.group() for match in RE_WORD.finditer(self.text))

I used several generator expressions when implementing the Vector class in Example 12-16. Each of these methods has a generator expression: __eq__, __hash__, __abs__, angle, angles, format, __add__, and __mul__. In all those methods, a list comprehension would also work, at the cost of using more memory to store the intermediate list values.

In Example 17-10, we saw that a generator expression is a syntactic shortcut to create a generator without defining and calling a function. On the other hand, generator functions are more flexible: we can code complex logic with multiple statements, and we can even use them as coroutines, as we’ll see in “Classic Coroutines”.

For the simpler cases, a generator expression is easier to read at a glance, as the Vector example shows.

My rule of thumb in choosing the syntax to use is simple: if the generator expression spans more than a couple of lines, I prefer to code a generator function for the sake of readability.

def __mul__(self, scalar):
    if isinstance(scalar, numbers.Real):
        return Vector(n * scalar for n in self)
    else:
        return NotImplemented

The Sentence examples we’ve seen demonstrate generators playing the role of the classic Iterator pattern: retrieving items from a collection. But we can also use generators to yield values independent of a data source. The next section shows an example.

But first, a short discussion on the overlapping concepts of iterator and generator.

An Arithmetic Progression Generator

The classic Iterator pattern is all about traversal: navigating some data structure. But a standard interface based on a method to fetch the next item in a series is also useful when the items are produced on the fly, instead of retrieved from a collection. For example, the range built-in generates a bounded arithmetic progression (AP) of integers. What if you need to generate an AP of numbers of any type, not only integers?

Example 17-11 shows a few console tests of an ArithmeticProgression class we will see in a moment. The signature of the constructor in Example 17-11 is ArithmeticProgression(begin, step[, end]). The complete signature of the range built-in is range(start, stop[, step]). I chose to implement a different signature because the step is mandatory but end is optional in an arithmetic progression. I also changed the argument names from start/stop to begin/end to make it clear that I opted for a different signature. In each test in Example 17-11, I call list() on the result to inspect the generated values.

    >>> ap = ArithmeticProgression(0, 1, 3)
    >>> list(ap)
    [0, 1, 2]
    >>> ap = ArithmeticProgression(1, .5, 3)
    >>> list(ap)
    [1.0, 1.5, 2.0, 2.5]
    >>> ap = ArithmeticProgression(0, 1/3, 1)
    >>> list(ap)
    [0.0, 0.3333333333333333, 0.6666666666666666]
    >>> from fractions import Fraction
    >>> ap = ArithmeticProgression(0, Fraction(1, 3), 1)
    >>> list(ap)
    [Fraction(0, 1), Fraction(1, 3), Fraction(2, 3)]
    >>> from decimal import Decimal
    >>> ap = ArithmeticProgression(0, Decimal('.1'), .3)
    >>> list(ap)
    [Decimal('0'), Decimal('0.1'), Decimal('0.2')]

Note that the type of the numbers in the resulting arithmetic progression follows the type of begin + step, according to the numeric coercion rules of Python arithmetic. In Example 17-11, you see lists of int, float, Fraction, and Decimal numbers. Example 17-12 lists the implementation of the ArithmeticProgression class.

class ArithmeticProgression:

    def __init__(self, begin, step, end=None):       
        self.begin = begin
        self.step = step
        self.end = end  # None -> "infinite" series

    def __iter__(self):
        result_type = type(self.begin + self.step)   
        result = result_type(self.begin)             
        forever = self.end is None                   
        index = 0
        while forever or result < self.end:          
            yield result                             
            index += 1
            result = self.begin + self.step * index  

__init__ requires two arguments: begin and step; end is optional, if it’s None, the series will be unbounded.

Get the type of adding self.begin and self.step. For example, if one is int and the other is float, result_type will be float.

This line makes a result with the same numeric value of self.begin, but coerced to the type of the subsequent additions.⁷

For readability, the forever flag will be True if the self.end attribute is None, resulting in an unbounded series.

This loop runs forever or until the result matches or exceeds self.end. When this loop exits, so does the function.

The current result is produced.

The next potential result is calculated. It may never be yielded, because the while loop may terminate.

In the last line of Example 17-12, instead of adding self.step to the previous result each time around the loop, I opted to ignore the previous result and each new result by adding self.begin to self.step multiplied by index. This avoids the cumulative effect of floating-point errors after successive additions. These simple experiments make the difference clear:

>>> 100 * 1.1
110.00000000000001
>>> sum(1.1 for _ in range(100))
109.99999999999982
>>> 1000 * 1.1
1100.0
>>> sum(1.1 for _ in range(1000))
1100.0000000000086

The ArithmeticProgression class from Example 17-12 works as intended, and is a another example of using a generator function to implement the __iter__ special method. However, if the whole point of a class is to build a generator by implementing __iter__, we can replace the class with a generator function. A generator function is, after all, a generator factory.

Example 17-13 shows a generator function called aritprog_gen that does the same job as ArithmeticProgression but with less code. The tests in Example 17-11 all pass if you just call aritprog_gen instead of ArithmeticProgression.⁸

def aritprog_gen(begin, step, end=None):
    result = type(begin + step)(begin)
    forever = end is None
    index = 0
    while forever or result < end:
        yield result
        index += 1
        result = begin + step * index

Example 17-13 is elegant, but always remember: there are plenty of ready-to-use generators in the standard library, and the next section will show a shorter implementation using the itertools module.

>>> import itertools
>>> gen = itertools.count(1, .5)
>>> next(gen)
1
>>> next(gen)
1.5
>>> next(gen)
2.0
>>> next(gen)
2.5

>>> gen = itertools.takewhile(lambda n: n < 3, itertools.count(1, .5))
>>> list(gen)
[1, 1.5, 2.0, 2.5]

import itertools


def aritprog_gen(begin, step, end=None):
    first = type(begin + step)(begin)
    ap_gen = itertools.count(first, step)
    if end is None:
        return ap_gen
    return itertools.takewhile(lambda n: n < end, ap_gen)

The standard library provides many generators, from plain-text file objects providing line-by-line iteration, to the awesome os.walk function, which yields filenames while traversing a directory tree, making recursive filesystem searches as simple as a for loop.

The os.walk generator function is impressive, but in this section I want to focus on general-purpose functions that take arbitrary iterables as arguments and return generators that yield selected, computed, or rearranged items. In the following tables, I summarize two dozen of them, from the built-in, itertools, and functools modules. For convenience, I grouped them by high-level functionality, regardless of where they are defined.

The first group contains the filtering generator functions: they yield a subset of items produced by the input iterable, without changing the items themselves. Like takewhile, most functions listed in Table 17-1 take a predicate, which is a one-argument Boolean function that will be applied to each item in the input to determine whether the item is included in the output.

The console listing in Example 17-15 shows the use of all the functions in Table 17-1.

>>> def vowel(c):
...     return c.lower() in 'aeiou'
...
>>> list(filter(vowel, 'Aardvark'))
['A', 'a', 'a']
>>> import itertools
>>> list(itertools.filterfalse(vowel, 'Aardvark'))
['r', 'd', 'v', 'r', 'k']
>>> list(itertools.dropwhile(vowel, 'Aardvark'))
['r', 'd', 'v', 'a', 'r', 'k']
>>> list(itertools.takewhile(vowel, 'Aardvark'))
['A', 'a']
>>> list(itertools.compress('Aardvark', (1, 0, 1, 1, 0, 1)))
['A', 'r', 'd', 'a']
>>> list(itertools.islice('Aardvark', 4))
['A', 'a', 'r', 'd']
>>> list(itertools.islice('Aardvark', 4, 7))
['v', 'a', 'r']
>>> list(itertools.islice('Aardvark', 1, 7, 2))
['a', 'd', 'a']

The next group contains the mapping generators: they yield items computed from each individual item in the input iterable—or iterables, in the case of map and starmap.9 The generators in Table 17-2 yield one result per item in the input iterables. If the input comes from more than one iterable, the output stops as soon as the first input iterable is exhausted.

Example 17-16 demonstrates some uses of itertools.accumulate.

>>> sample = [5, 4, 2, 8, 7, 6, 3, 0, 9, 1]
>>> import itertools
>>> list(itertools.accumulate(sample))  
[5, 9, 11, 19, 26, 32, 35, 35, 44, 45]
>>> list(itertools.accumulate(sample, min))  
[5, 4, 2, 2, 2, 2, 2, 0, 0, 0]
>>> list(itertools.accumulate(sample, max))  
[5, 5, 5, 8, 8, 8, 8, 8, 9, 9]
>>> import operator
>>> list(itertools.accumulate(sample, operator.mul))  
[5, 20, 40, 320, 2240, 13440, 40320, 0, 0, 0]
>>> list(itertools.accumulate(range(1, 11), operator.mul))
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]  

Running sum.

Running minimum.

Running maximum.

Running product.

Factorials from 1! to 10!.

The remaining functions of Table 17-2 are shown in Example 17-17.

>>> list(enumerate('albatroz', 1))  
[(1, 'a'), (2, 'l'), (3, 'b'), (4, 'a'), (5, 't'), (6, 'r'), (7, 'o'), (8, 'z')]
>>> import operator
>>> list(map(operator.mul, range(11), range(11)))  
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
>>> list(map(operator.mul, range(11), [2, 4, 8]))  
[0, 4, 16]
>>> list(map(lambda a, b: (a, b), range(11), [2, 4, 8]))  
[(0, 2), (1, 4), (2, 8)]
>>> import itertools
>>> list(itertools.starmap(operator.mul, enumerate('albatroz', 1)))  
['a', 'll', 'bbb', 'aaaa', 'ttttt', 'rrrrrr', 'ooooooo', 'zzzzzzzz']
>>> sample = [5, 4, 2, 8, 7, 6, 3, 0, 9, 1]
>>> list(itertools.starmap(lambda a, b: b / a,
...     enumerate(itertools.accumulate(sample), 1)))  
[5.0, 4.5, 3.6666666666666665, 4.75, 5.2, 5.333333333333333,
5.0, 4.375, 4.888888888888889, 4.5]

Number the letters in the word, starting from 1.

Squares of integers from 0 to 10.

Multiplying numbers from two iterables in parallel: results stop when the shortest iterable ends.

This is what the zip built-in function does.

Repeat each letter in the word according to its place in it, starting from 1.

Running average.

Next, we have the group of merging generators—all of these yield items from multiple input iterables. chain and chain.from_iterable consume the input iterables sequentially (one after the other), while product, zip, and zip_longest consume the input iterables in parallel. See Table 17-3.

Example 17-18 shows the use of the itertools.chain and zip generator functions and their siblings. Recall that the zip function is named after the zip fastener or zipper (no relation to compression). Both zip and itertools.zip_longest were introduced in “The Awesome zip”.

>>> list(itertools.chain('ABC', range(2)))  
['A', 'B', 'C', 0, 1]
>>> list(itertools.chain(enumerate('ABC')))  
[(0, 'A'), (1, 'B'), (2, 'C')]
>>> list(itertools.chain.from_iterable(enumerate('ABC')))  
[0, 'A', 1, 'B', 2, 'C']
>>> list(zip('ABC', range(5), [10, 20, 30, 40]))  
[('A', 0, 10), ('B', 1, 20), ('C', 2, 30)]
>>> list(itertools.zip_longest('ABC', range(5)))  
[('A', 0), ('B', 1), ('C', 2), (None, 3), (None, 4)]
>>> list(itertools.zip_longest('ABC', range(5), fillvalue='?'))  
[('A', 0), ('B', 1), ('C', 2), ('?', 3), ('?', 4)]

chain is usually called with two or more iterables.

chain does nothing useful when called with a single iterable.

But chain.from_iterable takes each item from the iterable, and chains them in sequence, as long as each item is itself iterable.

Any number of iterables can be consumed by zip in parallel, but the generator always stops as soon as the first iterable ends. In Python ≥ 3.10, if the strict=True argument is given and an iterable ends before the others, ValueError is raised.

itertools.zip_longest works like zip, except it consumes all input iterables to the end, padding output tuples with None, as needed.

The fillvalue keyword argument specifies a custom padding value.

The itertools.product generator is a lazy way of computing Cartesian products, which we built using list comprehensions with more than one for clause in “Cartesian Products”. Generator expressions with multiple for clauses can also be used to produce Cartesian products lazily. Example 17-19 demonstrates itertools.product.

>>> list(itertools.product('ABC', range(2)))  
[('A', 0), ('A', 1), ('B', 0), ('B', 1), ('C', 0), ('C', 1)]
>>> suits = 'spades hearts diamonds clubs'.split()
>>> list(itertools.product('AK', suits))  
[('A', 'spades'), ('A', 'hearts'), ('A', 'diamonds'), ('A', 'clubs'),
('K', 'spades'), ('K', 'hearts'), ('K', 'diamonds'), ('K', 'clubs')]
>>> list(itertools.product('ABC'))  
[('A',), ('B',), ('C',)]
>>> list(itertools.product('ABC', repeat=2))  
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'),
('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
>>> list(itertools.product(range(2), repeat=3))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0),
(1, 0, 1), (1, 1, 0), (1, 1, 1)]
>>> rows = itertools.product('AB', range(2), repeat=2)
>>> for row in rows: print(row)
...
('A', 0, 'A', 0)
('A', 0, 'A', 1)
('A', 0, 'B', 0)
('A', 0, 'B', 1)
('A', 1, 'A', 0)
('A', 1, 'A', 1)
('A', 1, 'B', 0)
('A', 1, 'B', 1)
('B', 0, 'A', 0)
('B', 0, 'A', 1)
('B', 0, 'B', 0)
('B', 0, 'B', 1)
('B', 1, 'A', 0)
('B', 1, 'A', 1)
('B', 1, 'B', 0)
('B', 1, 'B', 1)

The Cartesian product of a str with three characters and a range with two integers yields six tuples (because 3 * 2 is 6).

The product of two card ranks ('AK') and four suits is a series of eight tuples.

Given a single iterable, product yields a series of one-tuples—not very useful.

The repeat=N keyword argument tells the product to consume each input iterable N times.

Some generator functions expand the input by yielding more than one value per input item. They are listed in Table 17-4.

The count and repeat functions from itertools return generators that conjure items out of nothing: neither of them takes an iterable as input. We saw itertools.count in “Arithmetic Progression with itertools”. The cycle generator makes a backup of the input iterable and yields its items repeatedly. Example 17-20 illustrates the use of count, cycle, pairwise, and repeat.

>>> ct = itertools.count()  
>>> next(ct)  
0
>>> next(ct), next(ct), next(ct)  
(1, 2, 3)
>>> list(itertools.islice(itertools.count(1, .3), 3))  
[1, 1.3, 1.6]
>>> cy = itertools.cycle('ABC')  
>>> next(cy)
'A'
>>> list(itertools.islice(cy, 7))  
['B', 'C', 'A', 'B', 'C', 'A', 'B']
>>> list(itertools.pairwise(range(7)))  
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
>>> rp = itertools.repeat(7)  
>>> next(rp), next(rp)
(7, 7)
>>> list(itertools.repeat(8, 4))  
[8, 8, 8, 8]
>>> list(map(operator.mul, range(11), itertools.repeat(5)))  
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]

Build a count generator ct.

Retrieve the first item from ct.

I can’t build a list from ct, because ct never stops, so I fetch the next three items.

I can build a list from a count generator if it is limited by islice or takewhile.

Build a cycle generator from 'ABC' and fetch its first item, 'A'.

A list can only be built if limited by islice; the next seven items are retrieved here.

For each item in the input, pairwise yields a 2-tuple with that item and the next—if there is a next item. Available in Python ≥ 3.10.

Build a repeat generator that will yield the number 7 forever.

A repeat generator can be limited by passing the times argument: here the number 8 will be produced 4 times.

A common use of repeat: providing a fixed argument in map; here it provides the 5 multiplier.

The combinations, combinations_with_replacement, and permutations generator functions—together with product—are called the combinatorics generators in the itertools documentation page. There is a close relationship between itertools.product and the remaining combinatoric functions as well, as Example 17-21 shows.

>>> list(itertools.combinations('ABC', 2))  
[('A', 'B'), ('A', 'C'), ('B', 'C')]
>>> list(itertools.combinations_with_replacement('ABC', 2))  
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
>>> list(itertools.permutations('ABC', 2))  
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
>>> list(itertools.product('ABC', repeat=2))  
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'),
('C', 'A'), ('C', 'B'), ('C', 'C')]

All combinations of len()==2 from the items in 'ABC'; item ordering in the generated tuples is irrelevant (they could be sets).

All combinations of len()==2 from the items in 'ABC', including combinations with repeated items.

All permutations of len()==2 from the items in 'ABC'; item ordering in the generated tuples is relevant.

Cartesian product from 'ABC' and 'ABC' (that’s the effect of repeat=2).

The last group of generator functions we’ll cover in this section are designed to yield all items in the input iterables, but rearranged in some way. Here are two functions that return multiple generators: itertools.groupby and itertools.tee. The other generator function in this group, the reversed built-in, is the only one covered in this section that does not accept any iterable as input, but only sequences. This makes sense: because reversed will yield the items from last to first, it only works with a sequence with a known length. But it avoids the cost of making a reversed copy of the sequence by yielding each item as needed. I put the itertools.product function together with the merging generators in Table 17-3 because they all consume more than one iterable, while the generators in Table 17-5 all accept at most one input iterable.

Example 17-22 demonstrates the use of itertools.groupby and the reversed built-in. Note that itertools.groupby assumes that the input iterable is sorted by the grouping criterion, or at least that the items are clustered by that criterion—even if not completely sorted. Tech reviewer Miroslav Šedivý suggested this use case: you can sort the datetime objects chronologically, then groupby weekday to get a group of Monday data, followed by Tuesday data, etc., and then by Monday (of the next week) again, and so on.

>>> list(itertools.groupby('LLLLAAGGG'))  
[('L', <itertools._grouper object at 0x102227cc0>),
('A', <itertools._grouper object at 0x102227b38>),
('G', <itertools._grouper object at 0x102227b70>)]
>>> for char, group in itertools.groupby('LLLLAAAGG'):  
...     print(char, '->', list(group))
...
L -> ['L', 'L', 'L', 'L']
A -> ['A', 'A',]
G -> ['G', 'G', 'G']
>>> animals = ['duck', 'eagle', 'rat', 'giraffe', 'bear',
...            'bat', 'dolphin', 'shark', 'lion']
>>> animals.sort(key=len)  
>>> animals
['rat', 'bat', 'duck', 'bear', 'lion', 'eagle', 'shark',
'giraffe', 'dolphin']
>>> for length, group in itertools.groupby(animals, len):  
...     print(length, '->', list(group))
...
3 -> ['rat', 'bat']
4 -> ['duck', 'bear', 'lion']
5 -> ['eagle', 'shark']
7 -> ['giraffe', 'dolphin']
>>> for length, group in itertools.groupby(reversed(animals), len): 
...     print(length, '->', list(group))
...
7 -> ['dolphin', 'giraffe']
5 -> ['shark', 'eagle']
4 -> ['lion', 'bear', 'duck']
3 -> ['bat', 'rat']
>>>

groupby yields tuples of (key, group_generator).

Handling groupby generators involves nested iteration: in this case, the outer for loop and the inner list constructor.

Sort animals by length.

Again, loop over the key and group pair, to display the key and expand the group into a list.

Here the reverse generator iterates over animals from right to left.

The last of the generator functions in this group is iterator.tee, which has a unique behavior: it yields multiple generators from a single input iterable, each yielding every item from the input. Those generators can be consumed independently, as shown in Example 17-23.

>>> list(itertools.tee('ABC'))
[<itertools._tee object at 0x10222abc8>, <itertools._tee object at 0x10222ac08>]
>>> g1, g2 = itertools.tee('ABC')
>>> next(g1)
'A'
>>> next(g2)
'A'
>>> next(g2)
'B'
>>> list(g1)
['B', 'C']
>>> list(g2)
['C']
>>> list(zip(*itertools.tee('ABC')))
[('A', 'A'), ('B', 'B'), ('C', 'C')]

Note that several examples in this section used combinations of generator functions. This is a great feature of these functions: because they take generators as arguments and return generators, they can be combined in many different ways.

Now we’ll review another group of iterable-savvy functions in the standard library.

The functions in Table 17-6 all take an iterable and return a single result. They are known as “reducing,” “folding,” or “accumulating” functions. We can implement every one of the built-ins listed here with functools.reduce, but they exist as built-ins because they address some common use cases more easily. A longer explanation about functools.reduce appeared in “Vector Take #4: Hashing and a Faster ==”.

In the case of all and any, there is an important optimization functools.reduce does not support: all and any short-circuit—i.e., they stop consuming the iterator as soon as the result is determined. See the last test with any in Example 17-24.

The operation of all and any is exemplified in Example 17-24.

>>> all([1, 2, 3])
True
>>> all([1, 0, 3])
False
>>> all([])
True
>>> any([1, 2, 3])
True
>>> any([1, 0, 3])
True
>>> any([0, 0.0])
False
>>> any([])
False
>>> g = (n for n in [0, 0.0, 7, 8])
>>> any(g)  
True
>>> next(g)  
8

any iterated over g until g yielded 7; then any stopped and returned True.

That’s why 8 was still remaining.

Another built-in that takes an iterable and returns something else is sorted. Unlike reversed, which is a generator function, sorted builds and returns a new list. After all, every single item of the input iterable must be read so they can be sorted, and the sorting happens in a list, therefore sorted just returns that list after it’s done. I mention sorted here because it does consume an arbitrary iterable.

Of course, sorted and the reducing functions only work with iterables that eventually stop. Otherwise, they will keep on collecting items and never return a result.

The yield from syntax provides a new way of combining generators. That’s next.

The yield from expression syntax was introduced in Python 3.3 to allow a generator to delegate work to a subgenerator.

>>> def sub_gen():
...     yield 1.1
...     yield 1.2
...
>>> def gen():
...     yield 1
...     for i in sub_gen():
...         yield i
...     yield 2
...
>>> for x in gen():
...     print(x)
...
1
1.1
1.2
2

We can get the same result using yield from, as you can see in Example 17-25.

>>> def sub_gen():
...     yield 1.1
...     yield 1.2
...
>>> def gen():
...     yield 1
...     yield from sub_gen()
...     yield 2
...
>>> for x in gen():
...     print(x)
...
1
1.1
1.2
2

In Example 17-25, the for loop is the client code, gen is the delegating generator, and sub_gen is the subgenerator. Note that yield from pauses gen, and sub_gen takes over until it is exhausted. The values yielded by sub_gen pass through gen directly to the client for loop. Meanwhile, gen is suspended and cannot see the values passing through it. Only when sub_gen is done, gen resumes.

When the subgenerator contains a return statement with a value, that value can be captured in the delegating generator by using yield from as part of an expression. Example 17-26 demonstrates.

>>> def sub_gen():
...     yield 1.1
...     yield 1.2
...     return 'Done!'
...
>>> def gen():
...     yield 1
...     result = yield from sub_gen()
...     print('<--', result)
...     yield 2
...
>>> for x in gen():
...     print(x)
...
1
1.1
1.2
<-- Done!
2

Now that we’ve seen the basics of yield from, let’s study a couple of simple but practical examples of its use.

>>> def chain(*iterables):
...     for it in iterables:
...         for i in it:
...             yield i
...
>>> s = 'ABC'
>>> r = range(3)
>>> list(chain(s, r))
['A', 'B', 'C', 0, 1, 2]

>>> def chain(*iterables):
...     for i in iterables:
...         yield from i
...
>>> list(chain(s, t))
['A', 'B', 'C', 0, 1, 2]

def tree(cls):
    yield cls.__name__


def display(cls):
    for cls_name in tree(cls):
        print(cls_name)


if __name__ == '__main__':
    display(BaseException)

BaseException

$ python3 tree.py
BaseException
    Exception
    GeneratorExit
    SystemExit
    KeyboardInterrupt

def tree(cls):
    yield cls.__name__, 0                        
    for sub_cls in cls.__subclasses__():         
        yield sub_cls.__name__, 1                


def display(cls):
    for cls_name, level in tree(cls):
        indent = ' ' * 4 * level                 
        print(f'{indent}{cls_name}')


if __name__ == '__main__':
    display(BaseException)

def tree(cls):
    yield cls.__name__, 0
    yield from sub_tree(cls)              


def sub_tree(cls):
    for sub_cls in cls.__subclasses__():
        yield sub_cls.__name__, 1         


def display(cls):
    for cls_name, level in tree(cls):     
        indent = ' ' * 4 * level
        print(f'{indent}{cls_name}')


if __name__ == '__main__':
    display(BaseException)

def tree(cls):
    yield cls.__name__, 0
    yield from sub_tree(cls)


def sub_tree(cls):
    for sub_cls in cls.__subclasses__():
        yield sub_cls.__name__, 1
        for sub_sub_cls in sub_cls.__subclasses__():
            yield sub_sub_cls.__name__, 2


def display(cls):
    for cls_name, level in tree(cls):
        indent = ' ' * 4 * level
        print(f'{indent}{cls_name}')


if __name__ == '__main__':
    display(BaseException)

$ python3 tree.py
BaseException
    Exception
        TypeError
        StopAsyncIteration
        StopIteration
        ImportError
        OSError
        EOFError
        RuntimeError
        NameError
        AttributeError
        SyntaxError
        LookupError
        ValueError
        AssertionError
        ArithmeticError
        SystemError
        ReferenceError
        MemoryError
        BufferError
        Warning
    GeneratorExit
    SystemExit
    KeyboardInterrupt

def sub_tree(cls):
    for sub_cls in cls.__subclasses__():
        yield sub_cls.__name__, 1
        for sub_sub_cls in sub_cls.__subclasses__():
            yield sub_sub_cls.__name__, 2
            for sub_sub_sub_cls in sub_sub_cls.__subclasses__():
                yield sub_sub_sub_cls.__name__, 3

def tree(cls):
    yield cls.__name__, 0
    yield from sub_tree(cls, 1)


def sub_tree(cls, level):
    for sub_cls in cls.__subclasses__():
        yield sub_cls.__name__, level
        yield from sub_tree(sub_cls, level+1)


def display(cls):
    for cls_name, level in tree(cls):
        indent = ' ' * 4 * level
        print(f'{indent}{cls_name}')


if __name__ == '__main__':
    display(BaseException)

def tree(cls, level=0):
    yield cls.__name__, level
    for sub_cls in cls.__subclasses__():
        yield from tree(sub_cls, level+1)


def display(cls):
    for cls_name, level in tree(cls):
        indent = ' ' * 4 * level
        print(f'{indent}{cls_name}')


if __name__ == '__main__':
    display(BaseException)

Python’s standard library has many functions that accept iterable arguments. In your code, such functions can be annotated like the zip_replace function we saw in Example 8-15, using collections.abc.Iterable (or typing.Iterable if you must support Python 3.8 or earlier, as explained in “Legacy Support and Deprecated Collection Types”). See Example 17-34.

from collections.abc import Iterable

FromTo = tuple[str, str]  

def zip_replace(text: str, changes: Iterable[FromTo]) -> str:  
    for from_, to in changes:
        text = text.replace(from_, to)
    return text

Define type alias; not required, but makes the next type hint more readable. Starting with Python 3.10, FromTo should have a type hint of typing.TypeAlias to clarify the reason for this line: FromTo: TypeAlias = tuple[str, str].

Annotate changes to accept an Iterable of FromTo tuples.

Iterator types don’t appear as often as Iterable types, but they are also simple to write. Example 17-35 shows the familiar Fibonacci generator, annotated.

from collections.abc import Iterator

def fibonacci() -> Iterator[int]:
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Note that the type Iterator is used for generators coded as functions with yield, as well as iterators written “by hand” as classes with __next__. There is also a collections.abc.Generator type (and the corresponding deprecated typing.Generator) that we can use to annotate generator objects, but it is needlessly verbose for generators used as iterators.

Example 17-36, when checked with Mypy, reveals that the Iterator type is really a simplified special case of the Generator type.

from collections.abc import Iterator
from keyword import kwlist
from typing import TYPE_CHECKING

short_kw = (k for k in kwlist if len(k) < 5)  

if TYPE_CHECKING:
    reveal_type(short_kw)  

long_kw: Iterator[str] = (k for k in kwlist if len(k) >= 4)  

if TYPE_CHECKING:  
    reveal_type(long_kw)

Generator expression that yields Python keywords with less than 5 characters.

Mypy infers: typing.Generator[builtins.str*, None, None].¹¹

This also yields strings, but I added an explicit type hint.

Revealed type: typing.Iterator[builtins.str].

abc.Iterator[str] is consistent-with abc.Generator[str, None, None], therefore Mypy issues no errors for type checking in Example 17-36.

Iterator[T] is a shortcut for Generator[T, None, None]. Both annotations mean “a generator that yields items of type T, but that does not consume or return values.” Generators able to consume and return values are coroutines, our next topic.

Classic Coroutines

Understanding classic coroutines in Python is confusing because they are actually generators used in a different way. So let’s step back and consider another feature of Python that can be used in two ways.

We saw in “Tuples Are Not Just Immutable Lists” that we can use tuple instances as records or as immutable sequences. When used as a record, a tuple is expected to have a specific number of items, and each item may have a different type. When used as immutable lists, a tuple can have any length, and all items are expected to have the same type. That’s why there are two different ways to annotate tuples with type hints:

# A city record with name, country, and population:
city: tuple[str, str, int]

# An immutable sequence of domain names:
domains: tuple[str, ...]

Something similar happens with generators. They are commonly used as iterators, but they can also be used as coroutines. A coroutine is really a generator function, created with the yield keyword in its body. And a coroutine object is physically a generator object. Despite sharing the same underlying implementation in C, the use cases of generators and coroutines in Python are so different that there are two ways to type hint them:

# The `readings` variable can be bound to an iterator
# or generator object that yields `float` items:
readings: Iterator[float]

# The `sim_taxi` variable can be bound to a coroutine
# representing a taxi cab in a discrete event simulation.
# It yields events, receives `float` timestamps, and returns
# the number of trips made during the simulation:
sim_taxi: Generator[Event, float, int]

The typing documentation describes the formal type parameters of Generator like this:

Generator[YieldType, SendType, ReturnType]

The SendType is only relevant when the generator is used as a coroutine. That type parameter is the type of x in the call gen.send(x). It is an error to call .send() on a generator that was coded to behave as an iterator instead of a coroutine. Likewise, ReturnType is only meaningful to annotate a coroutine, because iterators don’t return values like regular functions. The only sensible operation on a generator used as an iterator is to call next(it) directly or indirectly via for loops and other forms of iteration. The YieldType is the type of the value returned by a call to next(it).

The Generator type has the same type parameters as typing.Coroutine:

Coroutine[YieldType, SendType, ReturnType]

The typing.Coroutine documentation actually says: “The variance and order of type variables correspond to those of Generator.” But typing.Coroutine (deprecated) and collections.abc.Coroutine (generic since Python 3.9) are intended to annotate only native coroutines, not classic coroutines. If you want to use type hints with classic coroutines, you’ll suffer through the confusion of annotating them as Generator[YieldType, SendType, ReturnType].

David Beazley created some of the best talks and most comprehensive workshops about classic coroutines. In his PyCon 2009 course handout, he has a slide titled “Keeping It Straight,” which reads:

• Generators produce data for iteration

• Coroutines are consumers of data

• To keep your brain from exploding, don’t mix the two concepts together

• Coroutines are not related to iteration

• Note: There is a use of having `yield` produce a value in a coroutine, but it’s not tied to iteration.¹²

Now let’s see how classic coroutines work.

from collections.abc import Generator

def averager() -> Generator[float, float, None]:  
    total = 0.0
    count = 0
    average = 0.0
    while True:  
        term = yield average  
        total += term
        count += 1
        average = total/count

    >>> coro_avg = averager()  
    >>> next(coro_avg)  
    0.0
    >>> coro_avg.send(10)  
    10.0
    >>> coro_avg.send(30)
    20.0
    >>> coro_avg.send(5)
    15.0

    >>> coro_avg.send(20)  
    16.25
    >>> coro_avg.close()  
    >>> coro_avg.close()  
    >>> coro_avg.send(5)  
    Traceback (most recent call last):
      ...
    StopIteration

from collections.abc import Generator
from typing import Union, NamedTuple

class Result(NamedTuple):  
    count: int  # type: ignore  
    average: float

class Sentinel:  
    def __repr__(self):
        return f'<Sentinel>'

STOP = Sentinel()  

SendType = Union[float, Sentinel]  

SendType: TypeAlias = float | Sentinel