Tags

, , ,

Last time I began exploring Python generator functions. I mostly covered their basic function as iterables, and why they’re good in for-loops. They’re also good for infinite lists. Much of their value lies in how they defer processing an item until it is actually asked for.

This time I’ll dig into the send method, which allows sending messages to a running generator. I’ll also introduce the yield from statement, which allows us to wrap a generator with another function that also acts like a generator.

In this post some our generators will create Collatz sequences. These come from an unsolved problem in mathematics called the Collatz conjecture. It’s called a lot of other things as well, because lots of people discovered it. (I’ve mentioned it before. It’s another cool example of how a simple rule can lead to a complex structure.)

A Collatz sequence starts with a positive integer, N:

  1. If N is even, divide it by two (÷ 2).
  2. If N is odd, multiply it by three and add 1 (3n+1).

In either case, we get a new value for N. We re-apply this rule over and over until N=1. The Collatz sequence is the chain of numbers from the starting value to the last value, 1.

The Collatz conjecture — so far unproven, but true in all tested cases — is that this process always converges on N=1. No matter what number we start with, we always end up with 1.

Our generator will take an integer and return its Collatz sequence. We’ll also consider a multi-sequence wrapper function that shows off the yield from statement.

§ §

Given some positive integer, N, calculating the next number per the two rules above is very easy, especially in Python using a lambda expression:

# Calculate and return the next Collatz number...
Collatz = lambda n:(0) if abs(n)==1 \
          else (((n*3)+1) if (n%2) else (n//2))

# Calculate and return the next Collatz number (pure)...
Collatz0 = lambda n:(((n*3)+1) if (n % 2) else (n//2))
#

I do love a good lambda expression, but I had to continue the first one onto a second line to make it fit the blog column. The “pure” version (second) is fine (canonical, in fact), but has some caveats. In any event, it’s easier to discuss if we re-write it as a function:

# Same as the first lambda expression above...
def Collatz (n):
    '''Calculate and return the next Collatz number.'''
    if abs(n) == 1:
        return 0
    if n % 2:
        return ((n*3) + 1)
    return (n // 2)
#

The extra bit at the beginning, lines #4 and #5 (the lack of which makes the second lambda expression “pure”) puts both +1 and -1 on the same special footing — the return value in either case is zero. This does two things. Firstly, it lets the sequence terminate nicely. See for yourself what the “pure” function returns as Collatz(1). Secondly, it allows negative number Collatz sequences. (All of which is a topic for another post.)

Lines #6 and #7 handle the case where N is odd, and line #8 handles the even case.

§

Given our Collatz function, our sequence generator looks like this:

def gen_collatz_1 (n):
    '''A Collatz sequence generator function.'''
    steps = 1
    while 1 < n:
        yield n
        # Calculate next Collatz number...
        n = Collatz(n)
        # Count steps as we go...
        steps += 1
    # Final yield when n==1...
    yield n
    return steps

# Get the Collatz sequence for N=11...
cs = list(gen_collatz_1(11))
print(cs)
print()
#

Note that the generator returns the number of steps it took to reach 1. In the previous post I had a generator that returned a value, but that value didn’t appear to show up any place. Now we’ll find out what happened to it. (It’s just a frill; it’s not important to the sequence generation, but it does illustrate what happens to return values.)

To see where the return value goes, run the following snippet (or type it into a Python prompt):

# Reveal the return value...
# Use a number that returns a short sequence...
g = gen_collatz_1(8)
print('#1 %s' % next(g))
print('#2 %s' % next(g))
print('#3 %s' % next(g))
print('#4 %s' % next(g))
print('#5 %s' % next(g))
#

Here’s the result:

#1 8
#2 4
#3 2
#4 1
Traceback (most recent call last):
  File "generators.py", line 357, in <module>
    print('#5 %s' % next(g))
StopIteration: 4

Notice the last line. The generator puts any return value from the function into the StopIteration exception. If there is no explicit return statement, the StopIteration exception has None for its value (normal functions with no return statement also return None).

It isn’t something you’ll probably have much cause to use directly, but there are ways to leverage it if you want to. That’s an advanced topic I’ll get to next time.

§

Before we continue, I’d like to go back to the stepper generator from the last post. There’s another topic I introduced but didn’t explore. Here’s the code again:

def stepper (start=0.0, step=1.0):
    '''Generate numbers forever.'''
    curr = float(start)
    incr = float(step)
    while True:
        message = yield curr
        if message is not None:
            # Received value is new step value...
            incr = float(message)
            continue
        # Next increment...
        curr += incr
#

This generator catches any return value from the yield expression. If the value is not None, it’s assumed to be a float (or something that duck types as a float), and the value of that float is the new step value. This allows the client to change the step value during the run of numbers. It could even reverse the direction of the count.

Here’s an example of client code using the send method:

# Generate a series of increasing steps...
delta = 0.015625
increment = stepper(0.0, delta)
for ix in range(100):
    n = next(increment)
    print('%4d: %9.4f' % (ix+1,n))
    # Every 10 steps...
    if (0 < ix) and (0==(ix % 10)):
        # Double the increment...
        delta *= 2
        print('===== New delta: %.5f' % delta)
        # Send the new value to stepper...
        increment.send(delta)
print()
#

Each time the index variable, ix, is a multiple of ten, it doubles the increment value and sends it to the generator. The sequence starts slowly and builds quickly. By the time it hits 90, the step value is 8.0. The 100th number returned is 151.8438. Not bad for an initial step value of 15 one-thousandths.

It’s possible to get as elaborate with generator.send(value) as needed, but it should probably be limited to something simple (for all sorts of reasons). If you need an object that generates a list of values, and it has a complicated interface, it’s probably best to use a class. There’s a lot more flexibility that way.

But a number generator that can receive simple messages that alter its behavior, as for instance in the stepper, can be useful in some situations. I’ll leave some for next time (along with leveraging generator return values).

§ §

Python also has yield from, which acts a lot like yield. Let’s go back to some very simple examples:

# Two very simple examples of using yield from...
def gen0a ():
    print('  start')
    yield from [21, 42, 63, 84]
    print('  exit')

def gen0b (m, n):
    print('  start')
    yield from enumerate(range(m, n+1))
    print('  exit')

# Use a for-loop...
for n in gen0a():
    print(n)
print()

# Generate a list...
pairs = list(gen0b(10,20))
print(pairs)
print()
#

These are instrumented so we can see what’s going on (for all the good it’ll do us). These simple examples won’t give us anything very interesting, but they’ll get us started understanding yield from.

When we run the code fragment, it prints:

  start
21
42
63
84
  exit

  start
  exit
[(0, 10), (1, 11), (2, 12), (3, 13), (4, 14), (5, 15),
 (6, 16), (7, 17), (8, 18), (9, 19), (10, 20)]

From which it’s hard to tell if the generator is getting control back during each value of the iteration (it is). All we can instrument with these is the start and exit of the generator. We’re gonna need a bigger generator.

§ §

Let’s return to the Collatz sequence generator. We’ll use the same one as above, but heavily instrumented so we can see what’s going on. We’ll also add a wrapper function that uses a yield from statement.

def gen_collatz_1 (n):
    '''A Collatz sequence generator function.'''
    steps = 1
    print('    start (%d)' % n)
    while 1 < n:
        print('    yield1 (%d)' % n)
        yield n
        print('    resume1')
        # Calculate next Collatz number...
        n = Collatz(n)
        # Counting our steps as we go...
        steps += 1
    print('    yield2 (%d)' % n)
    yield n
    print('    resume2')
    print('    exit (%d)' % steps)
    return steps

def collatz_set_1 (start=1, end=100):
    '''Generate a list of Collatz sequences.'''
    print('  start (%d,%d)' % (start,end))
    for n in range(start,end+1):
        print('  yield (%d)' % n)
        rv = yield from gen_collatz_1(n)
        print('  resume (%s)' % rv)
    print('  exit')

for n in collatz_set_1(end=2):
    print(n)
print()
#

When run, it prints:

  start (1,2)
  yield (1)
    start (1)
    yield2 (1)
1
    resume2
    exit (1)
  resume (1)
  yield (2)
    start (2)
    yield1 (2)
2
    resume1
    yield2 (1)
1
    resume2
    exit (2)
  resume (2)
  exit

Clearly control returns to collatz_set_1, which passes it to gen_collatz_1, each time the for-loop requests the next number. So, the combination of the two functions acts like a generator. (Calling either function returns a generator object.)

Notice that the step count value returned by the generator is caught as the value returned by the yield from statement (actually an expression in this case).

§ §

In the above fragment, we asked for the Collatz sequences from 1 to 2 (so just 1 and 2), and we got back a list, [1, 2, 1], which combines the two sequences together. We can tell the end of a sequence because it’s always 1. We can make that more obvious with a single addition to the wrapper:

def collatz_set_1 (start=1, end=100):
    '''Generate a list of Collatz sequences.'''
    for n in range(start,end+1):
        print('  yield (%d)' % n)
        rv = yield from gen_collatz_1(n)
        # Return a zero to delimit sequences...
        yield 0
#

(I removed the print statements for clarity.) Line #7 forces a zero between sequences. Now when we ask for the same two lists we get: [1, 0, 2, 1, 0]

Which is nice visually, but still combines all the lists into one. The client needs to spot the final 1 (or delimiting 0), which makes its job in this case a bit harder. A better system would return a list of Collatz sequences (themselves lists). That goes against the grain of a generator, though. The whole point is returning control for each iteration. It’s easy enough to create a generator that returns a list of sequences:

def gen_collatz_sequences (start=1, end=100):
    '''Return Collatz sequences.'''
    for n in range(start,end+1):
        yield list(gen_collatz_1(n))

# Print Collatz sequences from 10 to 20...
for cs in gen_collatz_sequences(start=10, end=20):
    print(cs)
print()
#

But now the control trades back and forth only on each list request. One place this might work out is if the wrapper is for an infinite list of Collatz sequences:

def all_collatz_sequences (start=1):
    '''Return Collatz sequences FOREVER!'''
    n = start
    while True:
        yield list(gen_collatz_2(n))
        n += 1

# Print 100 Collatz sequences starting at 11...
cs = all_collatz_sequences(11)
for ix in range(100):
    print('%d: %s' % (ix,next(cs)))
#

The usual caution about infinite lists would apply, of course. But this still kind of defeats the point of a generator; it’s no better than a function that does the same thing (although these do all serve as examples). Generator functions work best when we want a value back each time through a loop.

The truth is there aren’t many use cases for yield from. Frankly, all the ones I can think of are fairly artificial, but maybe I just haven’t run into the need.

§ §

That’s enough for this time. Next time I’ll get into some slightly more advanced techniques, including more examples of yield from. Until then, stay coding!

[Sample code for all three posts: examples.zip]

Ø