Cam's Cyberspace

Recent Notes

Associated Types vs Type Parameters

Properties3
descriptionA type parameter is an input to impl selection and an associated type is an output, which is the whole reason Iterator carries an Item instead of being written Iterator of T.
tagscs, languages, type-theory
aliases

7 min read

Both features put a type placeholder in a trait, and both compile away. The question of which to reach for looks like style until you notice that they answer different questions. A type parameter asks the caller to choose. An associated type asks the implementor to choose, once, and then tells everyone else what the answer was.

The idea

Think of trait implementation as a relation between types. A trait with type parameters relates one implementing type to many parameter choices, so impl Trait<A> for X and impl Trait<B> for X can both exist and every use site must say which one it means. An associated type makes the relation functional in that position: given the implementing type, the associated type is determined, so nothing at the use site has to be annotated and the compiler can propagate it forward through inference. The choice between the two is not about syntax, it is about whether a position is an input to impl selection or an output of it.

The Iterator argument

The standard library defines Iterator with an associated type. type Item stands in for the type of the values the implementing type is iterating over, and next returns Option<Self::Item>. The Book poses the obvious objection directly: why not define the trait generically as Iterator<T> with fn next(&mut self) -> Option<T>?

The answer is what the generic version would permit. With generics, the types must be annotated in each implementation, and since Iterator<String> for Counter is also implementable, there could be multiple implementations of Iterator for Counter. Stated generally, when a trait has a generic parameter it can be implemented for a type multiple times, changing the concrete types of the generic parameters each time. The cost lands on the caller: calling next on a Counter would require type annotations to indicate which implementation is meant.

The associated-type version removes the ambiguity at its source. Because a trait cannot be implemented on a type more than once, the type of Item is chosen only once, since there can be only one impl Iterator for Counter, and no annotation is needed anywhere next is called. That is what makes iterator adapter chains readable. Every adapter in a chain reads its input item type off the previous stage as a determined fact. If Item were a parameter, map(...).filter(...).collect() would be an inference problem with a free variable at every link, and the turbofish would be mandatory rather than occasional.

This is the practical face of a distinction the type class tradition arrived at from the theory side: once a class can be instantiated at a type in more than one way, instance resolution stops being a function and the elaborator needs help from the programmer at every use.

Both, in one trait

std::ops::Add is the clean demonstration, because it uses both mechanisms at once and for opposite reasons.

trait Add<Rhs = Self> {
    type Output;
    fn add(self, rhs: Rhs) -> Self::Output;
}

Rhs is a type parameter, and its whole purpose is to allow more than one implementation. It carries the default Rhs = Self, so implementing Add for Point without further ceremony gives point-plus-point, but a Millimeters type can also carry impl Add<Meters> for Millimeters, setting Rhs explicitly instead of taking the default. Multiplicity is the feature: what you can add a thing to is genuinely a set of choices.

Output is an associated type, and it determines the type returned from add. Multiplicity here would be a defect. Given the left and right operand types, the result type is not a choice the caller should make, and if it were a parameter then a + b would be ambiguous in expression position, which is precisely where annotation is least welcome.

Default type parameters exist for two purposes: extending a type without breaking existing code, and allowing customization in specific cases most users will not need. Add is the second. Notice that the default softens the input parameter without converting it into an output. Rhs = Self supplies a value when the caller says nothing, while Output has no default at all because the implementor must state it.

What the reference adds

Associated types are type aliases associated with another type, and the alias is resolved through a projection. If Item has an associated type Assoc from Trait, then <Item as Trait>::Assoc names the type given in that implementation. Reading Self::Item as a projection rather than as a variable is what makes the inference story click: it is a lookup into a table keyed by the implementing type.

Three restrictions shape the design. Associated types cannot be defined in inherent implementations, which keeps them tied to a trait contract rather than to a type in isolation. They cannot be given a default implementation in traits, so unlike a method there is no fallback and every implementor must supply one. And there is an implicit Sized bound on associated types, relaxable with ?Sized, which is the same default that applies to ordinary type parameters and bites in the same place when the associated type is a slice or a trait object.

The contract framing is the one to keep. Associated types become part of the trait’s contract, and implementors must provide a type standing in for the placeholder, which means adding an associated type to a published trait is a breaking change in a way adding a defaulted method is not.

The decision, in one question

Ask whether two different answers for the same implementing type would ever be sensible. For Iterator::Item the answer is no, so it is an associated type. For Add<Rhs> the answer is yes, so it is a parameter. From settles it the same way: the standard library carries both impl From<char> for String and impl From<&str> for String, two implementations of one trait for one type, which is only possible because the source type is a parameter. Had From been written with an associated source type, String could be built from exactly one thing.

Languages without associated types have to encode the same intent with extra parameters, which is how recursive generic bounds end up looking the way they do: the output type is threaded through the signature as another input the caller is expected to get right, and correctness is maintained by convention instead of by the type system. Rust’s version pushes the obligation to the one place that actually knows the answer, and the modeling instinct behind it is the ordinary one from relations, where making a relation single-valued in a coordinate is exactly what turns it into a function you can compute with.

Sources

  • “Advanced Traits,” The Rust Programming Language. https://doc.rust-lang.org/book/ch20-02-advanced-traits.html . Supports the definition of associated types, Iterator with type Item and next returning Option<Self::Item>, the hypothetical Iterator<T> and its consequence of multiple implementations per type, the annotation burden at call sites, the single-implementation rule for associated types, associated types as part of the trait contract, the Add<Rhs = Self> definition with Output, the Millimeters/Meters example, and the two purposes of default type parameters.
  • “std::convert::From,” Rust standard library documentation. https://doc.rust-lang.org/std/convert/trait.From.html . Supports the coexistence of impl From<char> for String and impl From<&str> for String as two implementations of one trait for one type.
  • “Associated Items,” The Rust Reference. https://doc.rust-lang.org/reference/items/associated-items.html . Supports associated types as type aliases associated with another type, the <Item as Trait>::Assoc projection form, the prohibition on defining associated types in inherent implementations, the absence of defaults in traits, and the implicit Sized bound relaxable with ?Sized.

Graph View

Backlinks