Confused about traits, generics and/versus associated types

Hello everyone,

There are some aspects of trait definitions that I have a hard time to grasp, mainly the existence of both "regular" generics (the ones whose syntax is the same as for functions, structures and enums), associated types and the relationship between the two.

Let's start with the following code example (please tell me if there are any mistakes):

trait BinaryOperator<Rhs, Out> {
    fn binary_operation(&self, rhs: &Rhs) -> Out;
}

impl<Ket, Complex> BinaryOperator<Ket, Complex> for Bra {
    fn binary_operation(&self, rhs: &Ket) -> Complex {
        // TODO
    }
}

According to what I understood about associated types from the book, the following code example should be completely equivalent to the previous one (again correct me if you notice any mistakes):

trait BinaryOperator {
    type Rhs;
    type Out;

    fn binary_operation(&self, rhs: &Self::Rhs) -> Self::Out;
}

impl BinaryOperator for Bra {
    type Rhs = Ket;
    type Out = Complex;

    fn binary_operation(&self, rhs: &Ket) -> Complex {
        // TODO
    }
}

My questions are the following:

  • Are the two examples above actually equivalent ? Or are there subtle difference in terms of functionality or whatever ?
  • Can associated types replace "regular" generics in all cases ? Or are there some catch-22 type situations ? (Is this where GATs come into play ?)
  • I know that the core and standard libraries use a combination of both (for example: the Add trait), so are "regular" generics and associated items actually complementary features ? If yes, then how so ?

Thank you in advance !

P.S. I have a hard time understanding what GATs bring to the table. Is it simply about being able to write something like:

trait BinaryOperator {
    type Rhs;
    type Out;

    fn binary_operation(&self, rhs: &Self::Rhs) -> Self::Out;
}

impl<T> BinaryOperator for Bra {
    type Rhs = Ket;
    type Out = T;

    fn binary_operation(&self, rhs: &Ket) -> T {
        // TODO
    }
}

Or is this already possible and GATs are about something more exotic ?

2 Likes

No, they are not completely equivalent.

First off, generic arguments are inputs to a type-level computation: when you have a free type parameter, it can (and will) be chosen by the caller. In contrast, associated types are outputs: they are determined by an implementation of a trait, and can not be changed by the user of the code. So, for example:

fn greet<T: Display>(name: T) {
    println!("Hello, {}", name);
}

here, T may be whatever, as long as it's Display. You can call greet() with arguments of type &str, u32, f64, or even with a custom type you defined.

In contrast, if you look at the definition and usage of Deref, for example:

trait Deref {
    type Target;

    fn deref(&self) -> &Self::Target;
}

struct String {
   ...
}

impl Deref for String {
    type Target = str;
    ...
}

Then you can see how String always derefs to an &str. There is no way you, the user of String and Deref can change this.


As a consequence, there is another, practical difference between generic traits and traits with associated types. If you have a generic trait, you can potentially implement multiple versions of that trait for a given type. (Since a generic struct/enum/trait/function is not really a struct/enum/trait/function, it's merely a blueprint for making one.) However, if you have a non-generic trait, then you can only implement it once for a given type. If your non-generic trait has an associated type, then of course you can only ever have one associated type specified in the implementation. So this works:

trait MyTrait<T> {
    ...
}

impl MyTrait<u32> for MyType {
    ...
}
impl MyTrait<String> for MyType {
    ...
}

but this wouldn't:

trait MyTrait {
    type Assoc;
}

impl MyTrait for MyType {
    type Assoc = u32;
}
impl MyTrait for MyType {
    type Assoc = String;
}
8 Likes

The RFC that introduced associated types may be illuminating. You have to take some care in reading it, as it was pre-1.0 (before Rust was stable, so many things have changed) and not all of the ideas in the RFC have been implemented (there is no such thing as an associated lifetime for example). But with that caveat, I recommend the sections on

Another name for GATs is ATCs -- associated type constructors. The idea is that you need the ability to construct a type (by supplying a generic parameter) internally to the trait implementation. The most common example are borrows:

trait Trait {
    // Logically should be an associated type...
    type Output;
    // ...but that's a singular type and not a type constructor,
    //    so this won't actually work : ..............vvvv
    fn borrow<'a>(&'a self) -> <Self as Trait>::Output<'a>;
}

One can often hack around this with a second helper trait, but with GATs we can instead have

trait Trait {
    // You may have to spell out other bounds like `where Self: 'a`
    // for GATs work safely; the details are still a work in progress.
    type Output<'a>;
    // But the main idea is that this would now work:
    fn borrow<'a>(&'a self) -> <Self as Trait>::Output<'a>;
}

You can read more about the motivation in the associated type RFC:

And this blog post:

And finally, this follow-up blog post goes into designs beyond borrowing where ATCs (GATs) can be useful.

2 Likes

Thanks @H2CO3 and @quinedot, I think I get it better now.

Basically, every generic argument adds a degree of freedom to our trait (and thus to any type that implements it). Associated items on the other hand define constraints that are unique for each combination of generic argument values.

Edit: As a follow up question, can we apply trait bounds on generic arguments and/or associated items ?

Now on the subject of @nikomatsakis' blog posts, I guess I've hit my limit here, because I still don't understand what makes ATCs (or GATs or whatever) different from what is available now in stable Rust, even after reading them twice. :sweat_smile:

No, not quite. Associated items define what concrete types, functions, consts, etc. should result when you evaluate a type as an implementor of the trait.

That is basically the point of parametric generics.

Well that is exactly what I meant by constraint. For example, given the following code:

trait MyTrait<T1, T2> {
    type I1;
    type I2;
    ...
}

For given values of T1 and T2, the values of I1 and I2 are uniquely determined (by the implementer, yes), or in other words: the values of I1 and I2 are constrained by the values of T1 and T2.

Sorry, my field of expertise is not computer science, so I might not know what the right term in the present context is and so I fall back to the definitions applicable in my field. Plus, English is not my first language.

Ah, I see, sorry. Indeed, "constraint" in the context of traits and generics has a more specific meaning (to me) – it relates to trait bounds on type variables, equality of associated types, and similar relations that must hold.

Those work too. Although I don't quite understand what you mean by

What is there besides trait bounds and lifetimes ?

Constrained is right term, it just rarely comes up. Whereas the constraints imposed by trait bounds and lifetime relations are ever-present, and you used the word "constraint" specifically on the first go :slightly_smiling_face:.

Well, let's take a look. Here's an example from the second post, modified to compile on nightly. It doesn't look great due to the lack of implied bounds, but anyway, it works. We could implement the collection family pattern for LinkedList and VecDeque and whatever else, and we could then floatify them. Now let's see if we can get rid of the GATs -- it has two, a type GAT in CollectionFamily and a lifetime GAT in Collection<_>.

There actually is a reasonably well-known pattern for emulating lifetime GATs on stable. I've applied it here, and though it has added some noise, everything still works. Part of why it works is that supertrait bounds are implied, so when you know something implements Collection<Item>, you can just assume they implement IterType<'any, Item> too. That's what the for<'a> ... supertrait bound is giving us. Great, half-way there.

Now let's apply that pattern to CollectionFamily and uh... oh, dang it.

error: only lifetime parameters can be used in this context
 --> src/lib.rs:5:33
  |
5 | pub trait CollectionFamily: for<T> MemberType<T> {}
  |                                 ^

Higher-ranked bounds (for<'any> ...) only work with lifetimes, not types.

We can push forward though...

-pub trait CollectionFamily: for<T> MemberType<T> {}

 pub trait Collection<Item>: for<'a> IterType<'a, Item> {
     // Backlink to `Family`.
-    type Family: CollectionFamily;
+    type Family: MemberType<Item>;
-impl CollectionFamily for VecFamily {}
 pub fn floatify<C: Collection<i32>>(ints: &C) -> <C::Family as MemberType<f32>>::Member 
+where
+    C::Family: MemberType<f32> 
 {

And this works, but

  • We've lost the supertrait bound, so we have to mention the MemberType<_> bounds everywhere
  • There's no actual guarantee a family implements MemberType<T> for all T, where as you had to with the GAT
  • There's no actual guarantee you're working with a family as intended [1] since there can be a different implementation per input T, versus a single definition with the GAT

In summary, something GATs give us that we don't have today is for<T> bounds in the form of

trait ForTSomeBound {
    type SensibleName<T>: SomeBound;
}

They also make lifetime GATs nicer...ish. [2] I expect that to gradually improve over time as we get more implied and/or inferred bounds though.


  1. floatify there goes from a HashSet to a Vec ↩ī¸Ž

  2. It's considered a big enough deal that we still don't have lending iterators, etc, in std. ↩ī¸Ž

1 Like

Eg. a trait bound of the form T: Iterator<Item = String> constrains the set of types to only those iterators that yield strings.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.