I have been waiting for this feature for forever! I am so excited to have it stabilize (hopefully doesn’t get reverted). This will cut down on so much boiler plate in traits and enable new design patterns. This moves us one step closer to true HKT’s.
I remember a Rust team member (perhaps several) saying that they don't want full higher kinded types in Rust, as GATs (I'm paraphrasing here) should give most of the functionality for a smaller footprint. I'm not sure how true that is though. What are some use cases in your view for HKTs?
Writing combinators that work generically over Fn/FnMut/FnOnce (for a very simple case, try writing the "compose" function - currently you have to write all three implementations separately even though they're identical).
Writing code that works polymorphically between sync and async - this solves the "function colouring" problem without having to give up precise control of where yields happen.
Writing data structure traversals (e.g. a tree walker/visitor) that can handle some kind of extra "context" in a generic way (e.g. updating a state, or making a database call, or indeed making an async call).
If they take the time and effort to build a consistent underlying model, yes (though I think the only proven way to do that would be to implement proper higher-kinded types and then turn keywords like async into syntax sugar for those). If they just add a bunch of ad-hoc cases for the keywords that are visibly causing problems then they'll probably make the issue worse rather than better. Given Rust's history of missed opportunities with this kind of thing (NLL, try/?, async), I'm not particularly hopeful.
You should write about this somewhere, or even on their GitHub RFCs, as it seems from what I've read that they don't want to have HKTs due to how it interacts with the borrow system (poorly, apparently) as it's not as easy as with Haskell or OCaml which are garbage collected.
They're aware, plenty of people have tried to convince them that full HKTs are what they need and they're wasting their time doing dozens of partial implementaions instead of biting the bullet and doing it properly. They've made their decision that they'd rather do partial incremental work, and I'm not even sure they're wrong (it could be that they'll need the experience of all these different partial approaches in order to figure out how to make their borrow system handle HKT safely). I just hope they'll find a way to migrate all this stuff onto a coherent foundation when they finally do implement full HKT.
HKT's ought to be relatively easy to implement as a pattern on top of GAT's, so in that sense the functionality is available. The only immediate drawback is a slightly more complex syntax than what most languages support for HKT's, i.e. you have to express what would be type families in other languages as associated type constructors in Rust. But this is for good reasons as Rust devs have found that associated types seem more idiomatic in the context of a somewhat lower-level language. Other than that, the features are really quite similar.
I'm under the impression that "true" HKTs are incompatible with monomorphization, which means they wouldn't ever happen with Rust. (However, I also don't quite understand why these two concepts are incompatible.)
Here is some history of GATs, from the original author of the RFC and how their sole purpose is to not have to add HKTs. From the collapsed discussion in the OP.
> There are a myriad of potential use cases for GATs. Stabilization unblocks probable future language features (e.g. async functions in traits), potential future standard library features (e.g. a LendingIterator or some form of Iterator with a lifetime generic), and a plethora of user use cases (some of which can be seen just by scrolling through the tracking issue and looking at all the issues linking to it).
There are other possible uses, but those two are ones a typical Rust developer may have already run into.
> Allow type constructors to be associated with traits. This is an incremental step toward a more general feature commonly called "higher-kinded types," which is often ranked highly as a requested feature by Rust users.
GATs are a really straightforward extension of what the language already has. All this means is that now a generic type can take a value as a parameter, for example there could be a generic fixed-length array, which took a length as a parameter. In the past libraries had to hack their way around this by having huge tables of types named like, "N1, N2... N16... N1003", which were passed to generic signatures to indicate to the type system how big something had to be.
I don't think this makes the language more confusing, because putting an integer inside of the generics brackets is something that previously you might try to do, if you didn't know it wasn't allowed. In fact, I would go so far as to say that this is a compiler feature, rather than a language feature, because it fills in a semantic hole that already existed in the way Rust programmers thought about Rust types. :-)
Note however broader Const Generics, allowing you to use your enumerated Hat type as a constant parameter to a type, producing PigInAHat<Hat::StrawBoater> as a distinct type from PigInAHat<Hat::Top> are not yet in stable Rust and aren't on the near horizon.
The idea is that any types which Rust can see for itself can be trivially compared for equality will eventually qualify for this purpose, so your Hat enumeration, or a structure with four integers and a boolean in it, or anything that Rust says "Yeah, I'll just memcmp that for equality" would qualify. No floating point numbers, no strings, nothing actually crazy. But this is in some undefined future, for now we just have min_const_generics which is basically the fundamental integral types as constants in generics.
It seems like a pattern for languages that try to be more pragmatic. Instead of a Big Idea, turtles-upon-turtles approach that would take years to finalize in a form that doesn’t invalidate everything that came before it, one goes for an initially good enough approach and then release more and more features which to the insider might seem very holistic but to an outsider (like me) just sound like Static Runtime-Bounded Polyhydral Lambda Cube Type Capabilities and Associates.
I recently refactored some traits that had a lot of repetitive noise in the generic type parameters (which end up being reflected in function signatures etc). I went about this without really being overly aware of GATs and their status, but the code that I naturally ended up with required enabling them.
So from my point of view, I didn't really need to understand what GATs were bringing - it's a lifting of restrictions that would have previously felt arbitrary.
Conceptually it's "just" the ability to take one existing concept, generics, and apply it to another existing concept, associated types. Under the hood there's a lot going on to make that work with the type system, and there's some advanced things that this now enables, but as far as a beginner is concerned this is less "a new feature" than "lifting a restriction on an existing feature".
By analogy, imagine a version of C where you can't use a struct as a member of a union. Then, a new version of C comes along letting you use structs in unions. We could call that a new feature, "struct-in-unions"... or we could just call it lifting a restriction on an existing feature. It's entirely natural to want to use structs with unions, and it's probably what a learner of the language intuitively expects should be possible. Likewise, a learner of Rust probably expects that any type can be used as an associated type, and before today that wasn't true, and after today that is true.
As opposed to creating completely different ways of doing things from the existing patterns?
The parent was echoing the common complaint (exclusively from people who don't actually use rust, in my experience) that rust is getting "too many features."
But as others in this thread has pointed out, features like GATs actually make the language simpler, because they're removing weird (and to a new user, unexpected) restrictions on existing features. This will then unblock removing other surprising restrictions, like the inability to use async functions in traits.
Rust takes the philosophy that it's better to do hard work in the compiler in order to make the language simpler and easier for users. That's what's happening here.
Try thinking of it less as a new abstraction and more of removing a restriction from a previous abstraction. It is pretty easy to run into a situation where you want them without even knowing what the concept of a GAT is.
Rust gets a lot of unfair criticism of "adding new stuff" when a lot of what is "added" is actually removing restrictions and making it where a developer has less to learn.
Generics being a form of a compiler only dependently typed lambda axis is still infinitely more complex than chaining product & coproduct (sum) data types.
Please elaborate? Keep in mind that Rust isn't about making the simplest or most expressive language possible. Rather, it's about pushing the envelope on what sort of expressiveness we can soundly get away with while still benefiting from mechanical sympathy given the current state-of-the-art of optimizing compilers (and, also, while not being so foreign as to cause C-style language programmers to run away screaming).
It's labeled "stable", but this seems to require a bit more understanding by implementers than simple composition to safely use, specifically the part about "where clauses [being] required when those bounds can be proven in the methods that construct the GAT or other associated types that use the GAT in the trait".
I have been learning Rust by writing some toy code over the weekends, and 9 out of 10 times when I hit a roadblock and went to my local Rust Users Group, the answer was "just wait for GAT". Turns out these patterns occur organically out of fairly mundane needs of abstraction (e.g. the now-infamous `LendingIterator`), and especially for me as a C++17/20 daily driver, _arbitrary_ limitations on expressivity.
Don't get me wrong --- Rust feels a lot more expressive than C++17/20 in the vast majority of areas, but for the rest maybe 10%, it's pothole land for stable Rust. Eliminating some of these potholes is a big win for Rust's adoption story.
Well you don't have to use it just because it is added, but it will allow library writers to provide more ergonomic interfaces. This specific type system feature allows for stuff that weren't possible before but make sense and you'd expect to be valid code that compiles:
the most common example is the lending iterator. Have a struct that owns a vector of data. Can you implement an iterator that can return a reference of each item when you call next()? Not without GATs, because each time you return from next() you're creating a new lifetime that doesn't exist in your trait definition.
That's why current standard library iterators are basically structs that own a reference to what you iterate. See the GAT RFC which explains this concept much better than I can:
This isn't so much the introduction of a new concept or abstraction as the removal of what feels like an artificial limitation. You should be able to use a generic in a trait in a type defined in that trait, and when you can't it feels broken.
What kind of ergonomic benefit would this bring to an average rust developer who doesn't go into the depth of rust traits/type systems and just use libraries made by other smart people to develop some web service backend?
Lending iterators is the most obvious. Also simplification for library maintainers, and the ability to better abstract over traits (leading to less boxing / dynamic dispatch).
So more flexible APIs and more efficient code for the consumer, and simpler library code (which is usually an improvement in reliability and maintainability).
In fact, it's one of the last features that will make it to 1.65 as the branch for 1.65 will soon branch off, and new changes on the master branch will only make it to 1.66.
Hi! Book author here. I think the other comments were answering when the feature will be available in a stable release. No content has been written for this, and it's not entirely clear to me yet how best to work this into the book.
The RFC is probably the best documentation for now.
So I have a question about GATs: since there was a lot of concern about the complexity cost they add, was it not possible to just define traits with generic params (instead of generic associated types, GATs) to achieve everything GATs could? To demonstrate, doesn't something like this work for lending iterators?
An immediate issue which could be addressed with further complexity is that for loop desugaring is done very early in Rust's compilation pipeline, way before typing is actually performed. This would also be weird in the case that you have a for loop over some generic iterator, the monomorphized code could vary quite a bit based on what trait your type implements.
As far as I can tell, this can't actually work, because the return type of `fn next(&'a mut self)` should actually live for some lifetime `'b` that is shorter than `'a`, instead of at least as long as `'a`; mostly because `next` borrows `self` mutably.
GATs (generic associated types) allow you to define type, lifetime, or const generics on associated types. If you're familiar with languages that have "higher-kinded types", then you could call GATs type constructors on traits.
58 comments
[ 2.7 ms ] story [ 124 ms ] threadWriting combinators that work generically over Fn/FnMut/FnOnce (for a very simple case, try writing the "compose" function - currently you have to write all three implementations separately even though they're identical).
Writing code that works polymorphically between sync and async - this solves the "function colouring" problem without having to give up precise control of where yields happen.
Writing data structure traversals (e.g. a tree walker/visitor) that can handle some kind of extra "context" in a generic way (e.g. updating a state, or making a database call, or indeed making an async call).
https://blog.rust-lang.org/inside-rust/2022/07/27/keyword-ge...
What happened with these? I'm out of the loop.
(This 2020 blogpost https://www.fpcomplete.com/blog/monads-gats-nightly-rust/ does a nice job of describing one such pattern, though their choice of Unwrapped and Wrapped<> as identifiers is overly obscure.)
https://github.com/rust-lang/rust/pull/96709#issuecomment-11...
There are other possible uses, but those two are ones a typical Rust developer may have already run into.
> Allow type constructors to be associated with traits. This is an incremental step toward a more general feature commonly called "higher-kinded types," which is often ranked highly as a requested feature by Rust users.
I don't think this makes the language more confusing, because putting an integer inside of the generics brackets is something that previously you might try to do, if you didn't know it wasn't allowed. In fact, I would go so far as to say that this is a compiler feature, rather than a language feature, because it fills in a semantic hole that already existed in the way Rust programmers thought about Rust types. :-)
min_const_generics have been on stable for while
The idea is that any types which Rust can see for itself can be trivially compared for equality will eventually qualify for this purpose, so your Hat enumeration, or a structure with four integers and a boolean in it, or anything that Rust says "Yeah, I'll just memcmp that for equality" would qualify. No floating point numbers, no strings, nothing actually crazy. But this is in some undefined future, for now we just have min_const_generics which is basically the fundamental integral types as constants in generics.
It seems like a pattern for languages that try to be more pragmatic. Instead of a Big Idea, turtles-upon-turtles approach that would take years to finalize in a form that doesn’t invalidate everything that came before it, one goes for an initially good enough approach and then release more and more features which to the insider might seem very holistic but to an outsider (like me) just sound like Static Runtime-Bounded Polyhydral Lambda Cube Type Capabilities and Associates.
So from my point of view, I didn't really need to understand what GATs were bringing - it's a lifting of restrictions that would have previously felt arbitrary.
By analogy, imagine a version of C where you can't use a struct as a member of a union. Then, a new version of C comes along letting you use structs in unions. We could call that a new feature, "struct-in-unions"... or we could just call it lifting a restriction on an existing feature. It's entirely natural to want to use structs with unions, and it's probably what a learner of the language intuitively expects should be possible. Likewise, a learner of Rust probably expects that any type can be used as an associated type, and before today that wasn't true, and after today that is true.
Yes, precisely. This is the literally what parent was talking about, "programming language abstractions [...] stacking on top of each other"
The parent was echoing the common complaint (exclusively from people who don't actually use rust, in my experience) that rust is getting "too many features."
But as others in this thread has pointed out, features like GATs actually make the language simpler, because they're removing weird (and to a new user, unexpected) restrictions on existing features. This will then unblock removing other surprising restrictions, like the inability to use async functions in traits.
Rust takes the philosophy that it's better to do hard work in the compiler in order to make the language simpler and easier for users. That's what's happening here.
Rust gets a lot of unfair criticism of "adding new stuff" when a lot of what is "added" is actually removing restrictions and making it where a developer has less to learn.
I have been learning Rust by writing some toy code over the weekends, and 9 out of 10 times when I hit a roadblock and went to my local Rust Users Group, the answer was "just wait for GAT". Turns out these patterns occur organically out of fairly mundane needs of abstraction (e.g. the now-infamous `LendingIterator`), and especially for me as a C++17/20 daily driver, _arbitrary_ limitations on expressivity.
Don't get me wrong --- Rust feels a lot more expressive than C++17/20 in the vast majority of areas, but for the rest maybe 10%, it's pothole land for stable Rust. Eliminating some of these potholes is a big win for Rust's adoption story.
the most common example is the lending iterator. Have a struct that owns a vector of data. Can you implement an iterator that can return a reference of each item when you call next()? Not without GATs, because each time you return from next() you're creating a new lifetime that doesn't exist in your trait definition.
That's why current standard library iterators are basically structs that own a reference to what you iterate. See the GAT RFC which explains this concept much better than I can:
https://github.com/rust-lang/rfcs/blob/master/text/1598-gene...
TL;DR it's not a "new" feature per se but something that could have been present from the beginning without making the language different.
So more flexible APIs and more efficient code for the consumer, and simpler library code (which is usually an improvement in reliability and maintainability).
https://github.com/rust-lang/rust/pull/96709#issuecomment-11... Has an extensive list of libraries wanting to use GATs, with their justifications.
https://rust-lang.github.io/rustup/concepts/channels.html
The RFC is probably the best documentation for now.
GATs (generic associated types) allow you to define type, lifetime, or const generics on associated types. If you're familiar with languages that have "higher-kinded types", then you could call GATs type constructors on traits.