CODEWITHSUNDEEP
genericsrustvector
SleepyX667
SleepyX667

Reputation: 690

Why does .collect() sometimes infer Vec but other times infers &Vec?

I have the following code-snippets:

1. get the n-th element of a Vec recursively

fn helper<T: Clone>(n: usize, current_n: usize, current_xs: &Vec<T>, accumulator: Option<T>) -> Option<T> {
    if current_n > n {
        accumulator
    } else {
        let head = current_xs.get(0).cloned();
        let tail = current_xs.clone().into_iter().skip(1).collect();
        return helper(n, current_n + 1, &tail, head);
    }
}

2. get the length of a Vec recursively

fn helper<T: Clone>(current_xs: &Vec<T>, accumulator: usize) -> usize {
    if current_xs.is_empty() {
        accumulator
    } else {
        let tail = current_xs.clone().into_iter().skip(1).collect();
        return helper(tail, accumulator + 1)
    }
}

My Question is about that line:

let tail = current_xs.clone().into_iter().skip(1).collect();

In the first example the tail variable is of Type Vec<T> and in the second example the tail variable is of type &Vec<?>.

Questions:

Rust Playground

Upvotes: 0

Views: 868

Answers (2)

Jmb
Jmb

Reputation: 23329

In your second example, collect can return anything that implements FromIterator<Self::Item> (here Self::Item is T). So the compiler tries to guess the type of tail by looking at how it is used. When you call helper (tail, …), the compiler guesses that tail should have the same type as the first argument to helper, aka &Vec<U> for some as yet unknown type U. However, &Vec<U> does not implement FromIterator<T>, so the compiler bails out at this point.

OTOH when you call helper (&tail, …), the compiler guesses that &tail should have type &Vec<U> for some U, and therefore tail should have type Vec<U>. The compiler can then continue and determine that U==T, which gives the complete type of tail as Vec<T>.

As an aside, here is a more idiomatic implementation of your first helper that avoids unnecessary copies. Something similar can be done for the second one:

fn helper<T: Clone> (n: usize, current_n: usize, current_xs: &[T], accumulator: Option<&T>) -> Option<T> 
{
    if current_n > n {
        accumulator.cloned()
    } else {
        let head = current_xs.get (0);
        let tail = &current_xs[1..];
        return if tail.is_empty() { 
            None
        } else {
            helper (n, current_n + 1, tail, head)
        };
    }
}

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    println!("Element 3: {:?}", helper (3, 0, &v, None));
    println!("Element 10: {:?}", helper (10, 0, &v, None));
}

Playground

Upvotes: 2

SleepyX667
SleepyX667

Reputation: 690

The problem is:

Example 1: calls the recursive function with

return helper(n, current_n + 1, &tail, head); // &tail

Example 2: calls the recursive function with:

return  helper(tail, accumulator + 1) // tail

Changing tail to &tail everything works. At the moment I can't exactly explain why, so i would wait to accept this as correct answer and hope someone else can completely answer it.

Rust Playground

Upvotes: -1

Related Questions