I think the easiest way to understand it is this:

Suppose you have a concrete type like

    Vec<i32>

Regular generics enable you to make the contained type generic, so you have:

    Vec<T>

where T can be i32, u32, String, etc. GATs allow you to make the container generic. So you can have:

    T<i32>

where T might be Vec, Option, Box, etc.

Thanks, this was much easier to understand than the original article. What will I use this for? Usually for the “T” to be useful it needs to have some interface. In Java I’d just use Collection<Integer> or something more abstract.

T keeps its type info statically. So if you put a Set in, you can get a Set out.

Casting to Collection loses the static type info, so you couldn't write foo(bar(set)) if bar returned a Collection but foo accepted a Set.

I forget what exactly a GADT is (even though I've used Haskell a bit before). But just going by the linked example from Reddit, you could make a generic `map` function that worked on any container type. You'd have to implement the map function separately for each type. But then you could make a bunch of utility functions that you'd implement once that use the generic `map` under the hood, and all of those container types would be able to use those utility functions.

Not a Rust guy but I think that's the idea.

Just so that we're clear on acronyms for everyone out there, "GADT" is a computer science term for "generalized algebraic data type", which has no relation to "GAT", which is just Rust terminology for generics in associated types (even in Rust, I doubt that anyone will bother to refer to "GAT" in the coming years, rather than just lumping them in with the concept of associated types in general; there's really no need to teach them separately).

> you could make a generic `map` function that worked on any container type.

not only container types, it can be any type that has a consistent context of evaluation for the final value being calculated: "doing async IO", "doing optional presence", "doing potentially erroneous extraction", and so on. In that sense, "doing multiplicity of values" is the context expressing a container type you mentioned as an example.

What you're describing sounds to me like higher kinded types, which are of some relationship to GATs (GATs enable a better encoding of higher kinded types as I understand it), but are not GATs. https://docs.rs/higher/latest/higher/

> as I understand it

You could be 100% right (I have no idea, but it sounds reasonable), but this entire question really hits home that Rust has tons of basically incomprehensible design features.

The worst part about features like this are that a few smart people will actually use them (whether because they're powerful features, or just because they feel powerful when using them), and then render their code incomprehensible to the mere mortals who have to support their code in the future.

The KISS principle (https://en.wikipedia.org//wiki/KISS_principle) is sometimes ignored because people don't want to be stupid, and why wouldn't you want to use a new toy(tool) once you've figured it out?

This is quite uncharitable. Rust's features aren't there for no reason, they're there to address the hard problems of how to achieve C++-level performance while providing the level of abstraction that modern developers expect and remaining totally type-safe.

Furthermore, the amount of hand-wringing over this feature is disproportionate to its actual impact. It feels like people see "Haskell" mentioned in the same breath and immediately lose all sense of reason. This feature is not basically incomprehensible, it's a straightforward addition that allows generics to be used with associated types, both of which are features that already exist in the language.

If you're asking yourself, "when would I ever need to use these?", this answer is that you may never find call to use these. Traits are mechanisms for creating abstractions, which are mostly relevant to library authors. If you're not a library author, you may never have a good reason to write a trait. Even for people who are writing traits, they may have no reason to ever use associated types. And even for people who are writing traits with associated types, they may have no reason to ever want to use generics with those associated types.

However, all of these features are extremely useful for the people consuming libraries, and far from making Rust code more complicated, from what I've seen so far it makes Rust code in the wild less complicated.

Things like GATs also allow those smart people to add sorely needed features, like async traits, which the rest of us plebeians can benefit greatly from

The problem is people who are smart enough to use fancy features, but not wise enough to show restraint.

The question is do we inhibit the wise to protect us from the unwise? The answer might be yes. I enjoy learning about power features so I hope not.

this sounds almost too easy to understand, will have to check with the documentation. (thank you!)

I think 90% of the reason why people have a hard time with GAT is because there aren't a ton of use cases. From what I can tell, GAT is quite simple - it is just like all other Rust generics except that now the generic can be in a new place.

Rust has made it years without needing this (granted, a few things have been less than ideal because of it) because, for the most part, people have not needed to reach for this type of abstraction. But it's really just "Generics in a new place".

Personally, I've accidentally written the GAT syntax years before I ever heard the term GAT because I thought a generic could go there.

It's needed for a lot of features people desperately want. Async functions in traits, closures that return futures where you need to run the future in a loop, and array indexing that doesn't necessarily return a reference, are three examples of things that essentially need GATs in order to be implemented without allocating. You may not feel like you missed it but not having that leads to a ton of ugly workarounds in Rust code. Also, in a lot of cases where people would otherwise use GATs, people instead work around them by making traits generic and have super complicated towers of generic types, you've probably seen interfaces like this when using hyper for instance. GATs would simplify most of those interfaces.

The vast majority of users do not desperately want async functions in traits, they just use async_trait and go "it'll be cool when GATs are done". Obviously there are use cases for GAT, what I'm saying is that they're going to be in very generic library code, which I don't think most users are writing.

For libraries like Hyper, which prioritize being extremely generic (it's split into a ton of reusable crates), which aims to serve as a very low level set of generic primitives for HTTP, yes it will come up.

Hyper is a great example of a use case that 99.99% of developers are not going to be able to relate to because they aren't building a set of completely generic http primitives. It's an important use case, it's just not relatable.

I know people who refuse to use async_trait for documentation reasons alone. The macro-based solutions aren't always pleasant to use and often come with a lot of weird tradeoffs. And yeah, I agree that most users don't need to write theme explicitly--I'm arguing that users are currently significantly impacted by the lack of them, even if they are never in a position where they'd consider writing them themselves, because it prevents library authors from writing precise APIs. For example, you might not be wanting to write GATs like the Hyper authors, but anyone using Hyper for anything nontrivial (and that's surprisingly common, IME) is certainly negatively impacted by the massive complexity caused by needing to work around their absence.

THIS is literally the best explanation. My god people have forgotten how to explain anything anymore. Thank you.

It is easy to understand because it is an oversimplification :)

Which part is inaccurate/incomplete?

The part that says `T<i32>`. GATs don't allow you to do that, not directly. GATs allow you, as said by Boats in https://news.ycombinator.com/item?id=33506540, have a generic type as an associated type, nothing less, nothing more. If you want to express `T<i32>`, GATs _enables_ you to do that as a kind of a distorted encoding, but it's not as simple as https://news.ycombinator.com/item?id=33505810 makes it seem.

Bring able to abstract over Rc/RefCell and Arc/Mutex with marker types seems pretty useful. It's not directly HKT but it enables use cases that would otherwise be supported by HKT.

Yes, but that doesn't make it somehow accurate to explain HKT and pretend you're explaining GAT...

That is definitely true.

The Associated bit of GAT I guess.

Awesome example.

Note that this isn't directly what GATs are, but you can use marker types to achieve this effect.

The ability to just use T for Vec, Box, etc, anywhere you might want to is "higher kinded types" - GATs only allow it specifically for "associated types" on a trait.

awesome and simple!!!

You mention that you use Rust. In that case, you're almost certainly familiar with generics, and you're likely familiar with associated types. If you've ever found yourself struggling to write an associated type that needed a generic parameter, this feature is for you. And if you haven't ever needed to do such a thing, that's totally fine, and you can happily ignore it and content yourself with benefiting from libraries that are now able to expose simpler and more powerful APIs by leveraging this feature under the hood.

I've yet to figure out why to use associated types instead of generic parameters, and every time I've seen an explanation I nod my head in confusion and carry on.

You can view generic parameters as "inputs", they are controlled by the consumer of the type/trait (you construct a `Vec<String>` because you want to store a bunch of `String` values).

Associated types are "outputs", they are controlled by the impl (`<Vec<String> as IntoIterator>::into_iter()` will always return a `std::vec::IntoIter<String>`, because that is how the trait is implemented for `Vec<T>`).

You can often use generic parameters for "outputs" as well (you could have a world where you had `impl<T> IntoIterator<IntoIter<T>> for Vec<T>`). However, this prevents the compiler from inferring the "output" type since there is no longer a guarantee that it is unique for a given set of "inputs".

You can generalize this:

A: type level functions from types to (associated) types (i.e. normal generics)

B: type level functions from types to type level functions (either As or Bs) (GAT).

with generic parameters (i.e. higher kinded types, or template template parameters in C++) you could have type level functions that map type functions to (types or type functions), but once you have GATs you can fake them by passing to first order functions a type that has an associated type.

Associated types serve much the same role as generic parameters in the context of traits, but with the crucial distinction that associated types are specified by the person implementing the trait for their type, whereas generic parameters are specified by the person calling the methods defined by the trait.

In practice you could basically just have generic parameters and not bother with associated types, but it would be much less nice to use these APIs.

Here's an example of how an API would change if Rust didn't have associated types:

    let x = [1,2,3]; // an array of i32
    let mut y = x.iter(); // an iterator over it
    y.next(); // pull an item from the iterator

If Rust didn't have associated types, then that last line would have to look like this:

    y.next::<&i32>(); // if Rust didn't have associated types

The Rust book has a pretty good explanation of the difference. https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

I appreciate the explanation. I've been more of a firmware or application developer in Rust than library developer, so will keep this in the hip pocket.

Yeah basically if the day comes when you need these, you will just naturally use them and it will work and you will never think anything of it.

Whereas I stumbled upon a use for these ~4 years ago and was just mad that what I naturally wanted to do didn't work =)

But yeah in certain programming domains, probably most, it just doesn't come up.

Yeah - it's almost better to think of GATs as less of a feature and more of a weird restriction being removed. That's obviously super reductive knowing the amount of work that went into it, but from an end developer standpoint, it's an explanation that helped make it make sense to me.

Same here. I presume that one day I will have to write something using a GAT, and then the understanding will click with me, even if I don't speak the terminology.

Both generics and traits are mostly for library authors trying to make expressive APIs. If you're not creating libraries but instead consuming libraries, then it may be natural for you to never need to reach for this feature.

Many C++ developers have walked that path, never to be seen again.

Yeah. I'd like to meet the 5-year-old that understood that.

edit: the "What are GATs" paragraph in the link posted by @leetrout is much more usable.

I can program in Scala and Haskell relatively easily. I still struggle with Rust's lifetime abstractions and things like this:

  impl<I, F> LendingIterator for Map<I, F>
  where
   I: LendingIterator,
   F: for<'a> Mapper<'a, <I::Item as GivesItem<'a>>::Item>,
  {
   type Item = dyn for<'this> GivesItem<
    'this,
    Item = <F as Mapper<'this, <I::Item as GivesItem<'this>>::Item>>::Output,
   >;

   fn next(&mut self) -> Option<<Self::Item as GivesItem<'_>>::Item> {
    self.iter.next().map(&mut self.mapper)
   }
  }

Haskell is so much easier.

I feel you, this is some particularly rough Rust code, combining quite a lot of stuff that I don't think I directly interacted with for my first few years.

You have `for<'a>`, which I believe is probably the most complicated part of the language. That's a Higher Ranked Trait Bound, https://doc.rust-lang.org/nomicon/hrtb.html

It just means "for all possible lifetimes 'a" as opposed to a single specific instance of a lifetime. Honestly, my brain kinda knows when to use it and I've never bothered to push past that point and into "and I understand why it knows when to use it".

You have nested types, which always makes things a bit messy, but then you have the "I have a type, it implements a trait, and I want to refer to the associated type for that trait's implementation for that type".

ie: <MyType as ATraitItImpls>::Associated

Oof. But once you know what it is it's quite clear and explicit. You wouldn't want to do `MyType::Associated` because what if MyType implements multiple traits that have associated values named Associated? Rust prefers explicit.

I actually use this all the time now because it makes refactoring so easy to only refer to types through generic paths. If I change "Associated" I don't have to update anything at all.

When you nest these it gets extra messy, but it's just the same thing. Mapper's second generic parameter is just the associated type of some other thingy. I wonder if some type Aliasing would help, idk.

Then there's `'_`, which I've never bothered to use because I learned rust before it was a thing and so I just don't really care. The irony is that `'_` exists to make things clearer - it's just an annotation that says "there's a lifetime here that we don't actually have to write down, but I'm writing it so that you know what it is and that it's not some other lifetime".

https://dev-doc.rust-lang.org/beta/edition-guide/rust-2018/o...

So yeah, I get it. Rust is very explicit, and when you have a lot of nested stuff like this that explicitness can look a bit overwhelming. But I'll say that, knowing all of this, I can look at that code and trivially parse it because there's no ambiguity whatsoever.

Interesting, thank you!

For me, I am totally OK with remembering and resolving ambiguities in context (both Haskell and Scala are heavy with these). But when everything is explicit and visible all at once, I am stuck, because of information overload (I have ADHD, so there’s that).

Maybe Rust is just not for me.

I still haven't fully figured out how lifetimes work.

I hope you don't. To establish my credentials for this comment - GATs were my idea.

The entire point of GATs was to carve out a design space that solved peoples' problems without being so high-minded as monads and HKT and so on. Unfortunately, a lot of people who like monads like to talk about GATs in the same way. But its really as simple as this: when you add an associated type to a trait, you can make that type generic, the same way you can make a type alias generic when its not in a trait. The whole point of specifying GATs and not a more general "HKT" is that it's an obvious extension of the existing language.

There are lots of useful traits that you can't define if you can't make an associated type generic, so people are excited to have this feature.

It turned out that implementing this in rustc took a very long time, because refactoring the typechecker of rustc to support this was challenging. But that doesn't mean the feature itself is complicated or difficult to use. The whole point of GATs is that it shouldn't really feel like a feature once it's done: naturally, if you are writing a trait with a method that returns `Self::Foo`, but you need it to be `Self::Foo<T>` or `Self::Foo<'a>`, you can just do that, rather than the compiler telling you that it's not supported.

Not trying to make you feel like you have failed, but whenever I encounter language features on this level - aka not comprehensible for a mortal like myself - I do tend to want to shamefully turn away from this profession entirely. The good news is that I am most likely a total dunce.

I wish I could become reasonable with rust because I do like the concepts that I think I grasp.

When I find a language feature I don't understand even after reading what's out there, I ignore it. Then I plod along with my own code. Eventually I'll notice I've been writing the same boilerplate code again and again, and I'll finally see the use for the feature. At that point it's less a matter of "understanding" in a grand intellectual sense, and more just fitting my needs to the syntax. After a few such instances, I know the feature well enough to unblock someone else who doesn't get it. That's a good practical test of understanding.

TL;DR: don't worry about it. When you need it, you'll learn it.

Indeed, when I was very first learning to code I did this with arrays! Couldn’t understand the advantage of writing foo[0] and foo[1] over foo0 and foo1. And in some cases there isn’t really one. But of course arrays are very useful in general.

GATs seem easily understandable to me and I'm a "mere mortal". Like most things in software, the utility becomes clear when you actually have a practical purpose for its use. Don't get ahead of yourself.

There are other people, who are also mere mortals, that can understand them. I think you could understand them if you tried. You're not a dunce!

You're begging the question when you say that GATs are "not comprehensible for a mortal like myself." My entire point is that they were designed not to be incomprehensible.

What is "not comprehensible for a mortal" in this situation is why adding a generic to an associated type is a long-anticipated feature that took years of development to support. This is related to the "incomprehensible" discussion that occurs around this feature, talking about type functions and higher kindedness and all of these mathematical formalisms. But this discussion is just happening among practitioners and enthusiasts schooled in a certain jargon and area of arcane knowledge. It doesn't mean you need to understand any of this to just use the feature.

It's like people saying the internet is "not comprehensible for a mortal like myself" because most people do not have the background to properly understand IP/TCP/HTTP and how things like this undergirdle the technology that they use. And yet they use the internet just fine. If the design has succeeded, you should not need to even hear words like "higher kindedness" before you can make your associated type generic.

Possibly the system design is imperfect and the abstractions leaks and you as a user have to learn more than one would hope in order to successfully use the tool to accomplish your goals. Rust doesn't have a perfect track record here.

> My entire point is that they were designed not to be incomprehensible.

It's frustrating that the documentation / announcement always seems to go for the most complicated way to explain just about everything, in what I assume is an attempt to ensure it's the most comprehensive explanation, in the smallest number of lines. It's fine to provide different levels of explanation/examples.

Numerous times I read stuff and think "Nope. Absolutely no idea why I'd use that, and I'm not entirely sure I have even half a clue what it's trying to do" until much much later when I see more simplistic practical applications of it and comprehension slowly dawns about what was being explained.

To be super clear I'm not trying to disparage you at all. I am just saying that I might not be cut out for understanding these complexities and ... honestly it deeply frustrates me, but I don't know how to overcome it.

Traits can have associated types.

    trait Foo {
        type Bar;
    }

Until now, those types had to be concrete, as in the above example. You can implement Foo with `Bar = u32` and `Bar = String` and even `Bar = Vec<bool>`.

    trait Foo {
        type Bar<T>;
    }

That `Bar` type above can now be generic over some other type `T` so you can implement it for `Bar<T> = Vec<T>`, `Bar<T> = Result<T>`, `Bar<T> = Option<T>`, and any other generic type. That's it. That's the whole thing. Use it if it's useful to you.

If you've never needed to write a trait that incorporated an associated type (.AT) which needed to be generic (G..), then this won't mean much to you and that's fine. But you might be using libraries that could be somewhat more ergonomic if they were able to use this feature. The good news is that now that it's been released to stable, a future version of that library can be written more ergonomically.

Is that what this is all about? I feel like the examples people give are nowhere near this simple.

Yep.

People are trying to show how you might use it in practice, which is useful. But I think people should start with the above.

If you’ve ever used associated types, this is the sort of thing you would probably expect would be possible even if you never needed to do it. Now it’s possible.

> The entire point of GATs was to carve out a design space that solved peoples' problems without being so high-minded as monads and HKT and so on.

High-minded or snobbish or whatever other deragotory words that one wants to use: the benefit of something like HKT is that it encompasses one thing that Rust now currently ends up catching up to by implementing dozens of “X with Y” (“generic const in associated lifetimes positions”… to use a made up feature) that are just about lifting limitations, and that end up sounding “complicated” and “featureful” (kitchen sink accusations) to anyone who isn’t knee deep in building an async runtime library or whatever.

Meanwhile a Haskell programmer might go years and never think about HKT as a feature. It’s just “kinds” without artificial-looking limitations.

Before writing a completely asinine comment like this, you might consider that I, having been paid real American dollars to design this language, might know more than you about the relationship between GATs and HKTs and the design of Rust as a whole. Your comment is completely stupid.

Fortunately, Niko Matsakis blogged about our design discussions at the time. You can read more here and in the linked predecessor posts https://smallcultfollowing.com/babysteps/blog/2016/11/04/ass...

Yes, your attitude (shall we say) was apparent from the start.

> Meanwhile a Haskell programmer might go years and never think about HKT as a feature. It’s just “kinds” without artificial-looking limitations.

And yet, at the same time, Haskell has many, many extensions to enable certain features that would come for free in a dependently typed language, for example. I find Idris's type system easier to fit in my head, for example.

There's always a next level of generality in which previously complicated concepts can be expressed more simply, but there are also sometimes reasons not to want to reach that level of abstraction, for various reasons.

(Although in principle, I agree. I don't find the concept of HKTs particularly complicated per se.)

> And yet, at the same time, Haskell has many, many extensions to enable certain features that would come for free in a dependently typed language, for example.

For sure.

In Rust’s case though it seemed that insiders were saying that HKT was more than the language needed, while now they keep running into limitations which necessitates patching up feature limitations. And patching up the language itself, not compiler extensions (maybe rustc is the only compiler that people use (?) but the updates are really to the language (in the abstract) itself).

But in any case, I’ve been told that I’m just talking out of my behind ;)

Wait. Why are Monads complicated? Yes the math definition is complicated, but so is math definition of number 1 in set theory

You have a Rust-like enum that contains data like Option or Maybe, you want to abstract over it. There you have a rudimentary Monad.

> you want to abstract over it.

What does that mean? Any example you could point to?

Are you familiar with flat_map? It's the ability to take, for example, an iterator, then map over each element which itself can return an iterator.

Similarly, you have Option::and_then, which takes a callback that takes T and returns an Option<T>. Or Result::and_then.

"Monad" is simply the umbrella term for all flat_maps, and things like it, in existence.

Why would you want to abstract over it? For one, it's a surprisingly common design pattern in programming. You also quickly notice, for example, that filter_map is actually just a special case of flat_map since Option implements Iterator.

You can also study the properties of how such patterns behave. Monads are particularly interesting for a number of reasons. Monads are a kind of "most general" and least constrained form of sequencing, and it turns out that if your large-scale system is monad-like it can have a significant performance impact!

You don't need to have a thing called "Monad" in your type system to do any of the above. Having a thing called "Monad" in your type system does let you write code that abstracts over all flat_maps (and things like it) in existence, which has been used in the Haskell world to build a number of interesting libraries. But "monads" as a concept are useful to everyone in programming.

By the way, as a simple example of what I mean when I say that monads are the least constrained form of sequencing: flat_map is strictly more general than map. In Rust, if an iterator I implements ExactSizeIterator, then Map<I, F> implements ExactSizeIterator:

https://doc.rust-lang.org/std/iter/struct.Map.html#impl-Exac...

However, there is no such implementation for FlatMap<I, F>:

https://doc.rust-lang.org/std/iter/struct.FlatMap.html

This intuitively makes sense! If a single input can generate zero, one or more than one outputs, then there's no way to know the exact size of it.

The simple map is more constrained -- it has to generate exactly one value -- which means that it can support more operations. The monad-like flat_map is less constrained, and it can do more, which means that it can't support as many operations. There's a catchphrase in the programming language community to describe this sort of thing: "constraints liberate, liberties constrain".

This can make a huge difference in production systems. For example, if you have a distributed system that walks over an execution graph, and nodes in the graph can create new nodes (flat_map/monad-like), the properties of your system are very different from if nodes can't do that.

No, monad is more complicated than that. There is a specific method that it has to have, which does not make sense on all types, and can also have more than one sensible definition for a type. "You want to abstract over it" gets you to a "trait", not a "monad".

As was noted at the beginning of the referenced explanation:

"I would offer a bit [of a] non-trivial example"

Which is to say, this comment is deliberately trying to go above and beyond the ELI5 request from the OP. You may find the answer below that one a bit easier to understand: https://old.reddit.com/r/rust/comments/ynvm8a/could_someone_...