filter ​

The built-in filter() function in Python is used to filter sequences.

Similar to map(), the filter() function also takes a function and a sequence as arguments. However, unlike map(), filter() applies the given function to each element in the sequence, and keeps or discards the element based on whether the function returns True or False.

For example, to remove even numbers from a list and keep only odd numbers, you can write:

def is_odd(n):
    return n % 2 == 1

list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))
# Result: [1, 5, 9, 15]

To remove empty strings from a sequence, you can write:

def not_empty(s):
    return s and s.strip()

list(filter(not_empty, ['A', '', 'B', None, 'C', '  ']))
# Result: ['A', 'B', 'C']

As seen, the key to using filter(), a higher-order function, is correctly implementing a "filtering" function.

Note that the filter() function returns an Iterator, which is a lazy sequence. Therefore, to force filter() to compute the result, you need to use the list() function to obtain all results and return a list.

Using filter to Find Prime Numbers ​

One method for calculating prime numbers is the Sieve of Eratosthenes, which is quite simple to understand:

1. Start by listing all natural numbers from 2 onwards, constructing a sequence:

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

2. Take the first number in the sequence, 2, which is a prime number, and use it to filter out all multiples of 2:

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

3. Take the next number, 3, which is also a prime number, and use it to filter out all multiples of 3:

   5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

4. Continue this process by taking the first number, 5, and using it to filter out all multiples of 5:

   7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

By continuing this filtering process, all prime numbers can be obtained.

To implement this algorithm in Python, you can first construct an odd number sequence starting from 3:

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

Note that this is a generator and an infinite sequence.

Next, define a filtering function:

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

Finally, define a generator that continually returns the next prime number:

def primes():
    yield 2
    it = _odd_iter() # Initial sequence
    while True:
        n = next(it) # Return the first number in the sequence
        yield n
        it = filter(_not_divisible(n), it) # Construct a new sequence

This generator first returns the prime number 2, then uses filter() to continually produce a new filtered sequence.

Since primes() is also an infinite sequence, a condition must be set to exit the loop when calling it:

# Print prime numbers below 1000:
for n in primes():
    if n < 100:
        print(n)
    else:
        break

Note that an Iterator is a lazily computed sequence, allowing Python to express sequences such as "all natural numbers" or "all prime numbers" very concisely.

Exercise ​

A palindrome is a number that reads the same from left to right as it does from right to left, such as 12321 or 909. Use filter() to filter out palindromes:

def is_palindrome(n):
    pass

# Test:
output = filter(is_palindrome, range(1, 1000))
print('1~1000:', list(output))
if list(filter(is_palindrome, range(1, 200))) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191]:
    print('Test passed!')
else:
    print('Test failed!')

Summary ​

The purpose of filter() is to filter out elements from a sequence that meet specific conditions. Because filter() uses lazy evaluation, the filtering occurs only when retrieving the results, returning each filtered element one at a time.