appending generators to a stack in loop, generators point to final loop variable

Question

I'm doing some graph traversal. At each point I save a generator of the other possible options that could have been explored. Later, I explore a few of those generators but it doesn't work.

Here is a simplified example where you can see the "node" variable is set to 3 in all the generators. (so the generators point back to the "node" variable, but the "node" variable changes before the generator is consumed.

In my particular case I can store some pointers and add logic of what to do with those pointers to re create the generator - but this is an ugly solution.

Is there a simple way to do it?

node_size = {1:1, 2:2, 3:1, 4:3}
iters = []
for node in range(1,4):
    it = (1 + node_size[node]+j for j in xrange(3))
    #it = iter(list(it)) #remove comment to get correct result but very slow.
    iters.append(it)

for iter_ in iters:
    print list(iter_)

"""
Correct Output
[2, 3, 4]
[3, 4, 5]
[2, 3, 4]
"""

"""
Actual Output:
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
"""

Answer 1

Your generator expression references the global variable node. Since this is a free variable in the genexp, it closes over the name, not the value. Every time you grab an item from the generator, the expression 1 + node_size[node]+j is evaluated with the current value of node. That is, the value of node is read each time the generator is advanced, not once and for all at the time it is created. By the time you start grabbing items from the generator, node is 3, so all items in the generator reflect that value.

To get what you want, you need to bind node in the generator function itself. One quick way to do this is to force node into the loop portion of the genexp:

it = (1 + node_size[node]+j for node in [node] for j in xrange(3))

Since the loop part is evaluated just once when the genexp is created, this fixes a single value of node in the genexp scope.

If that way is too ugly-looking for you, you will have to write an explicit generator function instead of using a genexp:

def gen(nodeVal):
    for j in xrange(3):
        yield 1 + node_size[nodeVal]+j
for node in range(1, 4):
    iters.append(gen(node))

Here the generator closes over the name nodeVal, but since each generator is created by a separate function call, each gets its own value of nodeVal and all is well.

Answer 2

How about making generator functions that close over the node size value?

node_size = {1:1, 2:2, 3:1, 4:3}

iters = []
for node in xrange(1, 4):
    def it(n=node_size[node]):
        for j in xrange(1, 4):
            yield n + j
    itr = it()
    iters.append(itr)

for iter_ in iters:
    print list(iter_)

This prints the correct result for me.

EDIT: @BrenBarn posted an answer that led me directly to this answer:

node_size = {1:1, 2:2, 3:1, 4:3}

iters = []
for node in range(1, 4):
    n = node_size[node]
    itr = xrange(n+1, n+4)
    iters.append(itr)

for iter_ in iters:
    print list(iter_)

When you call xrange() it evaluates its arguments and then it gives you back an iterator that yields up the numbers.

I don't think there is any more efficient way to do this in Python!

In this case, we were able to avoid all math and get xrange() to yield up exactly the desired numbers. If you really needed to evaluate an expression you can still do the generator expression way:

itr = (1+j for j in xrange(n, n+3))