Cannot infer type for type parameter `S` when using HashSet::from_iter

Question

I am trying to solve an online challenge that involves comparing two sets. I followed this answer to convert my Vec<i32> output to HashSet

use std::collections::HashSet;
use std::iter::FromIterator;

struct Solution {}

impl Solution {
    pub fn solve(nums: Vec<i32>, k: i32) -> Vec<i32> {
        // todo, return dummy for now
        return vec![1, 2];
    }
}

fn main() {
    assert_eq!(
        HashSet::from_iter(Solution::solve(vec![1, 2, 3], 2)),
        HashSet::from_iter(vec![1i32, 2i32])
    )
}

For reasons I don't understand yet, the compilation fails:

error[E0282]: type annotations needed
  --> src/main.rs:15:9
   |
15 |         HashSet::from_iter(Solution::solve(vec![1, 2, 3], 2)),
   |         ^^^^^^^^^^^^^^^^^^ cannot infer type for type parameter `S` declared on the struct `HashSet`

It works fine for HashSet::from_iter(vec![1i32, 2i32])

I tried adding a type annotation like HashSet::from_iter::<Vec<i32>> with no avail. I also read the source implementation but still can't figure out what makes the compiler complain.

I can work around it by declaring it explicitly or construct the HashSet with a for loop and inserts, but I would like to understand what is going on here.

I'm using Rust 1.43.1.

Answer 1

I believe the answer from Kitsu is subtly incorrect since it suggests that Rust cannot infer the type of T because here may be an iterator implemented for a type P that collects a different type T (more on this at the end).

What's really happening

In fact, type inference for type S in HashSet<T, S> has nothing to do with the type of T. The issue is that there is no information in your program that allows the compiler to infer the type of S.

It is correct that adding a type parameter is sufficient to resolve the ambiguity:

HashSet::<i32>::from_iter(vec![1, 2, 3]);

This has nothing to do with the actual type you specify. Indeed, this works as well:

HashSet::<_>::from_iter(vec![1, 2, 3]);

The reason is that the definition of HashSet in the standard library includes a default type for S:

pub struct HashSet<T, S = RandomState> {
    base: base::HashSet<T, S>,
}

By writing HashSet::<_>::from_iter(vec![1, 2, 3]); you're telling the compiler that it should use the default type for S, which is RandomState.

What about multiple implementations?

Kitsu's answer states that type inference fails for S because there might be multiple implementations of FromIterator. This is incorrect, but having multiple implementations can cause type inference to fail for T.

Consider this example:

fn iterator_demo() {
    use std::collections::HashSet;
    use std::hash::{BuildHasher, Hash};
    use std::iter::FromIterator;

    struct Empty;

    impl<T, S> FromIterator<Empty> for HashSet<T, S>
    where
        T: Eq + Hash,
        S: BuildHasher + Default,
    {
        fn from_iter<I>(iter: I) -> HashSet<T, S>
        where
            I: IntoIterator<Item = Empty>,
        {
            iter.into_iter().for_each(drop);
            HashSet::default()
        }
    }

    let x = HashSet::<_>::from_iter(vec![Empty, Empty]);
}

This causes type inference to fail; note that this is a failure to infer T, not S:

error[E0282]: type annotations needed for `HashSet<T>`
  --> src/lib.rs:22:13
   |
22 |     let x = HashSet::<_>::from_iter(vec![Empty, Empty]);
   |         -   ^^^^^^^^^^^^^^^^^^^^^^^ cannot infer type
   |         |
   |         consider giving `x` the explicit type `HashSet<T>`, with the type parameters specified

Specifying the type resolves this ambiguity:

let x = HashSet::<String>::from_iter(vec![Empty, Empty]);

Credit to matt1992 on the Rust Discord for helping me to understand what's really happening here.

Answer 2

Let's look at the FromIterator::from_iter declaration, you've been using:

fn from_iter<T>(iter: T) -> Self
where
    T: IntoIterator<Item = A>,

After specifying HashSet compiler can deduce that Self is HashSet<S> for some S. T for your particular case can be deduced as a Vec<i32>: IntoIterator<Item = i32> (for the second line that is resolved after you explicitly specified an integer type).

But still, S is not deduced because, in general, you may have an implementation that collects HashSet<u64> from IntoIterator<Item = u8>. So compiler cannot understand what are items of the collected type. Then if you swap the expressions of the assert_eq error source changes:

assert_eq!(
    HashSet::from_iter(vec![1i32, 2i32]),
/*
   |
15 |     HashSet::from_iter(vec![1i32, 2i32]),
   |     ^^^^^^^^^^^^^^^^^^ cannot infer type for type parameter `S` declared on the struct `HashSet`
*/
    HashSet::from_iter(Solution::solve(vec![1, 2, 3], 2)),
)

The solution is fairly straightforward: you need to specify the item type of your HashSet:

assert_eq!(
    HashSet::<i32>::from_iter(Solution::solve(vec![1, 2, 3], 2)),
    HashSet::from_iter(vec![1i32, 2])
)