Weird behavior of Python iterator

Question

I was playing around with Python generators and the itertools module and tried making an infinite version of the Sieve of Eratosthenes. Here is my code:

from itertools import count, ifilter, islice

def sieve_broken():
    candidates = count(start=2)
    while True:
        prime = next(candidates)
        yield prime
        candidates = ifilter(lambda n: n % prime, candidates)

When I test it out, I get this:

>>> print list(islice(sieve_broken(), 10))
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

But if I replace the reassignment of candidates with a function like so:

def sieve_fixed():
    def exclude_multiples(factor, numbers):
        return ifilter(lambda n: n % factor, numbers)

    candidates = count(start=2)
    while True:
        prime = next(candidates)
        yield prime
        candidates = exclude_multiples(prime, candidates)

I get:

>>> print list(islice(sieve_fixed(), 10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

I can't figure out why the first version doesn't work. As far as I can tell, the two versions should be equivalent. Does anyone know why they're not the same?

score 4 · Accepted Answer · answered Nov 06 '13 at 01:41

4

You've fallen prey to a very common pitfall when using closures in Python: closures carry their scope, and you keep replacing the value in the same scope.

candidates = ifilter(lambda n, prime=prime: n % prime, candidates)

answered Nov 06 '13 at 01:41

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

I'm not sure I understand... where am I defining a function that returns a function? – user1475412 Nov 06 '13 at 02:32
@user1475412: You aren't returning it, but there's one as the first argument to `ifilter()` regardless. – Ignacio Vazquez-Abrams Nov 06 '13 at 02:34

Weird behavior of Python iterator

1 Answers1

Linked

Related