About filter_map

Am I correct when I say that the filter_map algorithm does actually maps first and then filters?

Well, it does both things at the same time. Its input function either yields a Some or a None, and it simply ignores the Nones. That doesn't seem to me like it's doing either the mapping or the filtering "first".

But it cannot do two things at the same time, I mean inside of the closure. It has to either filter first or map first. Isn't that so?

If you mean the mapping/predicate function that is the parameter of filter_map: well, it does what it does. filter_map has no control over what it does or how it does it. That function will just return a value, which is either Some or None. That is what decides what will be returned from the final iterator, and whether it will be returned at all. You can implement it in many different ways, and I don't think it's meaningful to ask whether it filters "first" or maps "first". Filtering and mapping are both things that are applied to a series of elements; you could say they were filtered first or mapped first if you used .filter().map() or .map().filter(). But the point of filter_map() is exactly that you do both things to a single element.


Anyway, what's the point of this question? What problem are you trying to solve?

1 Like

The point of this question is that I'm trying to learn iterators and how they behave. And this one I have to admit confused me a little.
I can perhaps explain bit better by providing an example:

 let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
 v.iter()
 .filter_map(|&x| if x % 2 == 0 { Some(x) } else { None });

So, in this example we first apply mapping (x%2 == 0) and then we are filtering (returning either Some or None).
And I believe that schema is always used in filter_map, that is, first mapping of some kind is done and then filtering, that is returing already mapped item as Some or None.

Yes, but the order of those two things done to a single element is map then filter, not filter then map.

The thing is, filter_map() doesn't care what order those operations are performed in. But even in a trivial example like this, you could do (or might need to do) things the other way around:

v.iter().filter_map(|&x| if x <= 5 { Some(x * 2) } else { None })

By your logic, here you are filtering first and only then mapping.

However, I would actually argue that this distinction is useless, because it's not observable from the point of the iterator or the result.

1 Like

Yes, fair point and valid observation. I'm not trying to argue here anything, I'm just trying to understand those things better, and I am still convinced that it is more natural to first map then filter, but I have really very, very limited exp in this area and I can be just plain wrong.

I don't think there's anything profound that needs further understanding here. You can write your mapping/filtering closure in any way you want, as long as it produces the correct results. You can even write it in a way that computation of the mapped value and filtering is interleaved, so the order can't be defined. But that's not a problem, again, because it simply doesn't matter.

5 Likes

There is a sense in which what filter_map() itself does is “mapping then filtering”, because it calls the function for every item and then filters out some of them. But, if we implement filter_map() in terms of filter() and map(), we need a second map() to be able unwrap the Options produced:

use std::fmt::Debug;

fn main() {
    // These are equivalent
    p((0..10i32).filter_map(some_operation));
    p((0..10i32)
        .map(some_operation)
        .filter(Option::is_some)
        .map(Option::unwrap));
}

fn some_operation(value: i32) -> Option<i32> {
    if value.rem_euclid(2) == 0 {
        Some(value * 10)
    } else {
        None
    }
}

fn p<I: Debug>(it: impl Iterator<Item = I>) {
    println!("{:?}", it.collect::<Vec<I>>());
}

But from the perspective of the function you're writing and passing to filter and map, it is allowed to perform filtering-like (return None) and mapping-like (compute some derived value) in any arbitrary interleaving. That's in a sense the point of filter_map() — it allows you to write things that would be awkward to do as a sequence of filters and maps, including borrowed data.

Here's an example I just made up. If you tried to rewrite it as a combination of .filter() and .map(), then either you'd be doing a few steps of packing up the data into temporary tuples, or you'd be doing the .filter(Option::is_some).map(Option::unwrap) I mentioned above — and it's generally considered bad style to use is_some() followed by unwrap() if it's possible to instead use a matching operation (thus avoiding an unreachable panic case) — and in this case, filter_map() is how you do that.

fn main() {
    // Prints [("a", "foo"), ("b", "1")]
    p(["a=foo", "b", "c=c=c", "=bar"].into_iter().filter_map(parse_equals));
}

fn parse_equals(input: &str) -> Option<(String, String)> {
    let mut split = input.split('=');
    let key = split.next()?;
    if key == "" {
        return None;
    }
    let value = match split.next() {
        Some(value) => value,
        None => "1",
    };
    if split.next().is_some() {
        // Too many elements
        return None;
    }
    Some((key.to_string(), value.to_string()))
}
5 Likes

It might be easier to understand by looking at how filter_map() is (roughly) implemented:

struct FilterMap<I, F, T> {
    iter: I,
    filter_map: F,
    _result_type: PhantomData<T>,
}

impl<I, F, T> Iterator for FilterMap<I, F, T>
where
    I: Iterator,
    F: FnMut(I::Item) -> Option<T>,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        loop {
            let item = self.iter.next()?;
            if let Some(value) = (self.filter_map)(item) {
                return Some(value);
            }
        }

        None
    }
}

(playground)

On the if let Some(value) = (self.filter_map)(item) line you can see that all our FilterMap iterator does is call the closure on the next item and yield the value if the closure returns Some.

It is up to whoever writes the closure to decide whether to filter or map first. In my playground snippet, I've written the function so it first filters out odd numbers and then maps even numbers to its square.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.