Filter

Just like list comprehensions, filters are yet another way to create a list from a list. Like map and fold, they are an important part of the list processor's, as well as functional programmer's, toolbox.

The purpose of the filter is to just return the values in the list for which the given predicate is true.

Let \(L\) be a subset of \(X\) and \(f : X \mapsto \left \{ 0, 1 \right \} \) be a function, then

\[filter(f,L) = \left \{ x \mid x \in L, f(x) = 1 \right \}. \]

It should be now obvious that the filter is pretty much the same as a list comprehension barring for the fact that the expression on the left is just a variable and nothing else.

Hence [x | x<- L, f(x)] is pretty much the same as filter f L. Or in python, [x for x in L if f(x)] and filter(f,L) are equivalent.

Filter all the prime numbers from the following list:

1 2 3 4 5

numbers_to_eval = [345748742, 352288653, 985077200, 357507035, 520291774, 729107087, 545059368, 647346013, 474128848, 430782065, 1017154128, 613900692, 335923302, 446776157, 861310614, 555315083, 705352600, 273035494, 457146240, 581163343]

---

Python

We'll have to build a function that tells primes and composites apart, first.

1 2 3 4 5 6

def isPrime(n): for i in range(2, n): # from 2 to n-1 if n%i == 0: # if n divided by i leaves remainder 0 return False else: return True

Now, we just feed the list and the function to filter:

1	filter(isPrime, numbers_to_eval)

---

Haskell

This is going to be fun. We are going to implement trial division using map and filter itself.

1 2 3 4 5 6

noDivsBy factors n = foldr (\f r-> f*f>n || ((rem n f /= 0) && r)) True factors -- primeNums = filter (noDivsBy [2..]) [2..] primeNums = 2 : 3 : filter (noDivsBy $ tail primeNums) [5,7..] isPrime n = n > 1 && noDivsBy primeNums n

Once we are done, we can use filter:

1	filter(isPrime, numbers_to_eval)

---

Mathematica

Things are pretty straight forward in Mathematica:

1	Select[numbers_to_eval, PrimeQ]

That should explain filter. Let us look at a different example.

For all starting numbers between 1 and 100, how many hailstone chains have a length greater than 15?

---

The first thing we need is a way to create the chains given a seed:

1 2 3 4 5

chain :: (Integral a) => a -> [a] chain 1 = [1] chain n | even n = n:chain (n `div` 2) | odd n = n:chain (n*3 + 1)

Here are the sequences for which we'd get a sequence of length larger than 15:

1	filter isLong (map chain [1..100]) where isLong xs = length xs > 15

We will discuss two main variants of filter: dropWhile and partition. We'll be defining them using the concept of filter we developed throughout the article.

dropWhile

dropWhile is just the opposite of filter. It throws away everything that matches the predicate.

1	dropWhile f L = filter not.f L

partition

partition splits the list into two parts: a part that matches the predicate and a part that does not.

1	partition p xs == (filter p xs, filter (not . p) xs)