Learn a little about generic association types (GAT)

Author: CrLF0710 / Post editor: Zhang Handong

What a long name! What is this?

Never mind. We’ll straighten things out from the beginning. Let’s review the syntax of Rust. What constitutes a Rust program? The answer is: item.

Each Rust program is a line, each one an entry. For example, if you write a constructor definition in main.rs, then you write an implementation definition that adds two methods to it, and then you write a main function. Those are the three entries in crate’s module entry.

With items out of the way, let’s talk about associated items. An associated entry is not an entry! The point is the word “connection”. What is connection? The effect is to use a special keyword called Self. This keyword is used to refer to the type just mentioned.

Associated items can be defined in two places, in curly braces for the attribute definition and in curly braces for the implementation definition.

There are three types of association items: association constant, association function, and association type (alias). They correspond to three types of entries: constants, functions, and types (aliases).

Give me an example!

#! [feature(generic_associated_types)] #! [allow(incomplete_features)] const A: usize = 42; fn b<T>() {} type C<T> = Vec<T>; trait X { const D: usize; fn e<T>(); type F<T>; // This is the new one! <T>} struct S; impl X for S { const D: usize = 42; fn e<T>() {} type F<T> = Vec<T>; }Copy the code

What’s the use of this?

Pretty useful, but only in certain situations. There are two classic use cases for generic association types in the Rust community, and we’ll try to introduce them first.

But before we get started, let’s go over generics one more time. The word generic in English is generic. What is a generic type? Simply put, it is the shortcoming of what parameter type to let the user fill in.

This, by the way, has been loosely translated as generic because many systems fill in parameters that are types. In Rust, it’s not just types that can be generic parameters. There are three types of generic parameters: type, lifetime, and constant.

Ok, let’s look at a concrete example of a generic type: Rc

, which is a generic type with a generic parameter. The generic type Rc is not a type. It is only a type that provides “arguments” to the generic parameter, such as Rc

.

What if I write a data structure that shares data, but I don’t know in advance whether the user wants me to use Rc or Arc here? The easiest way to do this is to code it twice, which sounds a little clunky, and it is, but it works. By the way, there are two libraries in Crates. IO: IM and IM-RC. The main difference is whether it uses Arc or RC. In fact, generic association types can solve this problem very well. Next, we will look at the first classic use case of generic association types: type family.

Task #1: Support type families with generic relational types

Now let’s make a “selector” that tells the compiler whether Rc

or Arc

is needed. The code looks like this:

trait PointerFamily {
    type PointerType<T>;
}

struct RcPointer;

impl PointerFamily for RcPointer {
    type PointerType<T> = Rc<T>;
}

struct ArcPointer;

impl PointerFamily for ArcPointer {
    type PointerType<T> = Arc<T>;
}
Copy the code

Pretty simple, you have two “selector” types that you can use to indicate whether you want to use Rc or Arc. Practical use:

struct MyDataStructure<PointerSel: PointerFamily> {
    data: PointerSel::PointerType<T>
}
Copy the code

Then you can use RcPointer or ArcPointer to select the actual data. With this feature, the two packages mentioned above can be combined into one package. Yeah.

Task #2: Implement stream processing iterators with generic relational types

The other problem is that Rust is specific to other languages and either doesn’t have this problem (Guldan: At what cost?). Or, give up treating the problem (ahem).

The problem is that you want to represent the dependencies between input values and between input values and output values on the API interface. Dependency is not an easy thing to express. Rust’s plan? In Rust, this man’s favorite little sign of survival ‘_ everyone’s seen it. It is responsible for representing this dependency correspondence on the API.

Let’s actually use this lifetime tag, the iterator feature of the library that you’ve all seen, which looks like this:

pub trait Iterator {
    type Item;

    pub fn next(&'_ mut self) -> Option<Self::Item>;
    // ...
}
Copy the code

It’s great, but there’s one small problem. The value of type Item is completely independent of the type of Iterator itself (Self). Why is that? Because you take a value from Iterator, the resulting temporary range (‘_ above) is the generic argument to the next correlation function. The defined Item is a separate association type, so how can it be used?

Most of the time this isn’t a problem, but for some library apis it’s not enough. For example, if you have an iterator that, in turn, hands the user temporary files, the user can close them at any time. You can use Iterator at this point without any problems. But if every time you generate a temporary file and load some data, the iterator will want you to be able to tell it that you’re done. This way it can delete temporary files, or not delete them at all, but simply reuse its storage space to save another file, which is ok.

So at this point we can design the API with generic relational types.

pub trait StreamingIterator {
    type Item<'a>;

    pub fn next(&'_ mut self) -> Option<Self::Item<'_>>;
    // ...
}
Copy the code

When implemented, you can actually make the type of Item a dependent type, such as a borrow, and the type system ensures that Item is no longer in use by the user until you call next or move the destructor. Yeah.

You’re too down-to-earth. Can you do something abstract? All right, from now on we’re not talking. Just to be clear, we’re still talking about simplifying things, like binders and predicate.

First let’s establish the relationship between the name of the generic type and the concrete type. It’s a mapping, of course.

Fn generic_type_mapping(_: GenericTypeCtor, _: Vec<GenericArg>) -> Type;Copy the code

For example, Vec

, Vec is the name of the generic type and its constructor, and

is the list of generic parameters, just one item. After this mapping, a Vec

is obtained.

Ok, and then trait, what is trait, trait is actually a mapping.

Fn trait_mapping(_: Type, _: Trait) -> Option<Vec<AssociateItem>>; fn trait_mapping(_: Type, _: Trait) -> Option<Vec<AssociateItem>>;Copy the code

Here, the Trait can act as a predicate, that is, it can be used to determine a type. The conclusion is either None, which means “does not match this Trait,” or Some(items), which means “this type matches this Trait,” and maps a list of associated items.

Enum AssociateItem {AssociateType(Name, Type), GenericAssociateType(Name, GenericTypeCtor), GenericFunction(Name, GenericFunc), AssociatedConst(Name, Const),}Copy the code

AssociateItem here: : GenericAssociateType is the only place where indirectly perform in the current rust generic_type_mapping place. You can retrieve a different GenericTypeCtor using the same Trait by passing a different Type to the first parameter of trait_mapping, and then generic_type_mapping. The purpose of Rust’s syntax framework is to combine different GenericTypectors with the specified Vec

.

GenericTypeCtor, by the way, is what some articles call HKT. Through the methodology described above, Rust incorporated HKT capabilities for user use for the first time. Although there is only one form, all other forms of use can be made from this form. All in all, strange abilities have increased!

Duckling and I are learning to walk, and to finish, we’re going to try to mimic some constructs in other languages in GAT.

#! [feature(generic_associated_types)] #! [allow(incomplete_features)] trait FunctorFamily { type Type<T>; fn fmap<T, U, F>(value: Self::Type<T>, f: F) -> Self::Type<U> where F: FnMut(T) -> U; } trait ApplicativeFamily: FunctorFamily { fn pure<T>(inner: T) -> Self::Type<T>; fn apply<T, U, F>(value: Self::Type<T>, f: Self::Type<F>) -> Self::Type<U> where F: FnMut(T) -> U; } trait MonadFamily: ApplicativeFamily { fn bind<T, U, F>(value: Self::Type<T>, f: F) -> Self::Type<U> where F: FnMut(T) -> Self::Type<U>; }Copy the code

Then we implement these types for a “selector” :

struct OptionType;

impl FunctorFamily for OptionType {
    type Type<T> = Option<T>;

    fn fmap<T, U, F>(value: Self::Type<T>, f: F) -> Self::Type<U>
    where
        F: FnMut(T) -> U,
    {
        value.map(f)
    }
}

impl ApplicativeFamily for OptionType {
    fn pure<T>(inner: T) -> Self::Type<T> {
        Some(inner)
    }

    fn apply<T, U, F>(value: Self::Type<T>, f: Self::Type<F>) -> Self::Type<U>
    where
        F: FnMut(T) -> U,
    {
        value.zip(f).map(|(v, mut f)| f(v))
    }
}

impl MonadFamily for OptionType {
    fn bind<T, U, F>(value: Self::Type<T>, f: F) -> Self::Type<U>
    where
        F: FnMut(T) -> Self::Type<U>,
    {
        value.and_then(f)
    }
}
Copy the code

Ok, then we can express the properties of Option as Functor, Applicative, Monad through the “selector” OptionType. What about it? Does it open up a million new possibilities?

Learn a little about generic association types (GAT)

Learn a little about generic association types (GAT)

Task #1: Support type families with generic relational types

Task #2: Implement stream processing iterators with generic relational types

Related Posts

Github’s 10 most interesting recent open source machine learning projects

Koa – the router new solutions

Linux from Bronze to Web – Step-by-step guide to building your own blog site