On the fingers: associated types in Rust and what is their difference from type arguments

Why does Rust have associated types, and what is the difference between them and type arguments aka generics, because they are so similar? Is it not enough just the latter, as in all normal languages? For those who are just starting to learn Rust, and especially for people who come from other languages ​​("This is generics!" - the javist, wise for years, will say), such a question arises regularly. Let's get it right.

TL; DR The former controls the called code, the latter the caller.

Generics vs associated types

So, we already have type arguments, or everyone’s favorite generics. It looks something like this:

trait Foo {
    fn bar(self, x: T);
}

This Tis precisely the type argument. It seems that this should be enough for everyone (like 640 kilobytes of memory). But in Rust, there are also associated types, something like this:

trait Foo {
    type Bar; // Это ассоциированный тип
    fn bar(self, x: Self::Bar);
}

At first glance, the same eggs, but from a different angle. Why did you need to introduce another entity into the language? (Which, by the way, was not in the early versions of the language.)

Type arguments are arguments , which means that they are passed to the trait at the place of the call, and the control over which type will be used instead Tbelongs to the caller. Even if we do not indicate explicitly at the place of the call T, the compiler will do this for us using type inference. That is, implicitly, anyway, this type will be inferred on the caller and passed as an argument. (Of course, all this happens during compilation, not in runtime.)

Consider an example. The standard library has a trait AsRefthat allows one type to pretend to be another type for a while, converting a link to itself into a link to something else. Simplified, this trait looks like this (in reality, it is a little more complicated, I intentionally removed everything unnecessary, leaving only the minimum necessary for understanding):

trait AsRef {
    fn as_ref(&self) -> &T;
}

Here the type is Tpassed by the caller as an argument, even if it happens implicitly (if the compiler infers this type for you). In other words, it is the caller who decides which new type Twill pretend to be our type that implements this trait:

let foo = Foo::new();
let bar: &Bar = foo.as_ref();

Here, the compiler, using knowledge bar: &Bar, will use the implementation to call the method , because it is the type that is required by the caller. It goes without saying that the type must implement the trait , and besides this, it can implement as many other options as you like , among which the caller selects the right one.AsRefas_ref()BarFooAsRefAsRef

In the case of the associated type, everything is exactly the opposite. The associated type is completely controlled by those who implement this trait, and not by the caller.

A common example is an iterator. Suppose we have a collection, and we want to get an iterator from it. What type of values ​​should the iterator return? Exactly the one contained in this collection! It is not up to the caller to decide what the iterator will return, and the iterator himself knows better what exactly he knows how to return. Here is the abbreviated code from the standard library:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option;
}

Note that the iterator does not have a type parameter that allows the caller to choose what the iterator should return. Instead, the type of the next()value returned from the method is determined by the iterator itself using the associated type, but it is not stuck with nails, i.e. each iterator implementation can choose its type.

Stop. So what? All the same, it is not clear why this is better than a generic. Imagine for a moment that we use the usual generic instead of the associated type. The trait of the iterator will then look something like this:

trait GenericIterator {
    fn next(&mut self) -> Option;
}

But now, firstly, the type Tneeds to be indicated again and again in every place where the iterator is mentioned, and secondly, now it has become possible to implement this trait several times with different types, which for the iterator looks somehow strange. Here is an example:

struct MyIterator;
impl GenericIterator for MyIterator {
    fn next(&mut self) -> Option { unimplemented!() }
}
impl GenericIterator for MyIterator {
    fn next(&mut self) -> Option { unimplemented!() }
}
fn test() {
    let mut iter = MyIterator;
    let lolwhat: Option<_> = iter.next(); // Error! Which impl of GenericIterator to use?
}

See the catch? We can’t just take and call iter.next()without squats - we need to let the compiler know, explicitly or implicitly, what type will be returned. And it looks awkward: why should we, on the call side, know (and tell the compiler!) The type that the iterator will return, while this iterator should know better what type it returns ?! And all because we were able to implement the trait GenericIteratortwice with a different parameter for the same thing MyIterator, which from the point of view of the semantics of the iterator also looks ridiculous: why is it that the same iterator can return values ​​of different types?

If we return to the variant with the associated type, then all these problems can be avoided:

struct MyIter;
impl Iterator for MyIter {
    type Item = String;
    fn next(&mut self) -> Option { unimplemented!() }
}
fn test() {
    let mut iter = MyIter;
    let value = iter.next();
}

Here, firstly, the compiler will correctly deduce the type without unnecessary words , and secondly, it will not work to implement the trait for the second time with a different type of return value, and thereby spoil everything.value: OptionIteratorMyIter

For fixing. A collection can implement such a trait in order to be able to turn itself into an iterator:

trait IntoIterator {
    type Item;
    type IntoIter: Iterator;
    fn into_iter(self) -> Self::IntoIter;
}

And again, here it is the collection that decides what iterator will be, namely: an iterator whose return type matches the type of elements in the collection itself, and no other.

More on the fingers

If the examples above are still incomprehensible, then here is an even less scientific but more intelligible explanation. Type arguments can be considered as “input” information that we provide for the trait to work. Associated types can be considered as "output" information that the trait provides us with so that we can use the results of its work.

The standard library has the ability to overload mathematical operators for its types (addition, subtraction, multiplication, division, and the like). To do this, you need to implement one of the corresponding traits from the standard library. Here, for example, how this trait looks for the addition operation (again, simplified):

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

Here we have an “input” argument RHS- this is the type to which we will apply the addition operation with our type. And there is an "output" argument Add::Output- this is the type that will result from the addition. In the general case, it can differ from the type of terms, which, in turn, can also be of different types (add tasty to the blue and get soft - but what, I do this all the time). The first is specified using the type argument, the second is specified using the associated type.

You can implement any number of additions with different types of the second argument, but each time there will be only one type of result, and it is determined by the implementation of this addition.

Let's try to implement this trait:

use std::ops::Add;
struct Foo(&'static str);
#[derive(PartialEq, Debug)]
struct Bar(&'static str, i32);
impl Add for Foo {
    type Output = Bar;
    fn add(self, rhs: i32) -> Bar {
        Bar(self.0, rhs)
    }
}
fn test() {
    let x = Foo("test");
    let y = x + 42; // Компилятор преобразует это в вызов ::add(42) для x
    assert_eq!(y, Bar("test", 42));
}

In this example, the type of the variable yis determined by the addition algorithm, not the calling code. It would be very strange if it were possible to write something like let y: Baz = x + 42, that is, force the addition operation to return the result of some extraneous type. It is precisely from such things that the associated type insures us Add::Output.

Total

We use generics where we do not mind having multiple trait implementations for the same type, and where it is acceptable to specify a specific implementation on the call side. We use associated types where we want to have one "canonical" implementation, which itself controls the types. Combine and mix in the right proportions, as in the last example.

Failed coin? Kill me with comments.