Building more intuition for `MyType<T>` and `MyTrait<U>`

[EdmundsEcho]

I'm working on building a more fluid intuition for how to write more generic code in Rust And, getting a better feel for when to specify my own traits. For now, I'm limiting the scope to "generic over the type" not lifetimes, nor constants.

Traits - where I am

I first equated them to "type classes" in Haskell. Both type classes and traits have been explained with the idea of "an interface". As a way to express type bounds, type classes and traits relate to each other very well. Ad hoc polymorphism is also used to describe a "across" types capability. While I have seen credible sources describe traits "as types in Rust", it is more true with trait objects, and thus does introduce an ad hoc polymorphism.

However, traits are far more a "go to" in Rust, than type classes are in Haskell (type classes in general should be used for "canonical" properties shared across types, e.g., types that "commute", are "functors" etc.). Similarly, what I know about interfaces is incomplete for what traits do in Rust.

Concrete traits, concrete types, got it

I have put the idea of generic code with traits likely to go beyond the idea of the "base case" of using a concrete trait to augment my types with additional functionality. In concrete types and traits, it's straightforward enough.

Generic Types

The generic version of a type is also pretty clear in my mind: Option, Vec and the like are type constructors Vec: Type -> Type. I only use this terminology because it taps into a solid amount of FP concepts such as Functors, Monoids and the like. This level setting, is likely a boundary where a "trait"'s ability to augment my type's functionality likely stops. Specifically, a generic trait cannot make my concrete type a type constructor... or can it, just in a weird sort of way (Hash trait + concrete type)?

Generic traits

When I consider a generic trait, it gets fuzzy. So far, my model specifies how the type parameter can relate to self, the type that implements the trait and similarly how the two type parameters can relate when the type is also generic.

where I have GenericTrait<U> and GenericSruct<T>

1. "pass-through": T = U. Here the trait enhances whatever MyStruct in MyStruc<T> specifies (in other words, does not know of, nor can interact with T

   • this only works if I also consider traits with associated types as generic despite not having a type parameter. E.g., Vec<T> implements IntoIterator (generic by way of associated types)
     • here one specifies the other; 1:1

   ?? Is it possible to generically specify use of a concrete trait on a generic type??

2. is orthogonal to self: T != U and remains unaware of T (i.e., U cannot depend on bounds put on T) e.g., the [Hash](Hash in std::hash - Rust) and [Index](Index in std::ops - Rust) traits.

   • augment my type with a hash capability that can use whatever hash function "works best"

   ?? Is it possible to make a generic trait concrete by implementing a new trait, e.g., Trait Hash -> Trait HashWithThisHasher (so able to do so without implementing the trait for a given type).

3. interaction between T and U where U might depend on the traits implemented by T?

All in all, another way of expressing what I'm after here, is that in one extreme approach I could express my computation logic using nothing but traits + dummy struct. The only clear benefit of a struct is the ability to store data. Can all my methods be coded using traits? Where would this approach fall flat?

[alice]

To explain this, it may be useful to think about the "implements" relation. For each type/trait pair, either the type implements the trait, or it does not. When it does implement it, you can use the (type, trait) pair to look up the implementation, which gives you knowledge of anything inside the impl block (the methods, associated types, associated constants and so on). Notably, a type can only implement a given trait once.

How do generics come into the picture? Well, basically, you don't get a type until you've specified every single generic parameter. And you don't get a trait until you've specified every single generic parameter. So, Vec is not a type, but Vec<u8> is. Similarly, AsRef is not a trait, but AsRef<str> is. Once you've defined types and traits in this way, the explanation in the previous paragraph applies. A type such as Vec<u8> can choose to implement AsRef<str> or not. It can do this independently of the completely unrelated type Vec<String> or the completely unrelated trait AsRef<u8>.

Okay, maybe they're not completely unrelated. However, this is only true insofar as the ways in which the syntax for impl blocks limit you.

Understanding generic impl blocks is quite similar to generic structs or traits or methods. When something has a list of generic parameters, then you should duplicate that thing for every single possible combination of types that you can assign to the generic parameters, that satisfies the where clauses. So for example:

struct Vec<T> { ... }

is syntax-sugar to the infinite list:

struct Vec<u8> { ... }
struct Vec<String> { ... }
struct Vec<char> { ... }
struct Vec<TcpStream> { ... }
...

Similarly,

impl<T> AsRef<T> for Box<T> { ... }

is syntax-sugar for the following infinite list:

impl AsRef<u8> for Box<u8> { ... }
impl AsRef<String> for Box<String> { ... }
impl AsRef<char> for Box<String> { ... }
impl AsRef<TcpStream> for Box<TcpStream> { ... }
...

These duplications really are just "literally insert the type where it says T", nothing more, nothing less. You get "pass-through" when you use T on both sides. When you don't do that, you get orthogonal situations. When you use constructs like <T as Iterator>::Item on one side, then you get more complicated situations, since it expands to stuff like <Iter<'a, u8> as Iterator>::Item, which is long-hand for the type &'a u8.

As for associated types, they're different from generics. There's only one Iterator trait, and each implementation can make only one choice for what the Item associated type should be. The associated types are simply part of the information you look up when you look up the type/trait pair. This, combined with the fact that a type can only implement a trait once, is why expressions like <T as Iterator>::Item are meaningful. They perform a type/trait pair lookup and return the value of the associated type called Item.

Finally, as a note on lifetimes, they are completely like types here. The references &'a str and &'b str are different types when the lifetimes are different, and &str is not a type, but a type constructor that takes a lifetime and returns a type.

@EdmundsEcho

While I have seen credible sources describe traits "as types in Rust", it is more true with trait objects, and thus does introduce an ad hoc polymorphism.

Yes, I find this a misleading way to explain it. Traits are not types. Trait objects are types, but they're a different thing from the trait they're associated with.

[khimru]

@EdmundsEcho

Similarly, what I know about interfaces is incomplete for what traits do in Rust.

What that phrase even means? Interfaces work differently in different languages, but I would say Java interfaces come very close to the idea of Trait in Rust.

The big difference is that in Java you mix declaration of your type with declaration of the interface, but otherwise they are very close. Typeclasses in Haskell (which you already mentioned) come close, too.

I would say that traits are more of “types for types” or, maybe “interfaces for types”. And yes, they can turn your type into type maker. Like this:

struct VecMaker;
impl ContainerMaker for VecMaker {
    type Container<T> = Vec<T>;
    …
}

struct SetMaker;
impl ContainerMaker for SetMaker {
    type Container<T> = HashSet<T>;
    …
}

pub fn main() {
   let mut v = <VecMaker as ContainerMaker>::Container::<i32>::new();
   let mut s = <SetMaker as ContainerMaker>::Container::<i32>::new();
   …

Here v is vector and s is hashset but they are both created via SetMaker's Container type (and you can add function which would create new Container if you want).

As usual in such cases it's just really hard to understand what someone else doesn't understand. You obviously miss some important property of traits, but only you can discover what precisely you don't understand.

Traits were always very easy to me, except for trait objects (which are also pretty easy just incredibly limited… it's not that trait objects are hard to understand, rather they are hard to use because it's always a struggle for me to imagine how something like impl A for dyn B where Self: C is needed… isn't B a concrete type?), but that's both blessing and a curse: I've seen many people who struggle with them and helped them to understand them with examples and analogues, and people eventually “get them”… and then they couldn't even understand what was the problem they struggled with in the first place.

Traits are similar to Monads in some sense, except most people learn to use them easily even if they don't understand them fully.

[kpreid]

@EdmundsEcho

I first equated them to "type classes" in Haskell. … When I consider a generic trait, it gets fuzzy.

Traits with type parameters are more or less exactly equivalent to multi-parameter type classes in Haskell. That is the Rust code

trait AsRef<T> {...}

is analogous to the Haskell code

class AsRef s t where ...

The way in which they differ is that Rust has a distinguished Self parameter, which plays a special role in method lookup and trait objects. Other than those OOP-flavored things, Self and type parameters on a trait mostly act the same, despite being written very differently.

@EdmundsEcho

However, traits are far more a "go to" in Rust, than type classes are in Haskell (type classes in general should be used for "canonical" properties shared across types, e.g., types that "commute", are "functors" etc.).

I think that this should not really be considered a difference. Traits are about common properties shared across types. The fact that they are also used for things like “extension traits”, to add methods, is a distraction — it's another use of the same mechanism, but it's not the thing that justifies the existence of traits in Rust, or their design. (In fact, I think that much Rust code over-uses extension traits in the name of convenience. The method namespace is a risky thing to stuff new names into. It has only rarely bitten people — but it has.)

@EdmundsEcho

Specifically, a generic trait cannot make my concrete type a type constructor... or can it, just in a weird sort of way (Hash trait + concrete type)?

It cannot. The relationship of a trait to a type in this case is much like the relationship of a function to a type: just because a generic function takes a parameter of a certain type does not mean the type is any more generic. (Remember that all method calls are just syntax sugar for function calls, possibly generic ones.)

@EdmundsEcho

in one extreme approach I could express my computation logic using nothing but traits + dummy struct. The only clear benefit of a struct is the ability to store data. Can all my methods be coded using traits? Where would this approach fall flat?

You could indeed do that. It's just that the only reason to bother doing that is if you might want to have more than one trait implementation, where each one does something different. At that point, the struct type now means something (even if it has no data).

[EdmundsEcho]

@khimru

As usual in such cases it's just really hard to understand what someone else doesn't understand.

You are right. That said, part of learning is to figure out what questions to ask. For instance, going from one word processor to the next is mostly easy… because I know to ask “how do I copy/paste”.

Everyone’s comments thus far have been really helpful despite my at some level “not knowing what I don’t know”.

@khimru

Traits are similar to Monads in some sense

At first I thought “what are you talking about”?, but with imagination I can see a -> ma when I choose to augment my type a with a trait.

I will be reading over these responses (yours and others) again to take time to internalize them.

[khimru]

@EdmundsEcho

At first I thought “what are you talking about”?, but with imagination I can see a -> ma when I choose to augment my type a with a trait.

Sorry, was unclear. I was just implying that same trouble with Monads: people who “grok them” rarely can explain them to someone who don't “grok them”.

So many people who, after same struggles, “grok Monads” tried to write an explanation… and still people don't understand them.

It's also true that you can make Monads via use of traits in Rust (doesn't necessarily mean you should), but I wasn't talking about that.

[EdmundsEcho]

The information provided was very helpful. The collection of relations between type implements trait was grounding.

All in all, I've come to realize how the question of how generic parameters can be used prior to either the trait or type being made concrete (i.e., have the compiler generate/expand the implementation based on the concrete types "that meet the spec"), the ability to have them "interact", isn't possible in any meaningful way without the specialization feature (available with #![feature(specialization)]) is fully implemented. Even then, I suspect it will be limited without a mechanism to at least signal how certain mixes of trait bounds are mutually exclusive.

Quick note on the use of "generic": by definition of using traits, I am using a form of generic programming. My use of "concrete-trait" applies accordingly.

In order to implement types that depend on an interaction of type parameters, we need to be able to "admit" T with different, non-empty bounds for a given trait. That isn't possible.

// rust will expand this generic impl block
impl<T> Trait for T
    where T: TraitBound { ... }

// ok when MyType doesn't implement TraitBound
impl Trait for MyType { ... }

// not ok, overlap
impl<T> Trait for T
    where T: DifferentBound { ... }

The first impl block instructs Rust to create several implementations; one for each concrete type that implements TraitBound And for any type that can unify with T:TraitBound.

This latter clause effectively consumes the infinite list of possible unique entries in first impl block; leaving no "type space" for the third impl block. If each were able to expand, the entries would overlap on types T: TraitBound + DifferentBound; a type that "could be" and thus must be included in each of the expansions.

All in all, there is a gap between what a generic implementation requires to concretely implement the trait, and what is "admitted" (quantified); the theoretical ability to unify types is too greedy.

In my foggy understanding, when the "specialization" feature is implemented (allows overlap in certain circumstances), the ability to express "more specific" will work when comparing T with T: SomeTrait, with T: SomeTrait + OtherTrait, but still won't be able to resolve T: SomeTrait with T: OtherTrait. As long as the request to have Rust generate the entries where T:SomeTrait doesn't somehow exclude T:OtherTrait, Rust won't know what to do with T: SomeTrait + OtherTrait.

That said, I suspect the use of marker traits that flag, track and enforce "mutually exclusivity", may be useful. This seems possible given how the compiler can see how the following cannot unify and thus overlap:

impl<T> Foo for Box<T> { ... } // T: Sized
impl Foo for Box<dyn Trait> { ... }  // ...not so for Trait

Other places where I landed

A generic trait cannot make a type, a type constructor

@khimru posted an enticing example that might suggest otherwise. However, I've landed on the position that a concrete type cannot be made generic by implementing a generic trait. While traits can augment a type with the ability to instantiate generic types, Self remains concrete (per @kpreid's position).

@alice's reminder that &str is a type constructor that requires a lifetime parameter to make it concrete was a useful reminder as Rust will often elide the lifetime where the context permits.

Associated types ~ Functional dependencies

in multivariable type classes in Haskell

(also possible using type families)

In my search for "interaction", an associated type is more a "correlation" in that it is a single, concrete set of relations between types. When working with a generic type and a generic trait, I can generate the set of relations by "passing-through" the generic type parameter (equality relation between potentially different types). Per...

You get "pass-through" when you use T on both sides [of the "type implements trait" entry].

More generally (because the following does not require equality), it's @kpreid class AsRef s t | s -> t where ..., where s: Self, and t is the associated type. t varies with Self; Self determines t. It specifies a single "type implements trait" entry for every possible (infinite) number of entries for Self. To @alice's point:

is why expressions like <T as Iterator>::Item are meaningful. They perform a type/trait pair lookup and return the value of the associated type called Item.

Using associated types between traits

@alice

The associated types are simply part of the information you look up when you look up the type/trait pair.

... which I can use to align with other associated types or with parameters in generic traits.

// use the lookup info to set the associated type of a trait bound,
impl<T, U> Foo for T
    where T : Bar<Out=U> {
    type TraitOut = U;
}

// and/or use it to set align generic parameter values
impl<T, U> Trait<U> for T
   where 
      T: Bar<Out=U> {
   type TraitOut = U; 
   fn consume(&self, input: U) { ... }
   fn produce(&self) -> U { ... }
}

// and/or use it to set the bounds of an associated type
impl<T, U> Trait<U> for T
   where 
      T: Iterator,
      <T as Iterator>::Item: Trait<U> { ... }

and more with GATs...

Thank you to everyone for the replies that helped me frame how to develop my mental model here.

[jbe]

@khimru

It's also true that you can make Monads via use of traits in Rust (doesn't necessarily mean you should), but I wasn't talking about that.

Side note: I tried to create Monads (fmap). But Rust's type system poses some troubles, see:

• fmap Caveats
• some of my experimental code
• Playing with non_lifetime_binders
• Extra bound makes compiler fail recognizing types as equal
• Applicative functors: Compiler hangs when adding a bound

My conclusion (so far) is that Rust currently doesn't allow you to describe monads properly (at least not when you want to provide a generic API which accepts monads, which is the whole point of using these abstractions, right? – for the other cases, fmap seems to work well).

---

Edit: I just figured out that a hash-set isn't a functor in Haskell . So what I wrote above maybe isn't true, because if I don't attempt to implement functors/monads for these types with extra bounds (which I attempted with the fmap crate), things might be easier.