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

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_word(&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.

---

Associated types are a grouping mechanism, so they should be used when it makes sense to group types together.

The Graph trait introduced in the documentation is an example of this. You want a Graph to be generic, but once you have a specific kind of Graph, you don't want the Node or Edge types to vary anymore. A particular Graph isn't going to want to vary those types within a single implementation, and in fact, wants them to always be the same. They're grouped together, or one might even say associated.

---

Associated types can be used to tell the compiler "these two types between these two implementations are the same". Here's a double dispatch example that compiles, and is almost similar to how the standard library relates iterator to sum types:

trait MySum {
    type Item;
    fn sum<I>(iter: I)
    where
        I: MyIter<Item = Self::Item>;
}

trait MyIter {
    type Item;
    fn next(&self) {}
    fn sum<S>(self)
    where
        S: MySum<Item = Self::Item>;
}

struct MyU32;

impl MySum for MyU32 {
    type Item = MyU32;

    fn sum<I>(iter: I)
    where
        I: MyIter<Item = Self::Item>,
    {
        iter.next()
    }
}

struct MyVec;

impl MyIter for MyVec {
    type Item = MyU32;
    fn sum<S>(self)
    where
        S: MySum<Item = Self::Item>,
    {
        S::sum::<Self>(self)
    }
}

fn main() {}

Also, https://blog.thomasheartman.com/posts/on-generics-and-associated-types has some good information on this as well:

In short, use generics when you want to type A to be able to implement a trait any number of times for different type parameters, such as in the case of the From trait.

Use associated types if it makes sense for a type to only implement the trait once, such as with Iterator and Deref.

---