Fear Not the Association of Types

Rough data hit my eyes recently and the take­away was unsur­pris­ing: Rust asso­ci­ated types are mis­un­der­stood. In Chap­ter 17 of the Rust Book Exper­i­ment Will Crich­ton decided to inject ques­tions on API design. The ques­tions have been up long enough for us to see the pre­lim­i­nary data, and so far, the results are not great. Many ques­tions involv­ing asso­ci­ated types on traits were answered incor­rectly. I’ve been knee-deep in Rust traits recently and feel I have enough energy to chan­nel some pas­sion into a post on asso­ci­ated types. This post serves two pur­poses

1. to pro­vide a rule-of-thumb to help you deter­mine when a type para­me­ter should be an asso­ci­ated type
2. to show that asso­ci­ated types are no more than the return of a type-level func­tion

The sec­ond pur­pose, really a goal, may sound scary to you at first, but it’s my job to con­vince you that it’s true. You may not even know what I mean by “type-level func­tion,” we’ll cover all of this in time—please stay along for the ride.

Asso­ci­ated types are used all over the Rust stan­dard library. If you’re unfa­mil­iar with Rust, it may shock you to find that com­mon oper­a­tions

• mul­ti­pli­ca­tion: 2 * 3, or <i32 as Mul<i32>>::mul(2, 3)
• index­ing: vs[0], or <Vec<i32> as Index<usize>>::index(&vs, 0)
• pointer deref­er­enc­ing: *ptr, or <&i32 as Deref>::deref(ptr)

are imple­mented with traits and asso­ci­ated types, but let’s not get ahead of our­selves. Before we dig into the broader use of asso­ci­ated types let’s look at one com­mon exam­ple, the Mul trait.

pub trait Mul<Rhs> {
    type Output;

    fn mul(self, rhs: Rhs) -> Self::Output;
}

After this post I want you to be able to answer these two ques­tions: “Why is Out­put an asso­ci­ated type?” and “Why is Rhs a type para­me­ter?” If you can answer these well, the API of your future Rust libraries will be struc­tured well, and I look for­ward to using them. But let’s start from the begin­ning and write a ver­sion of the trait Mul with­out an asso­ci­ated type; our ver­sion shall, of course, be called Bad­Mul.

pub trait BadMul<Rhs, Output> {
    fn mul(self, rhs: Rhs) -> Output;
}

In the trait def­i­n­i­tion for Bad­Mul there are three type para­me­ters: Self, Rhs, and Out­put. Self is an implicit type para­me­ter to every trait and denotes the type for which the trait will be imple­mented. In the con­text of mul­ti­pli­ca­tion, Self is the type of the left-hand side operand. This means that the method mul has the type sig­na­ture fn mul(self: Self, rhs: Rhs) -> Out­put. The imple­men­ta­tion for Bad­Mul between two inte­gers is as fol­lows

impl BadMul<i32, i32> for i32 {
  fn mul(self, rhs: i32) -> i32 {
      self * rhs
  }
}

Edit, in Rust, like any lan­guage with sized inte­gers, mul­ti­pli­ca­tion between two i32s may over­flow. I’ve cho­sen to ignore over­flow for this post.In this trait imple­men­ta­tion we spec­i­fied that all three type para­me­ters, Self, Rhs, and Out­put, equal i32. In ele­men­tary school you mem­o­rized inte­ger mul­ti­pli­ca­tion tables and as you got older learned that we can mul­ti­ply much more. Let’s take a breath and jot down some of the types we could sub­sti­tute for our type para­me­ters.

• Self could be one of { i32, i64, f32, Matrix<i32>, … }
• Rhs could be one of { i32, i64, f32, Matrix<i32>, … }
• Out­put could be one of { i32, i64, f32, Matrix<i32>, … }

If you looked at the above and nod­ded your head. If you thought “yeah, that looks about right,” then I’m about to shat­ter your world. The above is wrong. One of those lines is not like the oth­ers. Take a ran­dom type from each of the above sets and sub­sti­tute it for the type in the sig­na­ture of mul. I’ll even write down a few for you.

• ✅ fn mul(self: i32, rhs: i32) -> i32
• ✅ fn mul(self: f32, rhs: i32) -> f32
• ❌ fn mul(self: i32, rhs: f32) -> Matrix<i32>

The last type sig­na­ture makes no sense. When you mul­ti­ply an inte­ger and a float you get a float, not a two-dimen­sional matrix, at least in tra­di­tional mul­ti­pli­ca­tion. So what went wrong? The type for Out­put is depen­dent on the actual types for Self and Rhs. We aren’t free to choose the type for Out­put if we’ve cho­sen Self and Rhs—there exists one nat­ural choice for Out­put once the oth­ers have been fixed. The depen­dency between type para­me­ters indi­cates that Out­put should be an asso­ci­ated type on the trait Bad­Mul. Of course, after mov­ing Out­put to be an asso­ci­ated type we should also rename the trait to Good­Mul, or to std::ops::Mul. I claim that if such a depen­dency exists between type para­me­ters, the depen­dent type para­me­ter should become an asso­ci­ated type.

Before mov­ing for­ward, let’s cor­rect the record by pro­vid­ing a bet­ter Mul trait def­i­n­i­tion with Out­put as an asso­ci­ated type and an exam­ple imple­men­ta­tion for mul­ti­ply­ing inte­gers and floats.

pub trait Mul<Rhs> {
    type Output;

    fn mul(self, rhs: Rhs) -> Self::Output;
}

impl Mul<f32> for i32 {
  type Output = f32;

  fn mul(self, rhs: f32) -> Self::Output {
    self as f32 * rhs
  }
}

When parameters become associates

If you were to stop read­ing here the rule-of-thumb for whether or not a type para­me­ter should be an asso­ci­ated type would read

A type para­me­ter depen­dent on other type para­me­ters should be an asso­ci­ated type.

Though I do believe this is an OK rule-of-thumb, it’s more hand-wavy than I’d like. Let’s make it more spe­cific by con­sid­er­ing one more change to the Mul trait def­i­n­i­tion. Con­sider the type para­me­ter Rhs, should Rhs be an asso­ci­ated type? Is Rhs depen­dent on the type of Self? To help you decide, let’s assign Self to be the con­crete type Vec<i32>. Pro­vided this assign­ment to Self, let’s list types we could assign to Rhs.

• ✅ i32
• ✅ f32
• ❌ Vec<i32>

We should not assign Rhs = Vec<i32> because Vec<i32> * Vec<i32> is an ambigu­ous oper­a­tion. Mul­ti­pli­ca­tion between vec­tors could mean ele­ment-wise mul­ti­pli­ca­tion, an inner vec­tor prod­uct, or an outer vec­tor prod­uct. Though some lan­guages/libraries do choose a default oper­a­tion for vec­tor mul­ti­pli­ca­tion, choos­ing a default is, in my opin­ion, poor design and for this post we will not con­sider it valid. There­fore, the choice to assign Vec<i32> to Self has reduced the pos­si­ble types assign­a­ble to Rhs. So yes, Rhs is depen­dent on Self, but should it be an asso­ci­ated type? The answer is no. To see why, let’s write another trait def­i­n­i­tion that declares Rhs an asso­ci­ated type. This ver­sion shall be called Restrict­ed­Mul.

trait RestrictedMul {
    type Rhs;
    type Output;

    fn mul(self, rhs: Self::Rhs) -> Self::Output;
}

impl RestrictedMul for i32 {
    type Rhs = i32;
    type Output = i32;

    fn mul(self, rhs: Self::Rhs) -> Self::Output {
        self * rhs
    }
}

impl RestrictedMul for i32 {
    type Rhs = f32;
    type Output = f32;

    fn mul(self, rhs: Self::Rhs) -> Self::Output {
        self * rhs
    }
}

The above code fails to type check. See for your­self in this play­ground. The code fails to type check because there are two imple­men­ta­tion blocks with the same header, or as rustc says, there are “con­flict­ing imple­men­ta­tions of Restrict­ed­Mul for i32”.

error[E0119]: conflicting implementations of trait `RestrictedMul` for type `i32`
  --> src/main.rs:17:1
   |
8  | impl RestrictedMul for i32 {
   | -------------------------- first implementation here
...
17 | impl RestrictedMul for i32 {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `i32`

The core issue is that for one left-hand side type, for exam­ple Self = i32, there are mul­ti­ple types we want to assign to the Rhs. After all, you can mul­ti­ply i32 with many other types: i32, i64, and Matrix<i32>, etc. When a type is a type para­me­ter, it sig­nals that there is more than one way to instan­ti­ate the type. (I.e., assign the para­me­ter a type.) When a type is an asso­ci­ated type, it sig­nals that it can be instan­ti­ated with exactly one type per imple­men­ta­tion block. Asso­ci­ated types aren’t just those depen­dent on other types, but spec­ify a map­ping from many types to one asso­ci­ated type. Our rule-of-thumb should read

A type para­me­ter should be an asso­ci­ated type if for all imple­men­ta­tion blocks there exists a rela­tion­ship map­ping the other type para­me­ters to it. (I.e., you can cre­ate a table map­ping the other para­me­ters to the asso­ci­ated type, like we did for Mul.)

This rule-of-thumb is bet­ter than the prior notion of depen­dence: Not only are asso­ci­ated types depen­dent on the trait’s type para­me­ters, but they are instan­ti­ated with a sin­gle type. In a pre­vi­ous post on Rust’s stan­dard library, Pret­zel Ham­mer puts forth a rule-of-thumb that reads

Use asso­ci­ated types when there should only be a sin­gle impl of the trait per type. Use generic types when there can be many pos­si­ble impls of the trait per type.

We are try­ing to say the same thing. I think their rule lacks a bit of speci­ficity, espe­cially when traits have both type para­me­ters and asso­ci­ated types. Take for exam­ple the Mul trait, there are sev­eral imple­men­ta­tions with i32 as the Self type. Though both of these rules-of-thumb are intu­ition-based and require fore­sight into how future devel­op­ers will use your trait. This fore­sight is a lit­tle scary, espe­cially if you’re new to Rust or traits. But I argue that you engage in this rea­son­ing fre­quently; every time you write a func­tion you per­form sim­i­lar rea­son­ing. We can pig­gy­back on your engi­neer­ing instinct about func­tions to help you rea­son about asso­ci­ated types.

From types to values, then back to types

I don’t want to get lost in type-the­o­retic weeds, so let’s allow our­selves to for­get sta­tic types for a moment. Let’s write a mul­ti­pli­ca­tion func­tion in a dynam­i­cally typed lan­guage, I pre­fer Julia, so Julia is what I will use. (If you’re unfa­mil­iar, the syn­tax is quite easy.)

function mul(a, b)
  a * b
end

The func­tion mul has two inputs and one out­put, C = mul(A, B). I shall ask again, what are some pos­si­ble val­ues we can pick for A, B, and C? Here’s some exam­ples

• A could be one of { 0, 1, 2, 2.0, … }
• B could be one of { 0, 1, 4/3, 2, … }
• C could be one of { 0, 1, 2, 3.14, … }

Just as before, we find that the set for C is not the same as the oth­ers. If you pick a ran­dom num­ber from each of the sets and assign the value to our vari­ables, the line 2 = mul(0, 1) would be non­sense; we know that 0 * 1 is equal to 0, not 2. The value of C depends on the val­ues cho­sen for A and B. You know this because you spent all that time in ele­men­tary school mem­o­riz­ing mul­ti­pli­ca­tion tables. These tables map two operand val­ues to the mul­ti­plied out­put value.

In the con­text of val­ues, my prompt­ing you to “pick a value for C” sounds weird, if not wrong. You don’t pick C you com­pute it. C is the return value of the func­tion and depends on the two input val­ues: A, and B. We want to trans­plant this same logic to under­stand why the trait def­i­n­i­tion of Bad­Mul was bad. In that def­i­n­i­tion Out­put was a type para­me­ter, but it doesn’t behave like a para­me­ter, you can’t pick it’s type. Instead, Out­put rep­re­sents a sin­gle spe­cific type as the result of the mul­ti­pli­ca­tion. Type para­me­ters are input types and asso­ci­ated types are out­put types. There exists a map­ping from input types to a out­put types, just like our ele­men­tary school mul­ti­pli­ca­tion table for val­ues, we can write a mul­ti­pli­ca­tion table for types.

This table shows that if you pro­vide two input types, which are rep­re­sented as the row and col­umn header, you get back an out­put type. This behav­ior is what I call a type-level func­tion: You pro­vide two input types and get back an out­put type, just how func­tions on val­ues take input val­ues (para­me­ters) and return an out­put value (the return).

By now, you may start to see why I describe asso­ci­ated types as the out­put of a type-level func­tion. A mul­ti­pli­ca­tion func­tion on val­ues maps two input num­bers to a third and it’s nat­ural to define this map­ping as a func­tion. For the same two input val­ues the mul func­tion always returns the same out­put value.

For traits, the same type para­me­ters always map to the same asso­ci­ated type. One ben­e­fit for type para­me­ters is that they guar­an­tee this. For exam­ple, mul­ti­ply­ing a Matrix<i32> with a i32 always returns Matrix<i32>—no ques­tions asked. In Rust you access the out­put type with

  <i32 as Mul<i32>>::Output
  /            \        \
Self          Rhs      Output

but if we wanted to mimic the struc­ture of the Julia mul func­tion, we could write

  i32 = Mul<i32, i32>
  /         /     \
Output    Self    Rhs

By mov­ing Out­put from a type para­me­ter to an asso­ci­ated type in the Mul trait we sta­t­i­cally guar­an­tee that for two input types there will exist only one imple­men­ta­tion of the mul­ti­ply method. The def­i­n­i­tion of Bad­Mul did not guar­an­tee this. Remem­ber that we pro­vided an imple­men­ta­tion for fn mul(self: i32, rhs: i32) -> i32, using Bad­Mul we could pro­vide a sec­ond imple­men­ta­tion that defines mul­ti­pli­ca­tion as fn mul(self: i32, rhs: i32) -> f32. This poor deci­sion shall have some neg­a­tive impli­ca­tions, as we will see.

// A refresher on the definition
pub trait BadMul<Rhs, Output> {
  fn mul(self, rhs: Rhs) -> Output;
}

// The only correct implementation
impl BadMul<i32, i32> for i32 {
    fn mul(self, rhs: i32) -> i32 {
        self * rhs
    }
}

// Some engineer's poor decision to provide another
impl BadMul<i32, f32> for i32 {
    fn mul(self, rhs: i32) -> f32 {
        (self * rhs) as f32
    }
}

In this ver­sion of the Rust uni­verse there are now two dif­fer­ent imple­men­ta­tions for mul­ti­pli­ca­tion between inte­gers. The Rust com­piler would need to infer the out­put type to cor­rectly pick which imple­men­ta­tion block to use. Even if there is only a sin­gle imple­men­ta­tion block, the Rust com­piler can­not pick the return type based on the imple­men­ta­tion block—it still needs to be inferred. This would require devel­op­ers to anno­tate more types than would oth­er­wise be nec­es­sary. Edit, I just learned about the type infer­ence change in Rust 1.80 that broke any crate with time as a depen­dency. Pre-1.80, Rust allowed infer­ence to resolve a type if there was a sin­gle imple­men­ta­tion block, despite this being unsound. Post-1.80 dis­al­lowed this behav­ior, thus break­ing infer­ence for any crate that relied on the pat­tern, one exam­ple being the time crate.

fn main() {
  println!("{}", 3 * 2);

  println!("{}", <i32 as BadMul<i32, _>>::mul(3, 2));
}

If the def­i­n­i­tion of Mul in the Rust stan­dard library were writ­ten like Bad­Mul, the first line in the above code would behave like the sec­ond line of code does. This is unde­sir­able because the code fails to type check.

error[E0283]: type annotations needed
   --> src/main.rs:20:18
   |
20 |   println!("{}", <i32 as BadMul<i32, _>>::mul(3, 2));
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                  cannot infer type of the type parameter `Output`
   |                  declared on the trait `BadMul

The above code doesn’t com­pile because the Rust com­piler doesn’t know how to infer the type para­me­ter Out­put. It needs to be spec­i­fied. The broader impli­ca­tion is that type para­me­ters that should be asso­ci­ated types require devel­op­ers to anno­tate more types. To recap, asso­ci­ated types guar­an­tee that there exists a sin­gle type for the imple­men­ta­tion block, thus help­ing the com­piler to infer types rather than requir­ing it to infer more than nec­es­sary.

<Self as Iterator<Item = Example>>::next(&mut self)

Rea­son­ing about asso­ci­ated types may be eas­ier with the Mul trait, after all, it fits my pro­posed men­tal model very well and mul­ti­pli­ca­tion is some­thing with which we’re all famil­iar. Lots of traits in the Rust stan­dard library use asso­ci­ated types, and some may not be as obvi­ous. Let’s look at two more traits: Iter­a­tor, and Deref, and specif­i­cally why they have asso­ci­ated types.

Iter­a­tors: Even if you don’t use iter­a­tors explic­itly, for and while loops are syn­tac­tic sugar for iter­a­tor-based code. Need­less to say they’re used quite a bit. Below is the trait def­i­n­i­tion for Iter­a­tor. Read it and ask your­self, why is Item an asso­ci­ated type?

pub trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}

Iter­a­tors have only one type para­me­ter, Self, the type imple­ment­ing the iter­a­tor. For all of the types that Self could be, each one has a sin­gle spe­cific type for Item. OK, not a table in this case, just a plain map. Again, we can write a table describ­ing the rela­tion­ship between Self and Item.

Item is an asso­ci­ated type because there exists a map­ping from Self types to Item types. If you’re new to Rust, you may be ask­ing “would it be wrong to make Item a type para­me­ter?” Just as with the Bad­Mul trait you could write a ver­sion with Item as a type para­me­ter, here’s a play­ground link, but would affect type infer­ence neg­a­tively. The con­cept of asso­ci­ated types may be tricky to grasp espe­cially if you come from an object-ori­ented lan­guage where the item type is usu­ally a type para­me­ter. For exam­ple the Java iter­a­tor inter­face.

How­ever, as the old say­ing goes, “just because Java does it, doesn’t mean you have to.” As we saw with the Bad­Mul trait, if Item were a type para­me­ter, Rust type infer­ence would not work as well. I will go as far as to assert that iter­a­tors and related crates, like iter­tools, would not be as ergonomic and require devel­op­ers to insert lots of type anno­ta­tions. Let’s take a quick detour and look at a small dif­fer­ence between Rust’s and Java’s type sys­tems, and ask, how does Java get away with this design deci­sion?

What Java does that you shouldn’t

So that every­one is on the same page, below is the def­i­n­i­tion for the Java Iter­a­tor inter­face.

public interface Iterator<Item> {
  // Returns `true` if the iteration has more elements.
  boolean hasNext();

  // Returns the next element in the iteration.
  // @throws `NoSuchElementException` if the iteration has no more elements
  E next();
}

In Rust the type of iter­a­tor ele­ments Item is an asso­ci­ated type and I want you to under­stand why that needs to be the case in Rust while Java gets away with using a type para­me­ter. A naïve response might be that Java doesn’t have type infer­ence for vari­able assign­ments. His­tor­i­cally this was true, but Java 10 intro­duced the var bind­ing that enables local infer­ence. For exam­ple, cre­at­ing a vec­tor and iter­at­ing over the con­tents is shown below in Rust and Java.

// create a vector with two zeros
let v = vec![0; 2];
// iterate over the vector and print the contents
for i in &v {
  println!("{i}");
}

// create a vector with two zeros
var v = new Vector<>() {{ add(0); add(0); }};
// iterate over the vector and print the contents
for (var i : v) {
  System.out.println(i);
}

Each code snip­pet behaves the same and nei­ther spec­i­fies the type of the iter­ated ele­ments. So the real rea­son can’t be for mere type infer­ence. The real rea­son is that Rust’s type sys­tem affects how the code runs in a deeper way than Java’s. And it all boils down to the fact that Java has a run­time sys­tem, the Java Vir­tual Machine (JVM).

The main goal of the Java type sys­tem is to make sure noth­ing will go wrong at run­time. In this con­text, let’s define “go wrong” as call­ing a method on an object that the object doesn’t have. For the small code snip­pet iter­at­ing over a vec­tor, Java needs to know just that Vec­tor imple­ments the inter­face Iter­a­tor. If it does, then the meth­ods for iter­at­ing will be found at run­time. It turns out that Vec­tor extends the class AbstractList, and through a chain of inher­i­tance Vec­tor inher­its the nec­es­sary imple­men­ta­tion for Iter­a­tor. Know­ing the exact meth­ods for the iter­a­tor isn’t what’s impor­tant, Java wants to know only that they exist, not what they are or where they live. This is also true of the Java Sys­tem.out.println func­tion, which is over­loaded to accom­mo­date dif­fer­ent types. In the above code the println(int i) over­load would be picked, but if the items were instead objects, println(Object o) would be called and run­time dis­patch would fig­ure out how to print the object—Java doesn’t sta­t­i­cally need to know the type.

Only car­ing about the exis­tence of a method at run­time dif­fers dras­ti­cally from Rust, the Rust com­piler needs to know the exact address of the func­tions to be called; there is no run­time to fig­ure this out. In the above code, here are some things Rust needs to know

• How to turn a &Vec<i32> into an iter­a­tor: using the trait sys­tem Rust knows it can call the trait method into_iter defined on the trait IntoI­t­er­a­tor for &Vec<T>. Thanks to the asso­ci­ated type in this trait, Item, Rust also knows that the ele­ments iter­ated over are of type &i32.
• How to print a &i32: Rust now knows that the type of i is &i32. Again using the trait sys­tem, the com­piler finds the fmt method of the Dis­play trait defined for i32.
• Rust also needs to know the size of the iter­ated ele­ments, check life­times, yada yada yada. We’ll ignore this.

All of these indi­vid­ual pieces of Rust’s type machin­ery are in place so that the com­piler can replace calls like into_iter and fmt with spe­cific func­tion addresses. Unlike Java, there is no run­time sys­tem that will find the meth­ods later. Rust needs to know now at com­pile time!

This is how Java can get away with using a type para­me­ter for iter­a­tor items, and why Rust devel­op­ers should learn how and when to prop­erly use asso­ci­ated types. Let’s return to the Rust stan­dard library and look at the last exam­ple, pointer deref­er­enc­ing.

Deref­er­ences: Pointer deref­er­enc­ing is a well-known oper­a­tion to sys­tems pro­gram­mers. If you’ve used a C-like lan­guage at some point, you’re acquainted with pointer deref­er­enc­ing and may have even deref­er­enced the null pointer. One fea­ture of Rust that you may be unfa­mil­iar with is called deref coer­cion. This means that Rust will auto­mat­i­cally insert deref­er­ence oper­a­tions where pos­si­ble. It’s the fea­ture that enables the fol­low­ing weird piece of code to type check.

use std::sync::Arc;
use std::rc::Rc;

fn takes_a_ref(x: &i32) { /* ... */ }

fn weird_func(y: &&&&&Box<Arc<Rc<&&&&&i32>>>) {
    takes_a_ref(y)
}

If you don’t like count­ing, there’s five ref­er­ences to the Box, and five inside the Rc to the inte­ger, for a total of thir­teen ref­er­ences. How­ever, when we call takes_a_ref(y) we don’t have to insert deref­er­ences, the com­piler does it for us. Et voilà, deref coer­cion in action! If you ever find your­self with thir­teen ref­er­ences to an inte­ger, please reeval­u­ate your life deci­sions that led you to that point. How is the com­piler able to do this with­out acci­den­tally screw­ing up our types? Let’s look at the trait def­i­n­i­tion Deref that defines how a type is deref­er­enced.

pub trait Deref {
    type Target;

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

// Example implementation for immutable references
impl<T> Deref for &T {
    type Target = T;

    // &&T -> &T
    fn deref(&self) -> &Self::Target {
        *self
    }
}

Observe that Tar­get, the result­ing type of the deref­er­ence, is an asso­ci­ated type. This is a very impor­tant design choice for the trait. With Tar­get as an asso­ci­ated type it is sta­t­i­cally guar­an­teed that a type always deref­er­ences to the same type. If Tar­get were instead a type para­me­ter, deref coer­cion could poten­tially insert deref­er­ences result­ing in code that doesn’t type check, due to ambigu­ous types like we saw with the Bad­Mul trait. Just like all the other traits we’ve looked at so far, we can write a table that describes the rela­tion­ship between the Self type and Tar­get.

Imple­ment­ing Deref is espe­cially help­ful for point­ers, or smart point­ers like Box and Arc. Imple­ment­ing Deref allows us pro­gramers to treat these types like point­ers and leaves the deref gym­nas­tics for the com­piler to insert.

Closing remarks

I’ve pro­vided a gen­eral rule-of-thumb to help you deter­mine when a type para­me­ter should be an asso­ci­ated type.

A type para­me­ter should be an asso­ci­ated type if for all imple­men­ta­tion blocks there exists a rela­tion­ship map­ping the other type para­me­ters to it. (I.e., you can cre­ate a table map­ping the other para­me­ters to the asso­ci­ated type, like we did for Mul.)

The impor­tant dif­fer­ence is that asso­ci­ated types can only be spec­i­fied once per imple­men­ta­tion, type para­me­ters can vary. This rela­tion­ship has impli­ca­tions on how behaves, pre­vi­ously we saw how mak­ing Out­put a type para­me­ter on the Bad­Mul trait would require us to write more anno­ta­tions—the com­piler couldn’t infer the type for us. There are other moti­vat­ing fac­tors behind asso­ci­ated types, spec­i­fied well in the RFC, I will sum­ma­rize a cou­ple here.

• Refac­tor­ing/Evo­lu­tion  You can add an asso­ci­ated type to an exist­ing trait with­out break­ing clients that don’t care about those types. You can’t add a type para­me­ter with­out break­ing all client code.
• Inputs/Out­puts  An input type para­me­ter is used to deter­mine which imple­men­ta­tion to use. Out­put types, or asso­ci­ated types, play no role in select­ing the imple­men­ta­tion.
• Infer­ence impli­ca­tions  Out­put types (asso­ci­ated types) can be used to resolve infer­ence types as soon as a match­ing imple­men­ta­tion is found. Input types can­not do the same. Even if there is a sin­gle match­ing imple­men­ta­tion block, type infer­ence can­not use an input type (type para­me­ter) to resolve infer­ence types. This restric­tion is required to ensure that a crate added in the future does not break exist­ing code. (This is called coher­ence.)

you want to read other’s writ­ing on asso­ci­ated types, con­sider the fol­low­ing:

• Pret­zel Ham­mer’s tour of the Rust stan­dard library.
• The Rust Book’s sec­tion on Advanced Traits.
• Users dis­cus­sion thread about type para­me­ters vs asso­ci­ated types.
• Asso­ci­ated types RFC

If you have ques­tions or would like to cor­rect this post, as always, my email is open.