Generic Associated Types (GAT) in Rust

GAT.md

"Higher-kinded types" is a vague term, conflating multiple language features under a single banner, which can be inaccurate.

As background, this RFC includes a brief overview of the notion of kinds and kindedness. Kinds are often called 'the type of a type,' the exact sort of unhelpful description that only makes sense to someone who already understands what is being explained. Instead, let's try to understand kinds by analogy to types.

In a well-typed language, every expression has a type. Many expressions have what are sometimes called 'base types,' types which are primitive to the language and which cannot be described in terms of other types. In Rust, the types bool, i64, usize, and char are all prominent examples of base types.

In contrast, there are types which are formed by arranging other types - functions are a good example of this. Consider this simple function:

fn not(x: bool) -> bool {
   !x
}

not has the type bool -> bool (my apologies for using a syntax different from Rust's). Note that this is different from the type of not(true), which is bool. This difference is important to understanding higher-kindedness.

In the analysis of kinds, all of these types - bool, char, bool -> bool and so on - have the kind type. Every type has the kind type.

However, type is a base kind, just as bool is a base type, and there are terms with more complex kinds, such as type -> type. An example of a term of this kind is Vec, which takes a type as a parameter and evaluates to a type. The difference between the kind of Vec and the kind of Vec<i32> (which is type) is analogous to the difference between the type of not and not(true). Note that Vec<T> has the kind type, just like Vec<i32>: even though T is a type parameter, Vec is still being applied to a type, just like not(x) still has the type bool even though x is a variable.

A relatively uncommon feature of Rust is that it has two base kinds, whereas many languages which deal with higher-kindedness only have the base kind type. The other base kind of Rust is the lifetime parameter. If you have a type like Foo<'a>, the kind of Foo is lifetime -> type.

Higher-kinded terms can take multiple arguments as well, of course. Result has the kind type, type -> type. Given vec::Iter<'a, T> vec::Iter has the kind lifetime, type -> type.

Terms of a higher kind are often called 'type operators'; the type operators which evaluate to a type are called 'type constructors'. There are other type operators which evaluate to other type operators, and there are even higher order type operators, which take type operators as their argument (so they have a kind like (type -> type) -> type).

See the full RFC document for more examples and rationale.

gat_lifetimes.rs

trait StreamingIterator {
    type Item<'a>;
    fn next(&mut self) -> Option<Self::Item>;
}

trait Foo {
    type Bar<'a, 'b>;
}

trait Baz {
    type Quux<'a>;
}

impl<T> Baz for T where T: Foo {
    type Quux<'a> = <T as Foo>::Bar<'a, 'static>;
}

fn foo<T: for<'a> StreamingIterator<Item<'a>=&'a [i32]>>(iter: T) { ... }

fn foo<T>(iter: T) where T: StreamingIterator, for<'a> T::Item<'a>: Display { ... }

gat_types.rs

trait PointerFamily {
    type Pointer<T>: Deref<Target = T>;
    fn new<T>(value: T) -> Self::Pointer<T>;
}

struct ArcFamily;

impl PointerFamily for ArcFamily {
    type Pointer<T> = Arc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Arc::new(value)
    }
}

struct RcFamily;

impl PointerFamily for RcFamily {
    type Pointer<T> = Rc<T>;
    fn new<T>(value: T) -> Self::Pointer<T> {
        Rc::new(value)
    }
}

struct Foo<P: PointerFamily> {
    bar: P::Pointer<String>,
}