# 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.

#### Contents

## Definition

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.

## Examples

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`

## Variants

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)`