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:

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

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.

filterfalse

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

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.

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.

Recursively

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

  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.

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.

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

which in our situation here is specialized as

Our compress function then looks like this:

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.

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.