Iterator API filter and map

Hi community!

I have experience in working with functional style API in other languages. As I learn about Rust's iterator API, I found the following a bit confusing.
Iterator.map() takes FnMut<Self::Item> -> B, but Iterator.fitler() takes FnMut<&Self::Item> -> bool .

So is there any reason why map() would not work with a reference? Similarly, what are the reasons for making filter() works with a reference?

// excerpt from std documentation for filter()
let a = [0, 1, 2];

let mut iter = a.iter().filter(|x| **x > 1); // need two *s!

Because of the ownership system.

If filter took ownership of a value, that value would be dropped at the end of the filter function.
Similarly, map takes ownership of the value to be able to map to another type or mutate the value.

1 Like

As I understood it, the decision of consumption or not is made by calling iter() or into_iter(). So why we need to further distinguish in the iterator adaptors?

#![allow(unused)]
fn main() {
let a: Vec<i32> = vec!(1, 2, 3, 4);

let b: Vec<i32> = a.into_iter().map(|x| x * 2).collect();

println!("{:?}", b);
// println!("{:?}", a); won't compile, as `a` was moved

}

Let's try to implement an ownership-taking filter.

impl<I, Item, P> Iterator for FilterOwned<I, P>
where
    I: Iterator<Item=Item>,
    P: FnMut(Item) -> bool,
{
    type Item = Item;
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let item = self.iter.next()?;
            if (self.predicate)(item) {
                return Some(item);
            }
        }
    }
}

The code is a little less terse than it could be so that it's easier to follow. To implement the filter iterator, we get the next item of the underlying iterator (or return None if there isn't one). Then we run the item through the filter, and return the item if it passes the filter. (If it doesn't pass the filter, we loop and try again.)

The code does not compile:


25 |             let item = self.iter.next()?;
   |                 ---- move occurs because `item` has type `Item`, which does not implement the `Copy` trait
26 |             if (self.predicate)(item) {
   |                                 ---- value moved here
27 |                 return Some(item);
   |                             ^^^^ value used here after move

And this is why the filter closure takes references and not ownership. If it took ownership, it would need to return the item, not just a bool. Otherwise the item cannot be returned to the user of the iterator.

What if you need ownership in your filter closure though? Then you're probably looking for filter_map. The closure takes ownership, and instead of returning true or false, it returns Some(item) or None.

5 Likes

Thanks! It becomes clear when you showed the implementation where it needs to work with all possible Iterator, regardless of their actual Item type.

My confusion was mainly coming from first time using the API and the encounter of double reference.

1 Like

Yes, that's a good point -- it's not just ownership, it's ownership in combination with the need to be very generic. (The filter_owned example compiles if you add the restriction Item: Copy, for example.)

exactly!

Another family of Iterator<T> that can implement FilterOwned are those whose T is a reference (I actually don't know how to express T is a reference to another type in the trait bound). So a non-borrow Iterator won't support filtering. I'm not sure if this would be less ergonomic to work with.

Shared references are Copy. Clone would be more general. (But filter_map is even more general.)

Mutable references have much the same restrictions as owned values.

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.