When is it appropriate to use an associated type versus a generic type?

In this question, an issue arose that could be solved by changing an attempt at using a generic type parameter into an associated type. That prompted the question "Why is an associated type more appropriate here?", which made me want to know more.

The RFC that introduced associated types says:

This RFC clarifies trait matching by:

• Treating all trait type parameters as input types, and
• Providing associated types, which are output types.

The RFC uses a graph structure as a motivating example, and this is also used in the documentation, but I'll admit to not fully appreciating the benefits of the associated type version over the type-parameterized version. The primary thing is that the distance method doesn't need to care about the Edge type. This is nice but seems a bit shallow of a reason for having associated types at all.

I've found associated types to be pretty intuitive to use in practice, but I find myself struggling when deciding where and when I should use them in my own API.

When writing code, when should I choose an associated type over a generic type parameter, and when should I do the opposite?

This is now touched on in the second edition of The Rust Programming Language. However, let's dive in a bit in addition.

Let us start with a simpler example.

When is it appropriate to use a trait method?

There are multiple ways to provide late binding:

trait MyTrait {
    fn hello_world(&self) -> String;
}

Or:

struct MyTrait<T> {
    t: T,
    hello_world: fn(&T) -> String,
}

impl<T> MyTrait<T> {
    fn new(t: T, hello_world: fn(&T) -> String) -> MyTrait<T>;

    fn hello_world(&self) -> String {
        (self.hello_world)(self.t)
    }
}

Disregarding any implementation/performance strategy, both excerpts above allow the user to specify in a dynamic manner how hello_world should behave.

The one difference (semantically) is that the trait implementation guarantees that for a given type T implementing the trait, hello_world will always have the same behavior whereas the struct implementation allows having a different behavior on a per instance basis.

Whether using a method is appropriate or not depends on the usecase!

When is it appropriate to use an associated type?

Similarly to the trait methods above, an associated type is a form of late binding (though it occurs at compilation), allowing the user of the trait to specify for a given instance which type to substitute. It is not the only way (thus the question):

trait MyTrait {
    type Return;
    fn hello_world(&self) -> Self::Return;
}

Or:

trait MyTrait<Return> {
    fn hello_world(&self) -> Return;
}

Are equivalent to the late binding of methods above:

• the first one enforces that for a given Self there is a single Return associated
• the second one, instead, allows implementing MyTrait for Self for multiple Return

Which form is more appropriate depends on whether it makes sense to enforce unicity or not. For example:

• Deref uses an associated type because without unicity the compiler would go mad during inference
• Add uses an associated type because its author thought that given the two arguments there would be a logical return type

As you can see, while Deref is an obvious usecase (technical constraint), the case of Add is less clear cut: maybe it would make sense for i32 + i32 to yield either i32 or Complex<i32> depending on the context? Nonetheless, the author exercised their judgment and decided that overloading the return type for additions was unnecessary.

My personal stance is that there is no right answer. Still, beyond the unicity argument, I would mention that associated types make using the trait easier as they decrease the number of parameters that have to be specified, so in case the benefits of the flexibility of using a regular trait parameter are not obvious, I suggest starting with an associated type.