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

Question

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:

• Why? Why returns the the exact line of code two different types?
• How can I return a Vec<T> in the second example?

Rust Playground

Answer 1

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