How does rust collect() create different collections generically

user_654928 0
Viewed 906

According to the documentation, this method https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.collect can create different collections based on the type of the variable its return value is assigned to. I've been researching this for a while now and I can't find the key reason it's able to do this. Is it overloaded generically somehow? How is it able to create different types based on the variable type?

I understand type inference is playing a role here, but I'm more confused about how that works in tandem with the actual underlying implementation of collect()

I'm beginning to learn rust so this concept is new to me. I am reading the rust book and have searched for this, but can't find what I'm looking for.

Thank you in advance!

Example from the link:

// This

let a = [1, 2, 3];

let doubled: Vec<i32> = a.iter()
                         .map(|&x| x * 2)
                         .collect();

assert_eq!(vec![2, 4, 6], doubled);

// Compared to this

use std::collections::VecDeque;

let a = [1, 2, 3];

let doubled: VecDeque<i32> = a.iter().map(|&x| x * 2).collect();

assert_eq!(2, doubled[0]);
assert_eq!(4, doubled[1]);
assert_eq!(6, doubled[2]);
rust
2 Answers

Notice that the generic type parameter of the Iterator::collect method implements the FromIterator trait. This is where all the magic happens -- if you look at the source of Iterator::collect<B>, you'll see that all it does is call FromIterator::from_iter. Since the compiler expects the return value to be of type B, it infers that FromIterator::from_iter refers to the implementation of FromIterator::from_iter on B (as from_iter returns Self).

If you look at implementors of FromIterator, you'll see that many standard collection types (among other types) like Vec and VecDeque implement this trait, and hence can be collected into. To put everything together, when compiling the line of code

let v: Vec<_> = some_iterator.collect()

The compiler first sets the type parameter B of the collect method to be Vec<_> (since collect returns a B), then calls the implementation of FromIterator::from_iter for Vec<T> in the function body of Iterator::collect to collect some_iterator into a Vec.

user_40381910

collect is a generic function:

fn collect<B>(self) -> B where ...

The return type depends on the generic type parameter. Any specialization, with that type parameter specified, will return a fixed type. The specialization collect::<Vec<i32>> will return Vec<i32>.

The implementation is essentially an indirection:

fn collect<B>(self) -> B
where
    B: FromIterator<Self::Item>,
    Self: Sized
{
    FromIterator::from_iter(self)
}

The type B is required to be something that can be constructed from an iterator, using FromIterator. Many containers would fit that requirement. We have an iterator type, Self. So, the implementation just delegates to FromIterator. For the implementation, B is an abstract type parameter, and what we know about it is exactly the constraints we specify.

For the code in question:

let doubled: Vec<i32> = a.iter()
                         .map(|&x| x * 2)
                         .collect();

collect is not given its type parameter, so it must be inferred. Note that the implementation does not act in tandem, per se. The type must be chosen before the body is instantiated.

It is known from the signature of collect that the type parameter and the return type are equal. The result is assigned to doubled, so the type of doubled and the return type of collect are equal. The type of doubled is specified. Therefore, the type parameter to collect is that type.

For comparison, in a language like C++ one could write:

 template <typename Container, typename Iterator>
 auto collect(Iterator begin, Iterator end) -> Container
 {
     return Container(begin, end);
 }

 auto s = std::string("foo");
 auto v = collect<std::vector<char>>(s.begin(), s.end());

A salient difference is that C++'s type inference is less powerful. Types can be deduced from parameters, like Iterator, but other types cannot be deduced and must be specified, like Container.

user_32421460
Related