Python 2 vs Python 3 - Difference in behavior of filter

Question

Could someone please help me understand why the following code that implements the "sieve of Eratosthenes" behaves differently across Python 2 and Python 3.

l = range(2, 20)
for i in range(2, 6):
    l = filter(lambda x: x == i or x % i != 0, l)
print(tuple(l))

With Python 2.7:

> python filter.py
(2, 3, 5, 7, 11, 13, 17, 19)

with Python 3.6:

> python filter.py
(2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19)

I understand that Python3's filter returns a filter object but can't explain the final result. (The code is from this lambdas tutorial 1).

Answer 1

There are two parts that play a role here:

• in python-3.x, filter works as a generator: the filtering is done lazy; and
• the i in the lambda x : ... is updated as well as the i in the for loop makes progression.

So at the end what you have constructed is something like:

l = filter(lambda x: x == 5 or x % 5 != 0,
        filter(lambda x: x == 5 or x % 5 != 0,
            filter(lambda x: x == 5 or x % 5 != 0,
                filter(lambda x: x == 5 or x % 5 != 0,l)
            )
        )
    )

Note that all filtering is done as if i was 5 all the time. So now you call tuple(..), the actual filtering will be done, and as you can see only multiples of five that are not five themeselves are filtered out.

An easy fix is to use list in the loop such that the filtering is done actively:

l = range(2, 20)
for i in range(2, 6):
    l = list(filter(lambda x: x == i or x % i != 0, l))
print(tuple(l))

Running this in python returns:

>>> l = range(2, 20)
>>> for i in range(2, 6):
...     l = list(filter(lambda x: x == i or x % i != 0, l))
... 
>>> print(l)
[2, 3, 5, 7, 11, 13, 17, 19]

Mind that although python-2.7 and python-3.x look quite the same these are actually "different" languages that are incompatible with each other: running code written in one will not always work in the other and vice versa.

Another note (credits to @ShadowRanger) is that one actually can bind i in your lambda. You do this by creating a "higher order lambda". Instead of writing:

lambda x : x == i or x % i != 0

you write:

(lambda j : (lambda x : x == j or x % j != 0))(i)

What happens is you define a function that takes as input a j that actually takes the value of i. By calling it immediately, j binds to the value of i.

Answer 2

In Python-3 filter returns a generator (in Python-2 it returns a list), so it's evaluated when you consume it. But that wouldn't be a problem by itself, the problem is that your i changes. At the time you consume the filter your i = 5 and all your filter just check for that.

I include some print-statements so you can more easily follow what is happening:

l = range(2, 20)
for i in range(2, 6):
    l = filter(lambda x: print(x, i) or (x == i or x % i != 0), l)
list(l)

2 5
2 5
2 5
2 5
3 5
3 5
3 5
3 5
4 5
4 5
4 5
4 5
5 5
5 5
5 5
5 5
6 5
6 5
6 5
6 5
7 5
7 5
7 5
7 5
8 5
8 5
8 5
8 5
9 5
9 5
9 5
9 5
10 5
11 5
11 5
11 5
11 5
12 5
12 5
12 5
12 5
13 5
13 5
13 5
13 5
14 5
14 5
14 5
14 5
15 5
16 5
16 5
16 5
16 5
17 5
17 5
17 5
17 5
18 5
18 5
18 5
18 5
19 5
19 5
19 5
19 5

[2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19]

That probably wasn't your intention. You could bind i to your lambda:

l = range(2, 20)
for i in range(2, 6):
    l = filter((lambda j: lambda x: print(x, j) or (x == j or x % j != 0))(i), l)
    # or
    # l = filter(lambda x, i=i: print(x, i) or (x == i or x % i != 0), l)
list(l)
2 2
2 3
2 4
2 5
3 2
3 3
3 4
3 5
4 2
5 2
5 3
5 4
5 5
6 2
7 2
7 3
7 4
7 5
8 2
9 2
9 3
10 2
11 2
11 3
11 4
11 5
12 2
13 2
13 3
13 4
13 5
14 2
15 2
15 3
16 2
17 2
17 3
17 4
17 5
18 2
19 2
19 3
19 4
19 5

[2, 3, 5, 7, 11, 13, 17, 19]

or cast your filter-result immediatly to a tuple:

l = range(2, 20)
for i in range(2, 6):
    l = tuple(filter(lambda x: x == i or x % i != 0, l))
print(l)
# (2, 3, 5, 7, 11, 13, 17, 19)