# Filtration

In constrast with `takewhile` which stops the first time it encounters a non-matching value, `filter` continues past non-matching values and produces a list containing all of the values that satisfy the predicate.

## `filter`

Here we use `filter` `filter` in Python to select, from among the natural numbers, only those that are even:

``````>>> it = filter(lambda x: x % 2 == 0, count(1))

>>> list(islice(it, 10))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]``````

Haskell’s `filter` function `filter` in `Data.List` and `Prelude` is the same.

``````λ> xs = filter even [1..]

λ> take 10 xs
[2,4,6,8,10,12,14,16,18,20]``````

We often hear people complain that they can’t remember whether `True` or `False` in the filtering function signifies keep or discard. You might consider using `mapMaybe` `mapMaybe` in `Data.Maybe` instead; it’s a little longer but the meaning of the code may be somewhat more apparent.

``````λ> f x = if (even x) then (Just x) else Nothing

λ> xs = mapMaybe f [1..]

λ> take 10 xs
[2,4,6,8,10,12,14,16,18,20]``````

### `filterfalse`

The opposite of `filter` is `filterfalse`, which selects all values that do not match the predicate.

``````>>> it = filterfalse(lambda x: x % 2 == 0, count(1))

>>> list(islice(it, 10))
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]``````

Haskell doesn’t have a separate “opposite” variant of `filter`, but it is convenient enough to compose the predicate with `not` `not` in `Data.Bool` and `Prelude` to invert it.

``````λ> xs = filter (not . even) [1..]

λ> take 10 xs
[1,3,5,7,9,11,13,15,17,19]``````

## `compress`

Python’s `compress` is sort of mixture of zipping and filtering. It zips a list of values with a list of Booleans specifying whether to keep or discard, and produces a list of only those elements that ended up being zipped next to a keep.

``````>>> it = compress([1, 2, 3, 4], [1, 0, 0, 1])

>>> list(it)
[1, 4]``````

### Recursively

We are not aware of `compress` in any Haskell library, but we can write one without too much trouble.

``````compress :: [Bool] -> [a] -> [a]

compress [] _ = []                                                 -- 1
compress _ [] = []                                                 -- 2
compress (False : selectors) (_ : xs) = compress selectors xs      -- 3
compress (True : selectors) (x : xs) = x : compress selectors xs   -- 4``````
1. If the selectors list is empty, then the output is empty.
2. If the data list is empty, then the output is empty.
3. If the first selector is `False`, then discard the first data item, and proceed with the tails of both lists.
4. If the first selector is `True`, then include the first data item, and proceed with the tails of both lists.
``````λ> compress [True, False, False, True] [1..]
[1,4]``````

This is not the only way we could have written this `compress` function. Next we’ll present three more alternatives that achieve the same result using functions in the standard library, to get some practice thinking about the `Data.List` functions we’ve seen above and to introduce a few new ones. We’ve said that “compressing” is a mixture of zipping and filtering, so each of these functions will be implemented using a zipping function and a filtering function. The gist of them all will be the same, but the details will vary slightly depending on which zipping function and which filtering function we choose.

### With `zip` and `catMaybes`

In this version, we use `zipWith` `zipWith` in `Data.List` and `Prelude` to zip the selectors and elements with a function that returns `Maybe`. Each list position gets mapped to `Just` a value if the selector says yes, or `Nothing` if the selector says no.

``````compress selectors xs = catMaybes (zipWith f selectors xs)
where
f True  x = Just x
f False _ = Nothing``````

`zipWith` returns `[Maybe a]`, and we need to convert that to `[a]`, discarding all of the `Nothing`s and unwrapping all of the `Just`s. This is what the `catMaybes` function `catMaybes` in `Data.Maybe` does.

### With `zip` and `mapMaybe`

If we `zip` `zip` in `Data.List` and `Prelude` the selectors and the values, then the type we have is `[(Bool, a)]`. We can then use `mapMaybe`, an extremely handy function which is like a simultaneous `map` and `filter`. This application of `mapMaybe` serves both to discard the rejected values and to remove the selectors, leaving us with only the accepted `a` values.

The type signature of `mapMaybe` is `mapMaybe` in `Data.Maybe`

``mapMaybe :: (a -> Maybe b) -> [a] -> [b]``

which in our situation here is specialized as

``mapMaybe :: ((Bool, a) -> Maybe a) -> [(Bool, a)] -> [a]``

Our `compress` function then looks like this:

``````compress selectors xs = mapMaybe f (zip selectors xs)
where
f (True,  x) = Just x
f (False, _) = Nothing``````

### With `zip`, `map`, and `filter`

Instead of using `mapMaybe` as we did in the previous version, we could have achieved in the same result in two separate steps: first using `filter` to remove the unwanted tuples, and then using `map` to unwrap the tuples.

``````compress selectors xs = f (zip selectors xs)
where
f = map    (\(_, x) -> x)
. filter (\(s, _) -> s)``````

We have given four different ways to define the same `compress` function. None of these implementations is particularly better or worse than the others; they are all reasonable options.

Join Type Classes for courses and projects to get you started and make you an expert in FP with Haskell.