Generator Functions and Expressions

Unlike normal functions that return a value and exit, generator functions automatically suspend and resume their execution and state around the point of value generation. Because of that, they are often a useful alternative to both computing an entire series of values up front and manually saving and restoring state in classes. The state that generator functions retain when they are suspended includes both their code location, and their entire local scope. Hence, their local variables retain information between results, and make it available when the functions are resumed.

The chief code difference between generator and normal functions is that a generator yields a value, rather than returning one—the yield statement suspends the function and sends a value back to the caller, but retains enough state to enable the function to resume from where it left off. When resumed, the function continues execution immediately after the last yield run. From the function’s perspective, this allows its code to produce a series of values over time, rather than computing them all at once and sending them back in something like a list.

To truly understand generator functions, you need to know that they are closely bound up with the notion of the iteration protocol in Python. As we’ve seen, iterator objects define a __next__ method (next in 2.X), which either returns the next item in the iteration, or raises the special StopIteration exception to end the iteration. An iterable object’s iterator is fetched initially with the iter built-in function, though this step is a no-op for objects that are their own iterator.

Python for loops, and all other iteration contexts, use this iteration protocol to step through a sequence or value generator, if the protocol is supported (if not, iteration falls back on repeatedly indexing sequences instead). Any object that supports this interface works in all iteration tools.

To support this protocol, functions containing a yield statement are compiled specially as generators—they are not normal functions, but rather are built to return an object with the expected iteration protocol methods. When later called, they return a generator object that supports the iteration interface with an automatically created method named __next__ to start or resume execution.

Generator functions may also have a return statement that, along with falling off the end of the def block, simply terminates the generation of values—technically, by raising a StopIteration exception after any normal function exit actions. From the caller’s perspective, the generator’s __next__ method resumes the function and runs until either the next yield result is returned or a StopIteration is raised.

The net effect is that generator functions, coded as def statements containing yield statements, are automatically made to support the iteration object protocol and thus may be used in any iteration context to produce results over time and on demand.

To illustrate generator basics, let’s turn to some code. The following code defines a generator function that can be used to generate the squares of a series of numbers over time:

>>> def gensquares(N):
        for i in range(N):
            yield i ** 2        # Resume here later

This function yields a value, and so returns to its caller, each time through the loop; when it is resumed, its prior state is restored, including the last values of its variables i and N, and control picks up again immediately after the yield statement. For example, when it’s used in the body of a for loop, the first iteration starts the function and gets its first result; thereafter, control returns to the function after its yield statement each time through the loop:

>>> for i in gensquares(5):     # Resume the function
        print(i, end=' : ')     # Print last yielded value

0 : 1 : 4 : 9 : 16 :
>>>

To end the generation of values, functions either use a return statement with no value or simply allow control to fall off the end of the function body.

To most people, this process seems a bit implicit (if not magical) on first encounter. It’s actually quite tangible, though. If you really want to see what is going on inside the for, call the generator function directly:

>>> x = gensquares(4)
>>> x
<generator object gensquares at 0x000000000292CA68>

You get back a generator object that supports the iteration protocol we met in Chapter 14—the generator function was compiled to return this automatically. The returned generator object in turn has a __next__ method that starts the function or resumes it from where it last yielded a value, and raises a StopIteration exception when the end of the series of values is reached and the function returns. For convenience, the next(X) built-in calls an object’s X.__next__() method for us in 3.X (and X.next() in 2.X):

>>> next(x)                     # Same as x.__next__() in 3.X
0
>>> next(x)                     # Use x.next() or next() in 2.X
1
>>> next(x)
4
>>> next(x)
9
>>> next(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

As we learned in Chapter 14, for loops (and other iteration contexts) work with generators in the same way—by calling the __next__ method repeatedly, until an exception is caught. For a generator, the result is to produce yielded values over time. If the object to be iterated over does not support this protocol, for loops instead use the indexing protocol to iterate.

Notice that the top-level iter call of the iteration protocol isn’t required here because generators are their own iterator, supporting just one active iteration scan. To put that another way generators return themselves for iter, because they support next directly. This also holds true in the generator expressions we’ll meet later in this chapter (more on this ahead):

>>> y = gensquares(5)           # Returns a generator which is its own iterator
>>> iter(y) is y                # iter() is not required: a no-op here
True
>>> next(y)                     # Can run next()immediately
0

Given the simple examples we’re using to illustrate fundamentals, you might be wondering just why you’d ever care to code a generator at all. In this section’s example, for instance, we could also simply build the list of yielded values all at once:

>>> def buildsquares(n):
        res = []
        for i in range(n): res.append(i ** 2)
        return res

>>> for x in buildsquares(5): print(x, end=' : ')

0 : 1 : 4 : 9 : 16 :

For that matter, we could use any of the for loop, map, or list comprehension techniques:

>>> for x in [n ** 2 for n in range(5)]:
        print(x, end=' : ')

0 : 1 : 4 : 9 : 16 :

>>> for x in map((lambda n: n ** 2), range(5)):
        print(x, end=' : ')

0 : 1 : 4 : 9 : 16 :

However, generators can be better in terms of both memory use and performance in larger programs. They allow functions to avoid doing all the work up front, which is especially useful when the result lists are large or when it takes a lot of computation to produce each value. Generators distribute the time required to produce the series of values among loop iterations.

Moreover, for more advanced uses, generators can provide a simpler alternative to manually saving the state between iterations in class objects—with generators, variables accessible in the function’s scopes are saved and restored automatically.^[41] We’ll discuss class-based iterables in more detail in Part VI.

Generator functions are also much more broadly focused than implied so far. They can operate on and return any type of object, and as iterables may appear in any of Chapter 14’s iteration contexts, including tuple calls, enumerations, and dictionary comprehensions:

>>> def ups(line):
        for sub in line.split(','):               # Substring generator
            yield sub.upper()

>>> tuple(ups('aaa,bbb,ccc'))                     # All iteration contexts
('AAA', 'BBB', 'CCC')

>>> {i: s for (i, s) in enumerate(ups('aaa,bbb,ccc'))}
{0: 'AAA', 1: 'BBB', 2: 'CCC'}

In a moment we’ll see the same assets for generator expressions—a tool that trades function flexibility for comprehension conciseness. Later in this chapter we’ll also see that generators can sometimes make the impossible possible, by producing components of result sets that would be far too large to create all at once. First, though, let’s explore some advanced generator function features.

In Python 2.5, a send method was added to the generator function protocol. The send method advances to the next item in the series of results, just like __next__, but also provides a way for the caller to communicate with the generator, to affect its operation.

Technically, yield is now an expression form that returns the item passed to send, not a statement (though it can be called either way—as yield X, or A = (yield X)). The expression must be enclosed in parentheses unless it’s the only item on the right side of the assignment statement. For example, X = yield Y is OK, as is X = (yield Y) + 42.

When this extra protocol is used, values are sent into a generator G by calling G.send(value). The generator’s code is then resumed, and the yield expression in the generator returns the value passed to send. If the regular G.__next__() method (or its next(G) equivalent) is called to advance, the yield simply returns None. For example:

>>> def gen():
       for i in range(10):
           X = yield i
           print(X)

>>> G = gen()
>>> next(G)              # Must call next() first, to start generator
0
>>> G.send(77)           # Advance, and send value to yield expression
77
1
>>> G.send(88)
88
2
>>> next(G)              # next() and X.__next__() send None
None
3

The send method can be used, for example, to code a generator that its caller can terminate by sending a termination code, or redirect by passing a new position in data being processed inside the generator.

In addition, generators in 2.5 and later also support a throw(type) method to raise an exception inside the generator at the latest yield, and a close method that raises a special GeneratorExit exception inside the generator to terminate the iteration entirely. These are advanced features that we won’t delve into in more detail here; see reference texts and Python’s standard manuals for more information, and watch for more on exceptions in Part VII.

Note that while Python 3.X provides a next(X) convenience built-in that calls the X.__next__() method of an object, other generator methods, like send, must be called as methods of generator objects directly (e.g., G.send(X)). This makes sense if you realize that these extra methods are implemented on built-in generator objects only, whereas the __next__ method applies to all iterable objects—both built-in types and user-defined classes.

Also note that Python 3.3 introduces an extension to yield—a from clause—that allows generators to delegate to nested generators. Since this is an extension to what is already a fairly advanced topic, we’ll delegate this topic itself to a sidebar, and move on here to a tool that’s close enough to be called a twin.

Just like generator functions, generator expressions are a memory-space optimization—they do not require the entire result list to be constructed all at once, as the square-bracketed list comprehension does. Also like generator functions, they divide the work of results production into smaller time slices—they yield results in piecemeal fashion, instead of making the caller wait for the full set to be created in a single call.

On the other hand, generator expressions may also run slightly slower than list comprehensions in practice, so they are probably best used only for very large result sets, or applications that cannot wait for full results generation. A more authoritative statement about performance, though, will have to await the timing scripts we’ll code in the next chapter.

Though more subjective, generator expressions offer coding advantages too—as the next sections show.

One way to see the coding benefits of generator expressions is to compare them to other functional tools, as we did for list comprehensions. For example, generator expressions often are equivalent to 3.X map calls, because both generate result items on request. Like list comprehensions, though, generator expressions may be simpler to code when the operation applied is not a function call. In 2.X, map makes temporary lists and generator expressions do not, but the same coding comparisons apply:

>>> list(map(abs, (−1, −2, 3, 4)))                          # Map function on tuple
[1, 2, 3, 4]
>>> list(abs(x) for x in (−1, −2, 3, 4))                    # Generator expression
[1, 2, 3, 4]

>>> list(map(lambda x: x * 2, (1, 2, 3, 4)))                # Nonfunction case
[2, 4, 6, 8]
>>> list(x * 2 for x in (1, 2, 3, 4))                       # Simpler as generator?
[2, 4, 6, 8]

The same holds true for text-processing use cases like the join call we saw earlier—a list comprehension makes an extra temporary list of results, which is completely pointless in this context because the list is not retained, and map loses simplicity points compared to generator expression syntax when the operation being applied is not a call:

>>> line = 'aaa,bbb,ccc'
>>> ''.join([x.upper() for x in line.split(',')])           # Makes a pointless list
'AAABBBCCC'

>>> ''.join(x.upper() for x in line.split(','))             # Generates results
'AAABBBCCC'
>>> ''.join(map(str.upper, line.split(',')))                # Generates results
'AAABBBCCC'

>>> ''.join(x * 2 for x in line.split(','))                 # Simpler as generator?
'aaaaaabbbbbbcccccc'
>>> ''.join(map(lambda x: x * 2, line.split(',')))
'aaaaaabbbbbbcccccc'

Both map and generator expressions can also be arbitrarily nested, which supports general use in programs, and requires a list call or other iteration context to start the process of producing results. For example, the list comprehension in the following produces the same result as the 3.X map and generator equivalents that follow it, but makes two physical lists; the others generate just one integer at a time with nested generators, and the generator expression form may more clearly reflect its intent:

>>> [x * 2 for x in [abs(x) for x in (−1, −2, 3, 4)]]       # Nested comprehensions
[2, 4, 6, 8]

>>> list(map(lambda x: x * 2, map(abs, (−1, −2, 3, 4))))    # Nested maps
[2, 4, 6, 8]

>>> list(x * 2 for x in (abs(x) for x in (−1, −2, 3, 4)))   # Nested generators
[2, 4, 6, 8]

Although the effect of all three of these is to combine operations, the generators do so without making multiple temporary lists. In 3.X, the next example both nests and combines generators—the nested generator expression is activated by map, which in turn is only activated by list.

>>> import math
>>> list(map(math.sqrt, (x ** 2 for x in range(4))))        # Nested combinations
[0.0, 1.0, 2.0, 3.0]

Technically speaking, the range on the right in the preceding is a value generator in 3.X too, activated by the generator expression itself—three levels of value generation, which produce individual values from inner to outer only on request, and which “just works” because of Python’s iteration tools and protocol. In fact, generator nestings can be arbitrarily mixed and deep, though some may be more valid than others:

>>> list(map(abs, map(abs, map(abs, (−1, 0, 1)))))          # Nesting gone bad?
[1, 0, 1]
>>> list(abs(x) for x in (abs(x) for x in (abs(x) for x in (−1, 0, 1))))
[1, 0, 1]

These last examples illustrate how general generators can be, but are also coded in an intentionally complex form to underscore that generator expressions have the same potential for abuse as the list comprehensions discussed earlier—as usual, you should keep them simple unless they must be complex, a theme we’ll revisit later in this chapter.

When used well, though, generator expressions combine the expressiveness of list comprehensions with the space and time benefits of other iterables. Here, for example, nonnested approaches provide simpler solutions but still leverage generators’ strengths—per a Python motto, flat is generally better than nested:

>>> list(abs(x) * 2 for x in (−1, −2, 3, 4))                # Unnested equivalents
[2, 4, 6, 8]
>>> list(math.sqrt(x ** 2) for x in range(4))               # Flat is often better
[0.0, 1.0, 2.0, 3.0]
>>> list(abs(x) for x in (−1, 0, 1))
[1, 0, 1]

Generator expressions also support all the usual list comprehension syntax—including if clauses, which work like the filter call we met earlier. Because filter is an iterable in 3.X that generates its results on request, a generator expression with an if clause is operationally equivalent (in 2.X, filter produces a temporary list that the generator does not, but the code comparisons again apply). Again, the join in the following suffices to force all forms to produce their results:

>>> line = 'aa bbb c'
>>> ''.join(x for x in line.split() if len(x) > 1)          # Generator with 'if'
'aabbb'
>>> ''.join(filter(lambda x: len(x) > 1, line.split()))     # Similar to filter
'aabbb'

The generator seems marginally simpler than the filter here. As for list comprehensions, though, adding processing steps to filter results requires a map too, which makes filter noticeably more complex than a generator expression:

>>> ''.join(x.upper() for x in line.split() if len(x) > 1)
'AABBB'
>>> ''.join(map(str.upper, filter(lambda x: len(x) > 1, line.split())))
'AABBB'

In effect, generator expressions do for 3.X iterables like map and filter what list comprehensions do for the 2.X list-builder flavors of these calls—they provide more general coding structures that do not rely on functions, but still delay results production. Also like list comprehensions, there is always a statement-based equivalent to a generator expression, though it sometimes renders substantially more code:

>>> ''.join(x.upper() for x in line.split() if len(x) > 1)
'AABBB'

>>> res = ''
>>> for x in line.split():                                   # Statement equivalent?
        if len(x) > 1:                                       # This is also a join
            res += x.upper()

>>> res
'AABBB'

In this case, though, the statement form isn’t quite the same—it cannot produce items one at a time, and it’s also emulating the effect of the join that forces results to be produced all at once. The true equivalent to a generator expression would be a generator function with a yield, as the next section shows.

Though beyond this book’s scope, many Python standard library tools generate values today too, including email parsers, and the standard directory walker—which at each level of a tree yields a tuple of the current directory, its subdirectories, and its files:

>>> import os
>>> for (root, subs, files) in os.walk('.'):         # Directory walk generator
        for name in files:                           # A Python 'find' operation
            if name.startswith('call'):
                print(root, name)

. callables.py
.\dualpkg callables.py

In fact, os.walk is coded as a recursive function in Python in its os.py standard library file, in C:\Python33\Lib on Windows. Because it uses yield (and in 3.3 yield from instead of a for loop) to return results, it’s a normal generator function, and hence an iterable object:

>>> G = os.walk(r'C:\code\pkg')
>>> iter(G) is G                     # Single-scan iterator: iter(G) optional
True
>>> I = iter(G)
>>> next(I)
('C:\\code\\pkg', ['__pycache__'], ['eggs.py', 'eggs.pyc', 'main.py', ...etc...])
>>> next(I)
('C:\\code\\pkg\\__pycache__', [], ['eggs.cpython-33.pyc', ...etc...])
>>> next(I)
StopIteration

By yielding results as it goes, the walker does not require its clients to wait for an entire tree to be scanned. See Python’s manuals and follow-up books such as Programming Python for more on this tool. Also see Chapter 14 and others for os.popen—a related iterable used to run a shell command and read its output.

In Chapter 18, we noted that starred arguments can unpack an iterable into individual arguments. Now that we’ve seen generators, we can also see what this means in code. In both 3.X and 2.X (though 2.X’s range is a list):

>>> def f(a, b, c): print('%s, %s, and %s' % (a, b, c))

>>> f(0, 1, 2)                       # Normal positionals
0, 1, and 2
>>> f(*range(3))                     # Unpack range values: iterable in 3.X
0, 1, and 2
>>> f(*(i for i in range(3)))        # Unpack generator expression values
0, 1, and 2

This applies to dictionaries and views too (though dict.values is also a list in 2.X, and order is arbitrary when passing values by position):

>>> D = dict(a='Bob', b='dev', c=40.5); D
{'b': 'dev', 'c': 40.5, 'a': 'Bob'}
>>> f(a='Bob', b='dev', c=40.5)      # Normal keywords
Bob, dev, and 40.5
>>> f(**D)                           # Unpack dict: key=value
Bob, dev, and 40.5
>>> f(*D)                            # Unpack keys iterator
b, c, and a
>>> f(*D.values())                   # Unpack view iterator: iterable in 3.X
dev, 40.5, and Bob

Because the built-in print function in 3.X prints all its variable number of arguments, this also makes the following three forms equivalent—the latter using a * to unpack the results forced from a generator expression (though the second also creates a list of return values, and the first may leave your cursor at the end of the output line in some shells, but not in the IDLE GUI):

>>> for x in 'spam': print(x.upper(), end=' ')
S P A M

>>> list(print(x.upper(), end=' ') for x in 'spam')
S P A M [None, None, None, None]

>>> print(*(x.upper() for x in 'spam'))
S P A M

See Chapter 14 for an additional example that unpacks a file’s lines by iterator into arguments.

Although beyond the scope of this chapter, it is also possible to implement arbitrary user-defined generator objects with classes that conform to the iteration protocol. Such classes define a special __iter__ method run by the iter built-in function, which in turn returns an object having a __next__ method (next in 2.X) run by the next built-in function:

class SomeIterable:
    def __init__(...): ...     # On iter(): return self or supplemental object
    def __next__(...): ...     # On next(): coded here, or in another class

As the prior section suggested, these classes usually return their objects directly for single-iteration behavior, or a supplemental object with scan-specific state for multiple-scan support.

Alternatively, a user-defined iterable class’s method functions can sometimes use yield to transform themselves into generators, with an automatically created __next__ method—a common application of yield we’ll meet in Chapter 30 that is both wildly implicit and potentially useful! A __getitem__ indexing method is also available as a fallback option for iteration, though this is often not as flexible as the __iter__ and __next__ scheme (but has advantages for coding sequences).

The instance objects created from such a class are considered iterable and may be used in for loops and all other iteration contexts. With classes, though, we have access to richer logic and data structuring options, such as inheritance, that other generator constructs cannot offer by themselves. By coding methods, classes also can make iteration behavior much more explicit than the “magic” generator objects associated with built-in types and generator functions and expressions (though classes wield some magic of their own).

Hence, the iterator and generator story won’t really be complete until we’ve seen how it maps to classes, too. For now, we’ll have to settle for postponing its conclusion—and its final sequel—until we study class-based iterables in Chapter 30.

As coded in Chapter 18, we can reorder a sequence with slicing and concatenation, moving the front item to the end on each loop; slicing instead of indexing the item allows + to work for arbitrary sequence types:

>>> L, S = [1, 2, 3], 'spam'
>>> for i in range(len(S)):            # For repeat counts 0..3
        S = S[1:] + S[:1]              # Move front item to the end
        print(S, end=' ')

pams amsp mspa spam

>>> for i in range(len(L)):
        L = L[1:] + L[:1]              # Slice so any sequence type works
        print(L, end=' ')

[2, 3, 1] [3, 1, 2] [1, 2, 3]

Alternatively, as we saw in Chapter 13, we get the same results by moving an entire front section to the end, though the order of the results varies slightly:

>>> for i in range(len(S)):            # For positions 0..3
        X = S[i:] + S[:i]              # Rear part + front part (same effect)
        print(X, end=' ')

spam pams amsp mspa

As is, this code works on specific named variables only. To generalize, we can turn it into a simple function to work on any object passed to its argument and return a result; since the first of these exhibits the classic list comprehension pattern, we can save some work by coding it as such in the second:

>>> def scramble(seq):
        res = []
        for i in range(len(seq)):
            res.append(seq[i:] + seq[:i])
        return res

>>> scramble('spam')
['spam', 'pams', 'amsp', 'mspa']

>>> def scramble(seq):
        return [seq[i:] + seq[:i] for i in range(len(seq))]

>>> scramble('spam')
['spam', 'pams', 'amsp', 'mspa']

>>> for x in scramble((1, 2, 3)):
        print(x, end=' ')

(1, 2, 3) (2, 3, 1) (3, 1, 2)

We could use recursion here as well, but it’s probably overkill in this context.

The preceding section’s simple approach works, but must build an entire result list in memory all at once (not great on memory usage if it’s massive), and requires the caller to wait until the entire list is complete (less than ideal if this takes a substantial amount of time). We can do better on both fronts by translating this to a generator function that yields one result at a time, using either coding scheme:

>>> def scramble(seq):
        for i in range(len(seq)):
            seq = seq[1:] + seq[:1]              # Generator function
            yield seq                            # Assignments work here

>>> def scramble(seq):
        for i in range(len(seq)):                # Generator function
            yield seq[i:] + seq[:i]              # Yield one item per iteration

>>> list(scramble('spam'))                       # list()generates all results
['spam', 'pams', 'amsp', 'mspa']
>>> list(scramble((1, 2, 3)))                    # Any sequence type works
[(1, 2, 3), (2, 3, 1), (3, 1, 2)]
>>>
>>> for x in scramble((1, 2, 3)):                # for loops generate results
        print(x, end=' ')

(1, 2, 3) (2, 3, 1) (3, 1, 2)

Generator functions retain their local scope state while active, minimize memory space requirements, and divide the work into shorter time slices. As full functions, they are also very general. Importantly, for loops and other iteration tools work the same whether stepping through a real list or a generator of values—the function can select between the two schemes freely, and even change strategies in the future.

As we’ve seen, generator expressions—comprehensions in parentheses instead of square brackets—also generate values on request and retain their local state. They’re not as flexible as full functions, but because they yield their values automatically, expressions can often be more concise in specific use cases like this:

>>> S
'spam'
>>> G = (S[i:] + S[:i] for i in range(len(S)))   # Generator expression equivalent
>>> list(G)
['spam', 'pams', 'amsp', 'mspa']

Notice that we can’t use the assignment statement of the first generator function version here, because generator expressions cannot contain statements. This makes them a bit narrower in scope; in many cases, though, expressions can do similar work, as shown here. To generalize a generator expression for an arbitrary subject, wrap it in a simple function that takes an argument and returns a generator that uses it:

>>> F = lambda seq: (seq[i:] + seq[:i] for i in range(len(seq)))
>>> F(S)
<generator object <genexpr> at 0x00000000029883F0>
>>>
>>> list(F(S))
['spam', 'pams', 'amsp', 'mspa']
>>> list(F([1, 2, 3]))
[[1, 2, 3], [2, 3, 1], [3, 1, 2]]

>>> for x in F((1, 2, 3)):
        print(x, end=' ')

(1, 2, 3) (2, 3, 1) (3, 1, 2)

Finally, we can use either the generator function or its expression equivalent in Chapter 18’s tester to produce scrambled arguments—the sequence scrambling function becomes a tool we can use in other contexts:

# file scramble.py

def scramble(seq):
    for i in range(len(seq)):                # Generator function
        yield seq[i:] + seq[:i]              # Yield one item per iteration

scramble2 = lambda seq: (seq[i:] + seq[:i] for i in range(len(seq)))

And by moving the values generation out to an external tool, the tester becomes simpler:

>>> from scramble import scramble
>>> from inter2 import intersect, union
>>>
>>> def tester(func, items, trace=True):
        for args in scramble(items):         # Use generator (or: scramble2(items))
            if trace: print(args)
            print(sorted(func(*args)))

>>> tester(intersect, ('aab', 'abcde', 'ababab'))
('aab', 'abcde', 'ababab')
['a', 'b']
('abcde', 'ababab', 'aab')
['a', 'b']
('ababab', 'aab', 'abcde')
['a', 'b']

>>> tester(intersect, ([1, 2], [2, 3, 4], [1, 6, 2, 7, 3]), False)
[2]
[2]
[2]

These techniques have many other real-world applications—consider generating attachments in an email message or points to be plotted in a GUI. Moreover, other types of sequence scrambles serve central roles in other applications, from searches to mathematics. As is, our sequence scrambler is a simple reordering, but some programs warrant the more exhaustive set of all possible orderings we get from permutations—produced using recursive functions in both list-builder and generator forms by the following module file:

# File permute.py

def permute1(seq):
    if not seq:                               # Shuffle any sequence: list
        return [seq]                          # Empty sequence
    else:
        res = []
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]        # Delete current node
            for x in permute1(rest):          # Permute the others
                res.append(seq[i:i+1] + x)    # Add node at front
        return res

def permute2(seq):
    if not seq:                               # Shuffle any sequence: generator
        yield seq                             # Empty sequence
    else:
        for i in range(len(seq)):
            rest = seq[:i] + seq[i+1:]        # Delete current node
            for x in permute2(rest):          # Permute the others
                yield seq[i:i+1] + x          # Add node at front

Both of these functions produce the same results, though the second defers much of its work until it is asked for a result. This code is a bit advanced, especially the second of these functions (and to some Python newcomers might even be categorized as cruel and inhumane punishment!). Still, as I’ll explain in a moment, there are cases where the generator approach can be highly useful.

Study and test this code for more insight, and add prints to trace if it helps. If it’s still a mystery, try to make sense of the first version first; remember that generator functions simply return objects with methods that handle next operations run by for loops at each level, and don’t produce any results until iterated; and trace through some of the following examples to see how they’re handled by this code.

Permutations produce more orderings than the original shuffler—for N items, we get N! (factorial) results instead of just N (24 for 4: 4 * 3 * 2 * 1). In fact, that’s why we need recursion here: the number of nested loops is arbitrary, and depends on the length of the sequence permuted:

>>> from scramble import scramble
>>> from permute import permute1, permute2

>>> list(scramble('abc'))                            # Simple scrambles: N
['abc', 'bca', 'cab']

>>> permute1('abc')                                  # Permutations larger: N!
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
>>> list(permute2('abc'))                            # Generate all combinations
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

>>> G = permute2('abc')                              # Iterate (iter() not needed)
>>> next(G)
'abc'
>>> next(G)
'acb'
>>> for x in permute2('abc'): print(x)               # Automatic iteration
...prints six lines...

The list and generator versions’ results are the same, though the generator minimizes both space usage and delays for results. For larger items, the set of all permutations is much larger than the simpler scrambler’s:

>>> permute1('spam') == list(permute2('spam'))
True
>>> len(list(permute2('spam'))), len(list(scramble('spam')))
(24, 4)

>>> list(scramble('spam'))
['spam', 'pams', 'amsp', 'mspa']
>>> list(permute2('spam'))
['spam', 'spma', 'sapm', 'samp', 'smpa', 'smap', 'psam', 'psma', 'pasm', 'pams',
 'pmsa', 'pmas', 'aspm', 'asmp', 'apsm', 'apms', 'amsp', 'amps', 'mspa', 'msap',
 'mpsa', 'mpas', 'masp', 'maps']

Per Chapter 19, there are nonrecursive alternatives here too, using explicit stacks or queues, and other sequence orderings are common (e.g., fixed-size subsets and combinations that filter out duplicates of differing order), but these require coding extensions we’ll forgo here. See the book Programming Python for more on this theme, or experiment further on your own.

That being said, there are specific use cases that generators can address well. They can reduce memory footprint in some programs, reduce delays in others, and can occasionally make the impossible possible. Consider, for example, a program that must produce all possible permutations of a nontrivial sequence. Since the number of combinations is a factorial that explodes exponentially, the preceding permute1 recursive list-builder function will either introduce a noticeable and perhaps interminable pause or fail completely due to memory requirements, whereas the permute2 recursive generator will not—it returns each individual result quickly, and can handle very large result sets:

>>> import math
>>> math.factorial(10)               # 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
3628800
>>> from permute import permute1, permute2
>>> seq = list(range(10))
>>> p1 = permute1(seq)               # 37 seconds on a 2GHz quad-core machine
                                     # Creates a list of 3.6M numbers
>>> len(p1), p1[0], p1[1]
(3628800, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 9, 8])

In this case, the list builder pauses for 37 seconds on my computer to build a 3.6-million-item list, but the generator can begin returning results immediately:

>>> p2 = permute2(seq)               # Returns generator immediately
>>> next(p2)                         # And produces each result quickly on request
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> next(p2)
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]

>>> p2 = list(permute2(seq))         # About 28 seconds, though still impractical
>>> p1 == p2                         # Same set of results generated
True

Naturally, we might be able to optimize the list builder’s code to run quicker (e.g., an explicit stack instead of recursion might change its performance), but for larger sequences, it’s not an option at all—at just 50 items, the number of permutations precludes building a results list, and would take far too long for mere mortals like us (and larger values will overflow the preset recursion stack depth limit: see the preceding chapter). The generator, however, is still viable—it is able to produce individual results immediately:

>>> math.factorial(50)
30414093201713378043612608166064768844377641568960512000000000000
>>> p3 = permute2(list(range(50)))
>>> next(p3)                         # permute1 is not an option here!
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
44, 45, 46, 47, 48, 49]

For more fun—and to yield results that are more variable and less obviously deterministic—we could also use Python’s random module of Chapter 5 to randomly shuffle the sequence to be permuted before the permuter begins its work. (In fact, we might be able to use the random shuffler as a permutation generator in general, as long as we either can assume that it won’t repeat shuffles during the time we consume them, or test its results against prior shuffles to avoid repeats—and hope that we do not live in the strange universe where a random sequence repeats the same result an infinite number of times!). In the following, each permute2 and next call returns immediately as before, but a permute1 hangs:

>>> import random
>>> math.factorial(20)               # permute1 is not an option here
2432902008176640000
>>> seq = list(range(20))

>>> random.shuffle(seq)              # Shuffle sequence randomly first
>>> p = permute2(seq)
>>> next(p)
[10, 17, 4, 14, 11, 3, 16, 19, 12, 8, 6, 5, 2, 15, 18, 7, 1, 0, 13, 9]
>>> next(p)
[10, 17, 4, 14, 11, 3, 16, 19, 12, 8, 6, 5, 2, 15, 18, 7, 1, 0, 9, 13]

>>> random.shuffle(seq)
>>> p = permute2(seq)
>>> next(p)
[16, 1, 5, 14, 15, 12, 0, 2, 6, 19, 10, 17, 11, 18, 13, 7, 4, 9, 8, 3]
>>> next(p)
[16, 1, 5, 14, 15, 12, 0, 2, 6, 19, 10, 17, 11, 18, 13, 7, 4, 9, 3, 8]

The main point here is that generators can sometimes produce results from large solution sets when list builders cannot. Then again, it’s not clear how common such use cases may be in the real world, and this doesn’t necessarily justify the implicit flavor of value generation that we get with generator functions and expressions. As we’ll see in Part VI, value generation can also be coded as iterable objects with classes. Class-based iterables can produce items on request too, and are far more explicit than the magic objects and methods produced for generator functions and expressions.

Part of programming is finding a balance among tradeoffs like these, and there are no absolute rules here. While the benefits of generators may sometimes justify their use, maintainability should always be a top priority too. Like comprehensions, generators also offer an expressiveness and code economy that’s hard to resist if you understand how they work—but you’ll want to weigh this against the frustration of coworkers who might not.

Although the map and zip built-ins are fast and convenient, it’s always possible to emulate them in code of our own. In the preceding chapter, for example, we saw a function that emulated the map built-in for a single sequence (or other iterable) argument. It doesn’t take much more work to allow for multiple sequences, as the built-in does:

# map(func, seqs...) workalike with zip

def mymap(func, *seqs):
    res = []
    for args in zip(*seqs):
        res.append(func(*args))
    return res

print(mymap(abs, [-2, −1, 0, 1, 2]))
print(mymap(pow, [1, 2, 3], [2, 3, 4, 5]))

This version relies heavily upon the special *args argument-passing syntax—it collects multiple sequence (really, iterable) arguments, unpacks them as zip arguments to combine, and then unpacks the paired zip results as arguments to the passed-in function. That is, we’re using the fact that the zipping is essentially a nested operation in mapping. The test code at the bottom applies this to both one and two sequences to produce this output—the same we would get with the built-in map (this code is in file mymap.py in the book’s examples if you want to run it live):

[2, 1, 0, 1, 2]
[1, 8, 81]

Really, though, the prior version exhibits the classic list comprehension pattern, building a list of operation results within a for loop. We can code our map more concisely as an equivalent one-line list comprehension:

# Using a list comprehension

def mymap(func, *seqs):
    return [func(*args) for args in zip(*seqs)]

print(mymap(abs, [−2, −1, 0, 1, 2]))
print(mymap(pow, [1, 2, 3], [2, 3, 4, 5]))

When this is run the result is the same as before, but the code is more concise and might run faster (more on performance in the section Timing Iteration Alternatives). Both of the preceding mymap versions build result lists all at once, though, and this can waste memory for larger lists. Now that we know about generator functions and expressions, it’s simple to recode both these alternatives to produce results on demand instead:

# Using generators: yield and (...)

def mymap(func, *seqs):
    res = []
    for args in zip(*seqs):
        yield func(*args)

def mymap(func, *seqs):
    return (func(*args) for args in zip(*seqs))

These versions produce the same results but return generators designed to support the iteration protocol—the first yields one result at a time, and the second returns a generator expression’s result to do the same. They produce the same results if we wrap them in list calls to force them to produce their values all at once:

print(list(mymap(abs, [−2, −1, 0, 1, 2])))
print(list(mymap(pow, [1, 2, 3], [2, 3, 4, 5])))

No work is really done here until the list calls force the generators to run, by activating the iteration protocol. The generators returned by these functions themselves, as well as that returned by the Python 3.X flavor of the zip built-in they use, produce results only on demand.

Of course, much of the magic in the examples shown so far lies in their use of the zip built-in to pair arguments from multiple sequences or iterables. Our map workalikes are also really emulating the behavior of the Python 3.X map—they truncate at the length of the shortest argument, and they do not support the notion of padding results when lengths differ, as map does in Python 2.X with a None argument:

C:code> c:\python27\python
>>> map(None, [1, 2, 3], [2, 3, 4, 5])
[(1, 2), (2, 3), (3, 4), (None, 5)]
>>> map(None, 'abc', 'xyz123')
[('a', 'x'), ('b', 'y'), ('c', 'z'), (None, '1'), (None, '2'), (None, '3')]

Using iteration tools, we can code workalikes that emulate both truncating zip and 2.X’s padding map—these turn out to be nearly the same in code:

# zip(seqs...) and 2.X map(None, seqs...) workalikes

def myzip(*seqs):
    seqs = [list(S) for S in seqs]
    res  = []
    while all(seqs):
        res.append(tuple(S.pop(0) for S in seqs))
    return res

def mymapPad(*seqs, pad=None):
    seqs = [list(S) for S in seqs]
    res  = []
    while any(seqs):
        res.append(tuple((S.pop(0) if S else pad) for S in seqs))
    return res

S1, S2 = 'abc', 'xyz123'
print(myzip(S1, S2))
print(mymapPad(S1, S2))
print(mymapPad(S1, S2, pad=99))

Both of the functions coded here work on any type of iterable object, because they run their arguments through the list built-in to force result generation (e.g., files would work as arguments, in addition to sequences like strings). Notice the use of the all and any built-ins here—these return True if all and any items in an iterable are True (or equivalently, nonempty), respectively. These built-ins are used to stop looping when any or all of the listified arguments become empty after deletions.

Also note the use of the Python 3.X keyword-only argument, pad; unlike the 2.X map, our version will allow any pad object to be specified (if you’re using 2.X, use a **kargs form to support this option instead; see Chapter 18 for details). When these functions are run, the following results are printed—a zip, and two padding maps:

[('a', 'x'), ('b', 'y'), ('c', 'z')]
[('a', 'x'), ('b', 'y'), ('c', 'z'), (None, '1'), (None, '2'), (None, '3')]
[('a', 'x'), ('b', 'y'), ('c', 'z'), (99, '1'), (99, '2'), (99, '3')]

These functions aren’t amenable to list comprehension translation because their loops are too specific. As before, though, while our zip and map workalikes currently build and return result lists, it’s just as easy to turn them into generators with yield so that they each return one piece of their result set at a time. The results are the same as before, but we need to use list again to force the generators to yield their values for display:

# Using generators: yield

def myzip(*seqs):
    seqs = [list(S) for S in seqs]
    while all(seqs):
        yield tuple(S.pop(0) for S in seqs)

def mymapPad(*seqs, pad=None):
    seqs = [list(S) for S in seqs]
    while any(seqs):
        yield tuple((S.pop(0) if S else pad) for S in seqs)

S1, S2 = 'abc', 'xyz123'
print(list(myzip(S1, S2)))
print(list(mymapPad(S1, S2)))
print(list(mymapPad(S1, S2, pad=99)))

Finally, here’s an alternative implementation of our zip and map emulators—rather than deleting arguments from lists with the pop method, the following versions do their job by calculating the minimum and maximum argument lengths. Armed with these lengths, it’s easy to code nested list comprehensions to step through argument index ranges:

# Alternate implementation with lengths

def myzip(*seqs):
    minlen = min(len(S) for S in seqs)
    return [tuple(S[i] for S in seqs) for i in range(minlen)]

def mymapPad(*seqs, pad=None):
    maxlen = max(len(S) for S in seqs)
    index  = range(maxlen)
    return [tuple((S[i] if len(S) > i else pad) for S in seqs) for i in index]

S1, S2 = 'abc', 'xyz123'
print(myzip(S1, S2))
print(mymapPad(S1, S2))
print(mymapPad(S1, S2, pad=99))

Because these use len and indexing, they assume that arguments are sequences or similar, not arbitrary iterables, much like our earlier sequence scramblers and permuters. The outer comprehensions here step through argument index ranges, and the inner comprehensions (passed to tuple) step through the passed-in sequences to pull out arguments in parallel. When they’re run, the results are as before.

Most strikingly, generators and iterators seem to run rampant in this example. The arguments passed to min and max are generator expressions, which run to completion before the nested comprehensions begin iterating. Moreover, the nested list comprehensions employ two levels of delayed evaluation—the Python 3.X range built-in is an iterable, as is the generator expression argument to tuple.

In fact, no results are produced here until the square brackets of the list comprehensions request values to place in the result list—they force the comprehensions and generators to run. To turn these functions themselves into generators instead of list builders, use parentheses instead of square brackets again. Here’s the case for our zip:

# Using generators: (...)

def myzip(*seqs):
    minlen = min(len(S) for S in seqs)
    return (tuple(S[i] for S in seqs) for i in range(minlen))

S1, S2 = 'abc', 'xyz123'
print(list(myzip(S1, S2)))         # Go!... [('a', 'x'), ('b', 'y'), ('c', 'z')]

In this case, it takes a list call to activate the generators and other iterables to produce their results. Experiment with these on your own for more details. Developing further coding alternatives is left as a suggested exercise (see also the sidebar Why You Will Care: One-Shot Iterations for investigation of one such option).

def myzip(*args):
    iters = map(iter, args)
    while iters:
        res = [next(i) for i in iters]
        yield tuple(res)

>>> list(myzip('abc', 'lmnop'))
[('a', 'l'), ('b', 'm'), ('c', 'n')]

def myzip(*args):
    iters = list(map(iter, args))       # Allow multiple scans
    ...rest as is...