How to write a Rust function that takes an iterator?

Question

I'd like to write a function that accepts an iterator and returns the results of some operations on it. Specifically, I'm trying to iterate over the values of a HashMap:

use std::collections::HashMap;

fn find_min<'a>(vals: Iterator<Item=&'a u32>) -> Option<&'a u32> {
    vals.min()
}

fn main() {
    let mut map = HashMap::new();
    map.insert("zero", 0u32);
    map.insert("one", 1u32);
    println!("Min value {:?}", find_min(map.values()));
}

But alas:

error: the `min` method cannot be invoked on a trait object
 --> src/main.rs:4:10
  |
4 |     vals.min()
  |          ^^^

error[E0277]: the trait bound `std::iter::Iterator<Item=&'a u32> + 'static: std::marker::Sized` is not satisfied
 --> src/main.rs:3:17
  |
3 | fn find_min<'a>(vals: Iterator<Item = &'a u32>) -> Option<&'a u32> {
  |                 ^^^^ `std::iter::Iterator<Item=&'a u32> + 'static` does not have a constant size known at compile-time
  |
  = help: the trait `std::marker::Sized` is not implemented for `std::iter::Iterator<Item=&'a u32> + 'static`
  = note: all local variables must have a statically known size

error[E0308]: mismatched types
  --> src/main.rs:11:41
   |
11 |     println!("Min value {:?}", find_min(map.values()));
   |                                         ^^^^^^^^^^^^ expected trait std::iter::Iterator, found struct `std::collections::hash_map::Values`
   |
   = note: expected type `std::iter::Iterator<Item=&u32> + 'static`
              found type `std::collections::hash_map::Values<'_, &str, u32>`

I get the same error if I try to pass by reference; if I use a Box, I get lifetime errors.

Solution 1

You want to use generics here:

fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
    I: Iterator<Item = &'a u32>,
{
    vals.min()
}

Traits can be used in two ways: as bounds on type parameters and as trait objects. The book The Rust Programming Language has a chapter on traits and a chapter on trait objects that explain these two use cases.

Additionally, you often want to take something that implements IntoIterator as this can make the code calling your function nicer:

fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
    I: IntoIterator<Item = &'a u32>,
{
    vals.into_iter().min()
}

Solution 2

Since Rust 1.26 impl Trait are available. A less verbose version.

use std::collections::HashMap;

fn find_min<'a>(vals: impl Iterator<Item = &'a u32>) -> Option<&'a u32> {
    vals.min()
}

fn main() {
    let mut map = HashMap::new();
    map.insert("zero", 0u32);
    map.insert("one", 1u32);
    println!("Min value {:?}", find_min(map.values()));
}

playground

Solution 3

This behaviour is a little unintuitive from those with a Python background rather than, say, a C++ background, so let me clarify a little.

In Rust, values are conceptually stored inside the name that binds them. Thus, if you write

let mut x = Foo { t: 10 };
let mut y = x;
x.t = 999;

y.t will still be 10.

So when you write

let x: Iterator<Item=&'a u32>;

(or the same in the function parameter list), Rust needs to allocate enough space for any value of type Iterator<Item=&'a u32>. Even if this was possible, it wouldn't be efficient.

So what Rust does instead is offer you the option to

• Put the value on the heap, eg. with Box, which gives Python-style semantics. Then you can take generically with &mut Iterator<Item=&'a u32>.

• Specialize each function invocation for each possible type to satisfy the bound. This is more flexible, since a trait reference is a possible specialization, and gives the compiler more opportunities for specialization, but means you can't have dynamic dispatch (where the type can vary dependent on runtime parameters).

Comments

[Doctor J]

I was so close. To expound, the difference with generics is static dispatch, i.e., Rust is creating a version of this function for each concrete type I call it with?

[Francis Gagné]

Correct. This way, the compiler knows the type of the iterator, therefore it knows its size, so it knows how much memory it needs to reserve. Also, a type like Iterator<Item=&'a u32> cannot be used alone; it can only be used behind a pointer.

[Vladimir Matveev]

Note that while requiring I to implement Iterator is absolutely correct if you want to pass arbitrary iterators into the function, the more generic way would be to require I to implement IntoIterator. It allows you to pass iterators too but you will be also able to pass anything which can be converted into an iterator, without the need to call conversion methods explicitly. I'd say this is the idiomatic approach to consume iterators and iterables.

[burfl]

@VladimirMatveev, can you elaborate a bit on that, please? I'm trying to get something like the following working with your advice... gist.github.com/anonymous/0c1db25a9b38a2fc95f44bec34ebd46a

[Francis Gagné]

@burfl: Your function should be returning u64, not T.

[burfl]

@FrancisGagné, holy cow, that was simple! Thank you so much!

[Boiethios]

With foo: impl Type this is much more easy now

[user5359531]

" require I to implement IntoIterator"; but what if you want to pass something that does not use into_iter to return an iterator? For example, if I wanted to iterate over either vector elements (my_vec.iter()) OR a file handle (fs::File::open("foo.txt").unwrap().lines()), etc.. Does IntoIterator still apply here?

[Francis Gagné]

@user5359531 Yes, all iterators also implement IntoIterator thanks to a blanket impl (impl<I> IntoIterator for I where I: Iterator; into_iter just returns self).

[K. Norbert]

The example here wouldn't compile, the let mut y = x assignment moves x, so line 3 cannot use x anymore. (unless you specify that Foo is Copy, but that gives a pretty good hint already that it won't behave like you would expect in scripting languages)

[K. Norbert]

Regardless of the semantics of "does it change the code, or does it change what you are allowed to do", the example code above is still invalid, and does not compile.

[K. Norbert]

I would assume it's non-copy because that's the default for structs, and there is no mention of it being Copy in your answer.

[K. Norbert]

The issue is that the code you are using to reason with is invalid, without some arbitrary assumptions that beginners might not have.

[TimY]

Is there a reason why this wouldn't be better than the alternatives, or is it just more recent?

[Fuji]

In Rust 1.26 impl Trait were added to the language. This a less verbose way to implement the same code

[ChrisPhoenix]

Agreed - the code here is broken and will teach people incorrect things about Rust. Please fix!

[Veedrac]

@ChrisPhoenix The code is not broken and I maintain that emphasizing the difference between Copy and move is extremely misleading, and largely illusory, in this context.

[Veedrac]

Teaching, or even implying too strongly, that Copy changes the behaviour of the code is factually incorrect and based around an invalid model of Rust that I imagine stems from C++. The more you play into that myth, the more it spreads.

[ChrisPhoenix]

I copy-and-pasted your code into a .rs file adding "struct Foo { t: i32, }". It did not compile. y does not need to be mutable, and "x.t = 999;" gets a " | ^^^^^^^^^ value partially assigned here after move" because Foo "does not implement the Copy trait." Why do you say code that doesn't compile is not broken? When I add "#[derive(Clone, Copy)]" to Foo (and remove the "mut" on y) it compiles and indeed y.t is 10.

[ChrisPhoenix]

For what it's worth, I loathe C++ and have never really learned it; I've been an embedded software engineer for decades and I know the difference between a data-copy and a reference. So does the Rust compiler. It's not that Copy "changes the behavior of the code" - it's that Copy allows "let y = x; x.t=999;" to compile at all.

[Veedrac]

@ChrisPhoenix That's like saying “I copy-and-pasted your code into a .rs file adding "struct Foo {}". It did not compile. Why do you say code that doesn't compile is not broken?” I never specified that Foo shouldn't be marked Copy, I just don't want to draw attention to it because it's independent of the behaviour I'm explaining, just like I didn't draw attention to the member t or its type. You can't really understand why certain things need to be marked Copy until you understand what assignment does.