Writing a function to take iterables of reference and value type

Question

I'd like to have a function that takes an iterable and returns its smallest and largest elements. This is part of an exercise in learning Rust, but I'm struggling in being able to handle reference types and value types at the same time.

This is what I have:

fn min_max<'a, I, T>(mut iter: I) -> Option<(&'a T, &'a T)>
where
    I: Iterator<Item = &'a T>,
    T: PartialOrd,
{
    let mut min = match iter.next() {
        Some(x) => x,
        // The collection is empty
        None => return None,
    };
    let mut max = min;

    for el in iter {
        if el < min {
            min = el;
        }
        if el >= max {
            max = el;
        }
    }

    Some((min, max))
}

Then, I give this an iterator over some integers.

let nums: [u32; 6] = [4, 3, 9, 10, 4, 3];
if let Some((min, max)) = min_max(nums.iter()) {
    println!("{} {}", min, max);
}

This works, and prints 3 10. But then I want to do some operations on the numbers before I compute the minimum and maximum, like a map and/or a filter.

let doubled = nums.iter().map(|x| 2 * x);
if let Some((min, max)) = min_max(doubled) {
    println!("{} {}", min, max);
}

This gives a compiler error:

error[E0271]: type mismatch resolving `<[closure@src/main.rs:31:35: 31:44] as std::ops::FnOnce<(&u32,)>>::Output == &_`
  --> src/main.rs:32:31
   |
32 |     if let Some((min, max)) = min_max(doubled) {
   |                               ^^^^^^^ expected u32, found reference
   |
   = note: expected type `u32`
              found type `&_`
   = note: required because of the requirements on the impl of `std::iter::Iterator` for `std::iter::Map<std::slice::Iter<'_, u32>, [closure@src/main.rs:31:35: 31:44]>`
   = note: required by `min_max`

This confused me, because if nums.iter() works as an argument, why shouldn't nums.iter().map(...)?

I understand the error message in principle: my array is of u32, not &u32, whereas my function requires Iterator::Item to be of type &'a T. But then I don't get why it errors only on the second sample (using .iter().map()) and not on the first (just .iter()).

I've made a playground with this example and a commented out example where I construct an iterable of integers from a string. This fails in exactly the same way as the second example above (and is closer to my actual use case).

let s = "4 3 9 10 4 3";
let parsed = s.split(" ").map(|x| x.parse::<u32>().unwrap());

if let Some((min, max)) = min_max(parsed) {
    println!("{} {}", min, max);
}

Answer 1

I'd like to have a function that takes an iterable and returns its smallest and largest elements.

Use Itertools::minmax.

handle reference types and value types at the same time.

You don't need to — references to numbers can also be compared:

fn foo(a: &i32, b: &i32) -> bool {
    a < b
}

In your case, remember that a value and a reference to that value are different types. That means you can accept an iterator of any type so long as the yielded values are comparable, and this includes both references and values, as requested:

fn min_max<I>(mut iter: I) -> Option<(I::Item, I::Item)>
where
    I: Iterator,
    I::Item: Clone + PartialOrd,
{
    let mut min = match iter.next() {
        Some(x) => x,
        // The collection is empty
        None => return None,
    };
    let mut max = min.clone();

    for el in iter {
        if el < min {
            min = el;
        } else if el >= max {
            max = el;
        }
    }

    Some((min, max))
}

I chose to add the Clone bound although to be more true to your original I could have used the Copy bound. Itertools returns an enum to avoid placing any restrictions on being able to duplicate the value.

This works with all three of your examples:

fn main() {
    let nums: [u32; 6] = [4, 3, 9, 10, 4, 3];
    if let Some((min, max)) = min_max(nums.iter()) {
        println!("{} {}", min, max);
    }

    let doubled = nums.iter().map(|x| 2 * x);
    if let Some((min, max)) = min_max(doubled) {
        println!("{} {}", min, max);
    }

    let s = "4 3 9 10 4 3";
    let parsed = s.split(" ").map(|x| x.parse::<u32>().unwrap());

    if let Some((min, max)) = min_max(parsed) {
        println!("{} {}", min, max);
    }
}

3 10
6 20
3 10

my array is of u32, not &u32, whereas my function requires Iterator::Item to be of type &'a T. But then I don't get why it errors only on the second sample (using .iter().map()) and not on the first (just .iter()).

Because iterating over an array returns references. By using map, you are changing the type of the iterator's item from &i32 to i32. You could have also chosen to adapt the first call to return values.

Answer 2

You have a type mismatch problem because the .iter() call produces a "slice" iterator (Iterator with Item = &T), but the .map(|x| 2 * x) is a iterator adaptor, the call of which produces a new "value" iterator (Iterator with Item = T). These values must necessarily be stored in memory before we can get them "slice", because we can only get a reference to the value that is already stored somewhere in the memory. Therefore, we need to collect the result of the map function before we can get an iterator with references to the values it returns:

let doubled: Vec<_> = nums.iter().map(|x| 2 * x).collect();

if let Some((min, max)) = min_max(doubled.iter()) {
    println!("{} {}", min, max);
}

For more details, see chapter 13.2 Iterators of The Rust Programming Language book.