Trait Constructors

In Rust we call the things that define ranges of values "type", u8 and Vec<f32> are types. The struct Vec<T> { ... } is sometimes called "type", but it is a "type constructor" instead. It has no defined values unless someone plugs a another type into it, which can be done after-the-fact.

Now, when I write:


trait Copy { }

I create a trait, and it defines specific behavior other types can implement. However, when I write


trait From<A> { ... }

trait Deref { type Target; }

why do we not call these "trait constructors"? Neither From nor Deref are complete, and both allow others to plug specific types into A or Target after-the-fact. Would I be wrong to argue that


impl From<u8> for Vec<u8> { }

impl From<u16> for Vec<u16> { }

impl Deref for Vec<u32> { type Target = u32; }

impl Deref for Vec<u64> { type Target = u64; }

is the implementation of 4 distinct traits for 4 distinct types?

[Edited my question slightly as I accidentally repeated two types]

I agree that this should be called a trait constructor, however

this is just a trait with an associated type.

Yes, those are 3 traits implemeted for 2 different types. The 3 traits are From<u8>, From<f32> and Deref and they are implemented for 2 types: Vec<u8> and Vec<f32>.

But Deref for Vec<u8> and Deref for Vec<f32> are incompatible on a "type" level, as in I could not pass an instance of one into a function / type parameter that expects the other; why would those be "the same trait"?

They are the same trait because they can both be passed to a function that accepts impl Deref. They are 2 types that both implement 1 trait.

As a concrete illustration of what @Kestrer posted, here's an example that illustrates that an associated type need not be used in a trait bound (while the trait is still exercised within the body).

Just as with the example above, you actually can, though you may be hard-pressed to find a situation where it's useful for Deref.

Isn't this just because the associated type is by default universally qualified? If I write

impl Deref for f32 {
    type Target = u8;
}

impl Deref for f64 {
    type Target = u16;
}

fn f(x: impl Deref<Target = u16>) {}

Then I can't call f anymore with f(0_f32), but only with f(0_f64), so I've written a function that requires a specific Deref to work. In particular f1 is the "associated type equivalent" of f2, as is g1 the one of g2:

fn f1(x: impl Deref<Target = u16>) {}

fn f2(x: impl From<u16>) {}

fn g1(x: impl Deref) {}

fn g2<T>(x: impl From<T>) {}

(The <T> in g2 is just slightly different surface syntax in my mind)

No, this is more like adding a where clause to the associated type

fn f(x: impl Deref<Target = u16>) {}

is the equivalent as:

fn f<D>(x: D) where D: Deref, <D as Deref>::Target = u16 {}

although equality constraints aren't supported yet

I'm on my phone, so I can't go into detail here with code examples etc.., but I want to point out that it makes sense to compare to the origin of Rust's traits, that is, the "type classes" in Haskell. What this comparison teaches us: The type that implements a trait and other type parameters of a trait are only superficially different; it is just Rust's trait syntax that makes them feel like they take different roles while in actuality they are quite similar.

What I mean is: compare something like A: From<B> with B: Into<A>; pretty similar right? In Haskell the feature that is similar to Rust trait parameters are "multi parameter type classes". Something like T: Ord would be spelled Ord T in Haskell, and if you translated something with a parameter like T: Add<S>, it would look like Add T S, so just one more parameter (so now there's "multiple parameters"). Regarding associated types, the oldest feature that allowed you do something similar in Haskell was "functional dependencies" where you could declare that one type class parameter depends on one or multiple other ones. E. g. if in Foo S T the parameter S depends on T (indicated by some syntax T -> S in the declaration), it means that implementations of the type class can't be such that there are two implementations with the same T but different S. So you can think of associated types as just another parameter that has the restriction that it must be uniquely determined by the other (ordinary) parameters and it has some special syntax to actually name/access the associated types in terms of the types it depends on.

TLDR, the qualitative difference between normal traits and ones with extra parameters or associated types is more like increasing the arity of the trait from 1 to 2 or 3 or higher, etc. This is like unary relations versus binary or ternary relations, etc. This is not such a stark difference as between types and type constructors, which is an arity difference of 0 versus >=1, or like the difference of a constant vs a function. So I don't think we should really call them anything different.

3 Likes

Yes, sorry, made an oopsie when writing that example, updated the types, should be 4 now.

Thanks for the detailed reply. I have to admit that I have some trouble following (maybe it's too early in the new year ...) and I don't know any Haskell. Asking differently, would you

  1. call From<A> and Deref ... "trait constructors"?
  2. say in the example above exist 2, 3 or 4 traits?

If you either said "no" nor "<4", what would you say is the critical point where my reasoning breaks down (apart from surface syntax)?

And maybe if I reformulate my point, "Deref { type T } is like From a type constructor, with the only (subsurface) difference how many times the constructor may be 'instantiated' per type, infinite vs. exactly 1".

You may find it informative to read RFC 195, which introduced associated types. It presents a notion of input and output type parameters, and examines the roles they play for inference and coherence. The section on constraining associated types is also relevant.

In terms of the RFC, you can call a function with a Deref bound (and Deref::Target not bound) because associated traits are output types (which cannot be used to determine the type which implements the trait), and not because the associated type is universally qualified. The associated type isn't taken into account when inferring the concrete type.

In contrast, your g2 function cannot be called without inferring the concrete type of T at the call site. T is an input type parameter. The difference goes beyond syntax.

f requires its trait bounds to be met, not a specific (implementer of) Deref. More than one implementation would work, not a specific one.

Let's alter your example a little to accommodate the orphan rule.

trait DerefLike {
    type Target;
}

impl DerefLike for f32 {
    type Target = u8;
}

impl DerefLike for f64 {
    type Target = u16;
}

impl<T> DerefLike for Vec<T> {
    type Target = T;
}

fn f0<T: DerefLike>(x: T) {}
fn f1<T: DerefLike<Target = u16>>(x: T) {}
fn f2<T: DerefLike + Copy>(x: T) {}

fn main() {
    let a = 0_f32;
    let b = 0_f64;
    let c = vec![0_u16];
}

f0 takes any of a, b, or c. f1 takes b or c. f2 takes a or b. The Target bound didn't change which traits were implemented, only which implementations met the bound. Same with the Copy bound.

I'm going to assume you meant trait constructor. In which case, couldn't you also say: "Display is like From<T> a trait constructor, with the only difference being how many times the constructor may be implemented per type, infinite vs. exact 1"?

I'm going to assume you meant trait constructor

Yes, sorry. Citing from that RFC (thanks, really interesting read) how would you interpret:

Type parameters to traits can either be "inputs" or "outputs":

Inputs. An "input" type parameter is used to determine which impl to use.

Outputs. An "output" type parameter is uniquely determined by the impl, but plays no role in selecting the impl.

which seems to suggest both T and Target are "the same kind of" parameters?

Also, what about dyn Trait? For example you can't write

fn ff0(x: &dyn DerefLike) {}

which suggests &dyn DerefLike is not a complete type (because, as I'd argue, DerefLike was not a complete trait), but instead you have to write

fn ff1(x: &dyn DerefLike<Target = u8>) {}

and provide that parameter for ff1 to compile. Even more, doesn't

fn ff2<T>(x: &dyn DerefLike<Target = T>) {}

suggest there is a 1-to-1 mapping from the type constructor &dyn DerefLike<Target = T> (constructing over T), to the "trait constructor" trait DerefLike { type Target; }, constructing over Target?

I'm accepting From<T> and Deref have different inference behavior, but in a world with slightly different Rust syntax they'd rather be written:

trait From<in T> { }

trait Deref<out Target> { }

with the caveat "there can only be one out per combination of in". All other things being the same, wouldn't it be obvious to call Deref a "trait constructor" then?

By the way, what I'm ultimately after is a minimum set of rules that most consistently (and practically) explain Rust's generics model, undisturbed by syntax or still unresolved implementation quirks. Most existing documentation I found is often not very precise and ignores large parts of the type / trait / impl machinery.

IMO that's just an incosistency, the compiler shouldn't allow only one of them. However allowing dyn DerefLike is probably a bit technically challenging, while not allowing T: DerefLike may be a bit limiting.

IMO that's just an incosistency, the compiler shouldn't allow only one of them. However allowing dyn DerefLike is probably a bit technically challenging

I'd say the compiler has no choice and must allow only one (unless we throw zero-cost abstractions overboard). If we extend DerefLike to

trait DerefLike {
    type Target;

    fn f(&self) -> Self::Target;
}

then ff0 can't be compiled to a singular function. In an actual

fn ff0(x: &dyn DerefLike) {
    let tmp = x.f();
}

how many bytes should allocated for tmp otherwise?

In that case the compiler could just ban calling trait methods where the associated type appears

I wouldn’t use the term “trait constructor”, no. And I’m not sure I understand the second question correctly, but I’d say From is one trait and Deref is one trait.

Now that I have a keyboard at hand I can try to explain what I meant with my Haskell comparison, and I’ll try without using Haskell syntax but instead propose a modified Rust syntax that demonstrates my points.

Imagine Rust didn’t have trait objects and also didn’t have method syntax, so no self parameter or Self type for traits. Then let’s first consider normal traits, something without any additional arguments or associated types. Let’s use Default. Currently:

pub trait Default: Sized {
    fn default() -> Self;
}

Getting rid of the special Self type, I would like to make Self a parameter, let’s call it S to remind us it replaces the former Self. I could imagine a syntax like

// alternative syntax (not actual valid Rust code)
pub trait Default<S> {
    fn default() -> S;
}

Now that there’s no Self types with traits needed, the syntax Type: Trait doesn’t really make too much sense in my opinion anymore either, so I’ll write Trait<Type> instead. In Rust currently we can use Default to write generic functions such as this one:

fn default_vector<S: Default>(len: usize) -> Vec<S> {
    let mut result = Vec::with_capacity(len);
    for _ in 0..len {
        result.push(Default::default());
    }
    result
}

With my proposed syntax, this would need to be written as

// alternative syntax (not actual valid Rust code)
fn default_vector<S>(len: usize) -> Vec<S>
where
    Default<S>,
{
    let mut result = Vec::with_capacity(len);
    for _ in 0..len {
        result.push(Default::default());
    }
    result
}

And let’s also write an implementation:

// alternative syntax (not actual valid Rust code)
impl Default<i32> {
    fn default() -> i32 {
        0
    }
}

And a generic one:

// alternative syntax (not actual valid Rust code)
impl<T> Default<Vec<T>> {
    fn default() -> Vec<T> {
        Vec::new()
    }
}

Note that I’m only changing the syntax of "ordinary" traits here so far, the behavior is supposed to be the same as before. The reason to do this is to avoid the Haskell comparison; the syntax becomes more similar to Haskell here and Haskell doesn’t have method syntax, e.g. any notion of self parameters of Self in traits; and it doesn’t have Rust-style trait objects either.

Let’s rewrite some other trait to the new syntax, taking Clone since it is very simple, too:

trait Clone: Sized {
    fn clone(&self) -> Self;

    fn clone_from(&mut self, source: &Self) {
        *self = source.clone()
    }
}

becomes

// alternative syntax (not actual valid Rust code)
trait Clone<S> {
    fn clone(this: &S) -> S;

    fn clone_from(target: &mut S, source: &S) {
        *self = source.clone()
    }
}

as mentioned above, we give up self parameters and method syntax.


So with this new syntax, it suddently looks like simple traits like Default or Clone already have a parameter; yet I wouldn’t call them ..anything..-constructor because these are just the most basic form of traits. They are just traits. Well, let’s be more precise: in the new syntax, Default or Clone itself is (the name of) a trait, but what is Default<MyCustomType> or Clone<i32>? I would call those constraints, following Haskell terminology. I guess the Rust term for it, following the reference, might be something like bound.... well actually no: Rust says you can put things of the form Type: Bound in a where clause, the whole Type: Bound thing really have a name at all, AFAICT. The grammar just calls it TypeBoundWhereClauseItem.

So let’s revisit the comparison with types. Consider Vec, Vec<i32>, Clone and Clone<i32>.

  • Vec is a type constructor
  • Vec<i32> is a type
  • Clone is a trait
  • Clone<i32> is a constraint

where constraint means “that thing of which a comma separated list makes up the body of a where clause”

No reintroducing From:

trait From<T>: Sized {
    fn from(_: T) -> Self;
}

becomes .... well, we can choose either From<T, S> or From<S, T>. I’ll use the latter so that the constraint formerly written as S: From<T> becomes From<S, T>. Admitted, it reads a little weird now, being called “from”, but whatever.

// alternative syntax (not actual valid Rust code)
trait From<S, T> {
    fn from(_: T) -> S;
}

similarly e.g.

// alternative syntax (not actual valid Rust code)
trait AsRef<S, T> 
where
    ?Sized<S>,
    ?Sized<T>, 
{
    fn as_ref(this: &S) -> &T;
}

And a complicated example:

fn intricate_conversion<S, T, U>(x: &S) -> Vec<U>
where
    S: ?Sized + AsRef<[T]>,
    T: Clone,
    U: From<T>,
{
    x.as_ref().iter().cloned().map(From::from).collect()
}

becoming something like

// alternative syntax (not actual valid Rust code)
fn intricate_conversion<S, T, U>(x: &S) -> Vec<U>
where
    ?Sized<S>,
    AsRef<S, [T]>,
    Clone<T>,
    From<U, T>,
{
    As_ref::as_ref(&x).iter().cloned().map(From::from).collect()
}

Perhaps you can understand now why in Haskell the feature that corresponds to trait parameters are called “multiple parameter type classes”. The thing that distinguishes e.g. Clone from From above is that Clone only has a single parameter, while From has multiple parameters.

Let’s talk about associated types. We could turn

trait Deref {
    type Target: ?Sized;
    fn deref(&self) -> &Self::Target;
}

struct Foo(i32);

impl Deref for Foo {
    type Target = i32;
    fn deref(&self) -> &i32 {
        &self.0
    }
}

into something like

// alternative syntax (not actual valid Rust code)
trait Deref<S>
where
    ?Sized<S>,
{
    type Target
    where
        ?Sized<Deref<S>::Target>;
    fn deref(this: &S) -> &Deref<S>::Target;
}

struct Foo(i32);

impl Deref<Foo> {
    type Target = i32;
    fn deref(this: &Foo) -> &i32 {
        &this.0
    }
}

and keep an assosiated-types kind of feature in our hypothetical modified Rust syntax here. And probably work with them just fine. There’s actually a feature in Haskell too that is similar to this kind of syntax. But there’s also a way to “translate” them into a functionally very similar form by introducing so-called “functional dependencies” instead, which are, in my opinion, easier to understand. It would look like the following:

// alternative syntax (not actual valid Rust code)
// with functional dependencies
trait Deref<S, Target>, S -> Target
where
    ?Sized<S>,
    ?Sized<Target>,
{
    fn deref(this: &S) -> &Target;
}

struct Foo(i32);

impl Deref<Foo, i32> {
    fn deref(this: &Foo) -> &i32 {
        &this.0
    }
}

The S -> Target syntax introduces new rules in the coherence checker (the thing that checks whether there are any conflicting trait implementations in your code). It means that you cannot have multiple implementations of Deref that only differ in the Target parameter. E.g. having both Deref<Foo, Bar> and Deref<Foo, Baz> would be illegal. However having both Deref<Foo, Bar> and Deref<Qux, Baz> is totally fine. As is having both Deref<Foo, Bar> and Deref<Qux, Bar>.

Of course it would still be useful to have a way to get the Target when you only have an S, so we’d like to also have some way to materialize the functional depencency (FD), (btw. something that Haskell does not really support AFAIK)

// alternative syntax (not actual valid Rust code)
// with functional dependencies
type Deref_Target<S> = the <Target> in Deref<S, Target>
where
    exists<Target>: Deref<S, Target>;
// I know that where clauses on type aliases don’t really do
// anything in Rust, but I’d like to point out that in order
// to use Deref_Target<S>, we *do* need to make sure that
// there exists *some* implementation Deref<S, Target>
// for *some* Target

Then we can write Deref_Target<S>with FDs instead of the Deref<S>::Targetwith ATs that associated types (ATs) gave us. And Deref<S, Target = T>with ATs becomes Deref<S, T>with FDs , while Deref<S>with ATs would become Deref<S, Deref_Target<S>>with FDs . Comparing with usual Rust syntax, Deref_Target<S>with FDs is like <S as Deref>::Targetordinary Rust and Deref<S, Deref_Target<S>>with FDs is like S: Derefordinary Rust .

In the functional dependency version, an associated type just became onather parameter. Nothing more complicated than the multi-parameter traits that we already had, just some new special coherence rules.


Now let’s try to leave this alternate Rust version again and work our way back to the original one. The only thing that we need to do is give every alternative syntax-style trait an additional special parameter named Self that does not need to be introduced for in the trait declaration. Also, Self gets special syntax for constraints: E.g. we write Self: From<T> instead of From<Self, T>. And Self is a valid self-type for methods. Finally, we give this From<T> syntax a new name, a bound. A bound is pretty much a constraint where the Self parameter is still missing. From<T> is like From<_, T> with a hole, _, still to be filled. Writing SomeType: From<T> fill this whole with the parameter SomeType.


So as a conclustion, I would say I have the following view:

  • Default is a trait
  • From is a trait, too
  • Default has no additional parameters apart from the implicit Self parameter, hence Default itself is also a valid bound
  • From on its own is not a bound, however
  • From<T> is a bound, I would not call From<T> a trait though. From<T> has the explicit parameter of From filled in, while the implicit Self parameter is still missing.
  • S: Default is a constraint
  • S: From<T> is a constraint, too
  • multiple bounds can also be combined with +: Clone + From<T> is a bound, too. When used in a where clause, a constraint S: Clone + From<T> using this compound bound is just a special notation combining the two constraints S: Clone, S: From<T>
  • an associated type is very similar to a parameter, it comes however with some special syntax, and it funtionally depends on Self and the other non-associated-type parameters. This dependency is also manifested in that you can write e.g. <S as Deref>::Target to name the associated type in terms of the Self type and the explicit type parameters [Deref has no type parameters besides Self; something like <A as Add<B>>::Output better shows the general pattern].
  • associated type parameters always have to be written as named parameters, so you can’t write S: Deref<T>, but it needs to look like S: Deref<Target = T> instead. So then we have:
  • Deref is a trait
  • Deref<Target = T> is a bound and
  • S: Deref<Target = T> is a constraint
  • <S as Deref>::Target acts like a type alias, e.g. it is a special way of writing something like Deref_Target<S>in the previous section. <S as Deref>::Target is a valid type whenever we have a constraint S: Deref<Target = T0> for some/any T0
  • S: Deref could be considered just an abbreviation of S: Deref<Target = <S as Deref>::Target>
    • this is only meant as a theoretical possibility; note that the compiler currently does not like it if you actually write S: Deref<Target = <S as Deref>::Target> in a Rust program.
  • the constraint S: Deref<Target = T> feels like it gives rise to an equality constraint S::Target == T; i.e. an alternative view would be that S: Deref is the most basic form of constraint and S: Deref<Target = T> is just syntax sugar for S: Deref, <S as Deref>::Target == T. In the functional-dependency flavored interpretation where S: Deref<Target = T> is the most basic form of constraint and S: Deref is just syntactic sugar, this equality constraint does falls out of the functional dependency, in detail:
    1. (functional dependency) there can’t be two different T1 and T2 such that both S: Deref<Target = T1> and S: Deref<Target = T2>
    2. Since we have a S: Deref<Target = T>, we know that <S as Deref>::Target is a valid type, and by definition it is a type such that we have S: Deref<Target = <S as Deref>::Target>
    3. by the first point (1.), instantiating T1 == T and T2 == <S as Deref>::Target the types T and <S as Deref>::Target must be the same, because otherwise they would be two different types with both S: Deref<Target = T> and S: Deref<Target = <S as Deref>::Target>by (2.)

Please feel free to answer or message me about anything confusing that might be a typo — so far I’ve already found and corrected some mixup of “with FDs” vs “with ATs” annotations as well as an occasional use of the word “context” where I meant “constraint”.

9 Likes

Wow, thank you so much for the fantastic answer! I'll probably need to read it a few more times with a pen in my hand, but this sort of explanation is exactly what I hoped for (actually, it's much, much better than I hoped for!)

Ok, let me try to summarize in my words if I understood this correctly so far.

In my world, I assumed traits are "things you attach to types". As a picture I'd draw them like this:


u32
- Copy
- Clone
- From<u8>
- From<u16>

String
- Clone
- Deref { target = str }

Box<i32>
- Deref { target = i32 }

In that world each of the - xxx entries is a trait; and since, say, u32 has two different From attached these are two different traits (as are the two differing Deref implementations).

What you are saying is traits are not really "things attached", but rather "relations over types". Drawing your model, I would go


Copy   |   Self [I]  |
       | ----------- |
       |    u32      |
       |    i32      |
       |    char     |
       |    ...      |

From   |   Self [I]  |    T [I]      |
       | ----------- | ------------- |
       |    u32      |    u8         |
       |    u32      |    u16        |
       |    String   |    &str       |
       |    ...      |    ...        |

Deref  |   Self [I]  |    Target [O] |
       | ----------- | ------------- |
       |    String   |    str       |
       |    Box<i32> |    i32        |
       |    ...      |    ...        |

with Copy, From, Deref being relation tables, with the added property that all [O] types are dependent on [I] types, i.e., so that for a trait X with two I and one O it would hold I1 x I2 -> O. Then, depending on where exactly I encounter a From or Deref in code it can be the actual trait (when "representing the table"), or a bound / constraint when checking if certain entries are present.

Is that about correct so far?

The rest of your comment makes it clear that you understand the distinction between T being an input parameter and Target being an output parameter, so I don't understand what you mean by "same kind" here.

I'd be very wary of drawing any general conclusions about the relationship between types and traits from the relationship between trait objects and traits. The type-erasing and dynamically-sized nature of trait objects leads to a number of restrictions ("object safety") which don't apply to types generally.

E.g. &dyn Clone is not a valid type; is Clone not a trait?

Even restricting the consideration to trait objects and traits, the 1-to-1 mapping you highlight could be relaxed (as mentioned in the RFC). There would need to be special consideration of methods that take or return the associated type (just as there are special considerations of associated functions and methods involving Self today).

So you feel that the obvious conclusion of your alternative syntax is that Deref is a "trait constructor" and not a trait, but Deref<Target = a_type> is a trait. Then why isn't the obvious conclusion of the actual syntax that Deref is a trait and not a "trait constructor"?

Perhaps if I illustrate with code:

// Using either syntax
impl From<u8> for MyType { ... }
// This will error due to overlapping implementations
// "impl From<u8> for MyType" showed up twice
impl From<u8> for MyType { ... }

// Actual syntax
impl Deref for MyType { ... }
// This will error due to overlapping implementations
// "impl Deref for MyType" showed up twice
impl Deref for MyType { ... }

// Alternative syntax
impl Deref<Target = isize> for MyType { ... }
// This will error due to overlapping implementations
// But there was no duplication of "what was implemented"!
//    (i.e. what came between `impl` and `for`)
impl Deref<Target = usize> for MyType { ... }

I.e. I think the actual syntax is doing a good job here. Deref is the trait which you implement. The associated type is part of that implementation.

I don't think you're going to have any better results if you ignore the differences in implementation and inference.

Sounds great, yes.