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, itertools.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 itertools.compress 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 Nothings and unwrapping all of the Justs. 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.