What's the difference between a trait's generic type and a generic associated type?

Question

This question is asked before generic associated types are available in Rust, although they are proposed and developed.

My understanding is that trait generics and associated types differ in the number of types which they can bind to a struct.

Generics can bind any number of types:

struct Struct;

trait Generic<G> {
    fn generic(&self, generic: G);
}

impl<G> Generic<G> for Struct {
    fn generic(&self, _: G) {}
}

fn main() {
    Struct.generic(1);
    Struct.generic("a");
}

Associated types bind exactly 1 type:

struct Struct;

trait Associated {
    type Associated;

    fn associated(&self, associated: Self::Associated);
}

impl Associated for Struct {
    type Associated = u32;

    fn associated(&self, _: Self::Associated) {}
}

fn main() {
    Struct.associated(1);
    // Struct.associated("a"); // `expected u32, found reference`
}

Generic associated types are a mix of these two. They bind to a type exactly 1 associated generator, which in turn can associate any number of types. Then what is the difference between Generic from the previous example and this generic associated type?

struct Struct;

trait GenericAssociated {
    type GenericAssociated;

    fn associated(&self, associated: Self::GenericAssociated);
}

impl<G> GenericAssociated for Struct {
    type GenericAssociated = G;

    fn associated(&self, _: Self::GenericAssociated) {}
}

Answer 1

Let's take a look at your last example again (shortened by me):

trait GenericAssociated {
    type GenericAssociated;
}

impl<G> GenericAssociated for Struct {
    type GenericAssociated = G;
}

This does not feature generic associated types! You are just having a generic type on your impl block which you assign to the associated type. Mh, ok, I can see where the confusion comes from.

Your example errors with "the type parameter G is not constrained by the impl trait, self type, or predicates". This won't change when GATs are implemented, because, again, this has nothing to do with GATs.

Using GATs in your example could look like this:

trait Associated {
    type Associated<T>; // <-- note the `<T>`! The type itself is 
                        //     generic over another type!

    // Here we can use our GAT with different concrete types 
    fn user_choosen<X>(&self, v: X) -> Self::Associated<X>;
    fn fixed(&self, b: bool) -> Self::Associated<bool>;
}

impl Associated for Struct {
    // When assigning a type, we can use that generic parameter `T`. So in fact,
    // we are only assigning a type constructor.
    type Associated<T> = Option<T>;

    fn user_choosen<X>(&self, v: X) -> Self::Associated<X> {
        Some(x)
    }
    fn fixed(&self, b: bool) -> Self::Associated<bool> {
        Some(b)
    }
}

fn main() {
    Struct.user_choosen(1);    // results in `Option<i32>`
    Struct.user_choosen("a");  // results in `Option<&str>`
    Struct.fixed(true);        // results in `Option<bool>`
    Struct.fixed(1);           // error
}

---

But to answer you main question:

What's the difference between a trait's generic type and a generic associated type?

In short: they allow to delay the application of the concrete type (or lifetime) which makes the whole type system more powerful.

There are many motivational examples in the RFC, most notably the streaming iterator and the pointer family example. Let's quickly see why the streaming iterator cannot be implemented with generics on the trait.

The GAT version of the streaming iterator looks like this:

trait Iterator {
    type Item<'a>;
    fn next(&self) -> Option<Self::Item<'_>>;
}

In current Rust, we could put the lifetime parameter on the trait instead of the associated type:

trait Iterator<'a> {
    type Item;
    fn next(&'a self) -> Option<Self::Item>;
}

So far so good: all iterators can implement this trait as before. But what if we want to use it?

fn count<I: Iterator<'???>>(it: I) -> usize {
    let mut count = 0;
    while let Some(_) = it.next() {
        count += 1;
    }
    count
}

What lifetime are we supposed to annotate? Apart from annotating the 'static lifetime, we have two choices:

• fn count<'a, I: Iterator<'a>>(it: I): this won't work because generic types of a function are choosen by the caller. But the it (which will become self in the next call) lives in our stack frame. This means that the lifetime of it is not known to the caller. Thus we get a compiler (Playground). This is not an option.
• fn count<I: for<'a> Iterator<'a>>(it: I) (using HRTBs): this seems to work, but it has subtle problems. Now we require I to implement Iterator for any lifetime 'a. This is not a problem with many iterators, but some iterators return items that don't life forever and thus they cannot implement Iterator for any lifetime -- just lifetimes shorter than their item. Using these higher ranked trait bounds often leads to secret 'static bounds which are very restricting. So this also doesn't always work.

As you can see: we cannot properly write down the bound of I. And actually, we don't even want to mention the lifetime in the count function's signature! It shouldn't be necessary. And that's exactly what GATs allow us to do (among other things). With GATs we could write:

fn count<I: Iterator>(it: I) { ... }

And it would work. Because the "application of a concrete lifetime" only happens when we call next.

If you are interested in even more information, you can take a look at my blog post “ Solving the Generalized Streaming Iterator Problem without GATs” where I try using generic types on traits to work around the lack of GATs. And (spoiler): it usually doesn't work.