Why does an existential type require a generic instead of an associated type?

Question

I have an existential type defined like this:

trait Collection {
    type Element;
}
impl<T> Collection for Vec<T> {
    type Element = T;
}

type Existential<T> = impl Collection<Element = T>;

A function, which takes a type implementing a trait with an associated type, returns this type. Why does this code work:

fn return_existential<I, T>(iter: I) -> Existential<T>
where
    I: IntoIterator<Item = T>,
    I::Item: Collection,
{
    let item = iter.into_iter().next().unwrap();
    vec![item]
}

playground

while this does not:

fn return_existential<I>(iter: I) -> Existential<I::Item>
where
    I: IntoIterator,
    I::Item: Collection,
{
    let item = iter.into_iter().next().unwrap();
    vec![item]
}

error: type parameter `I` is part of concrete type but not used in parameter list for the `impl Trait` type alias
  --> src/lib.rs:16:1
   |
16 | / {
17 | |     let item = iter.into_iter().next().unwrap();
18 | |     vec![item]
19 | | }
   | |_^

error: defining opaque type use does not fully define opaque type
  --> src/lib.rs:12:1
   |
12 | / fn return_existential<I>(iter: I) -> Existential<I::Item>
13 | | where
14 | |     I: IntoIterator,
15 | |     I::Item: Collection,
...  |
18 | |     vec![item]
19 | | }
   | |_^

error: could not find defining uses
  --> src/lib.rs:10:1
   |
10 | type Existential<T> = impl Collection<Element = T>;
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

playground

When using a Vec directly, this works fine:

fn return_existential<I>(iter: I) -> Vec<I::Item>
where
    I: IntoIterator,
    I::Item: Collection,
{
    let item = iter.into_iter().next().unwrap();
    vec![item]
}

playground

Note: Those examples are constructed while playing around with this feature. I won't use it anyway as long as my IDE is not aware of existential types. Additionally, the exact syntax is subject to change.

Calque

Are you asking (1) why a Work In Progress feature does not seem to be fully implemented OR (2) whether there is a fundamental limitation linked to existential types? – Repugnance

@Matthieu The latter. – Calque

To me, this just looks like the feature isn't fully polished. You should report a bug. – Mcswain

I filed this. – Calque

@oli-obk replied to this: I'm not 100% sure we can support this case out of the box and proposed the same solution as in my first code snippet as workaround. – Calque

I think this question might be out of date. The snippet type Existential<T> = impl Collection<Element = T>; does not compile on stable or nightly with the error "error: unconstrained opaque type" and "note: Existential must be used in combination with a concrete type within the same item" – Kwapong

Answer 1

The ATPIT, aka. existential type, means that the concrete type is defined by somewhere else (which is currently not well defined by rust) it is used.

In this case, it is the function return type that defines the concrete type, which means a certain generic instance of the existential type has to be defined by a certain generic instance of the function. Technically, the mapping relationship between the function and the existential is a surjection.

Now that the generic function return_existential is parameterized by I, which means that the generic existential type Existential also has to be parameterized by the I, so that each instance of Existential<I> is defined by return_existential<I>.

Thus it comes to a conclusion a generic existential type has to have exactly the same generic parameter list as which of the context where the concrete type is defined.

To easily understand, let's think about a counter-example:

If it is valid to have return_existential<I> return Existential<I::Item>,

for different types A, B and C,

where A: IntoIterator<Item = C>, B: IntoIterator<Item = C>

and return_existential<A> and return_existential<B> return different types,

what should Existential<C> be?

Should it be defined by return_existential<A> or return_existential<B>?

Scriven