python filter doesn't work

Question

I have an algorithm that can generate a prime list as a generator:

def _odd_iter():
    n=3
    while True:
        yield n
        n=n+2

def _not_divisible(n):
    return lambda x: x % n > 0

def primes():
    yield 2
    L=_odd_iter()
    while True:
        n=next(L)
        yield n
        L=filter(_not_divisible(n), L)

x=1
for t in primes():
    print(t)
    x=x+1
    if x==10:
        break

But if I put the lambda function into the filter function directly, like below:

def primes():
    yield 2
    L=_odd_iter()
    while True:
        n=next(L)
        yield n
        L=filter(lambda x: x%n>0, L)

I can get only an odd list, not a prime list. It seems the filter function doesn't work.

What can I do?

Answer 1

Here's a simpler program which illustrates the same problem.

adders = []
for i in range(4):
    adders.append(lambda a: i + a)
print(adders[0](3))

While one would expect the output to be 3, the actual output is 6. This is because a closure in python remembers the name and scope of a variable rather than it's value when the lambda was created. Since, i has been modified by the time the lambda is used, the lambda uses the latest value of i.

The same thing happens in your function. Whenever n is modified, all the lambda functions in the various filters also get modified. So, by the time the iterator reaches 9, all the filters are filtering factors of 7, not 5 or 3.

Since, in your first approach you are creating a new scope with each call to _not_divisible, the function works as intended.

If you absolutely must use a lambda directly, you can use a second argument like this:

def primes():
    yield 2
    L=_odd_iter()
    while True:
        n=next(L)
        yield n
        L=filter(lambda x, n=n: x%n>0, L)

Answer 2

The lambda that works is lambda x, n=n: x%n != 0. You apparently need to do this if you want n to be captured at the time the lambda is defined. Otherwise a lambda only looks up the variable name when it gets around to evaluating the lambda. In your case I think that meant locking onto an n value in a later iteration of the while loop.