Polymorphic "implements" clause on associated types

[knz]

In a nutshell, let’s say I have a trait A<T> { ... }; then another trait B { type X; ... }. How can I state that type X in B always implements A for all T?

Something like trait B { type X : A<*>; ... } but this is not valid code.

I believe we miss an existential quantifier in associated type definitions (and possibly other places).

Advice from IRC suggested definining B with a parameter, ie. trait B<T> {type X : A<T>; ... } however this does not work as soon as some other items in B wish to exploit the genericity of X; for example:

trait A<T> { type O; ... }
trait B<T> {
    type X : A<T>;
    fn transform<U>(x : U) -> <X as A<U>>::O;
    //                       ^^^^
    // Error: X does not implement A<U>, only A<T>
} 

Were it possible to write the generic form this error would evaporate:

indent preformatted text by 4 spaces
trait A<T> { type O; ... }
trait B {
    type X : A<*>;
    fn transform<U>(x : U) -> <X as A<U>>::O;
    //                             ^^^^ OK
} 

I first submitted this as this issue on the bug tracker, which in turn illustrates an attempt to shoe-horn a reduced yet powerful form of HKTs in the current associated type machinery, inspired from this example from last year.

However do not let this mention of HKTs distract from the present discussion: even if HKTs are to be implemented using a different approach, I believe that existential implementation specifiers such as proposed above would still be useful. Meanwhile, if you are really interested in HKTs, notice that they would come for free as a by-product of the existential quantification described above.

[knz]

I just noticed the for keyword for existential quantifiers for lifetimes (see https://github.com/rust-lang/rfcs/pull/387) so the example above really is a call to implement the last part of https://github.com/nikomatsakis/rfcs/blob/hrtb/active/0000-higher-ranked-trait-bounds.md which would enable the following solution:

trait A<T> { ... }
trait B { type X : for<T> A<T>;  ... }
//                  ^^^  not currently valid, should perhaps become valid.

[stebalien]

You can always write:

trait A<T> { type O; ...}
trait B<T> {
    type X : A<T>;
    fn transform<U>(x : U) -> <Self::X as A<U>>::O where Self::X: A<U>;
}

However, this obviously doesn’t guarantee that B<T> is implemented for all T. You could also blanket impl B<T> for all T but that also doesn’t let the user assume that B<T> is implemented for all T:

trait A<T> { type O; ... }
trait B<T> {
    type X : A<T>;
    fn transform(x : T) -> <Self::X as A<T>>::O;
}

impl<T> B<T> for ... {}

[knz]

I have tried to do this but I run into issues if I need to encapsulate anonymous closures, see https://gist.github.com/knz/45a2987d1369dbdb0cc8 for details about the specific error. Unsure how to proceed.

[comex]

Looking at the first error, it makes sense because

fn pr<A>(x : A) -> <Self as Tr<A>>::O   where Self : Tr<A>;

is (obviously) conditional on Self implementing Tr<[the argument type]>; when called from foo, the argument type is a unique anonymous closure, while the bounds on foo have only guaranteed that it implements Tr<A> and Tr<B> for some A and B which are completely unknown, except for the fact that the function arguments match associated types on them.

In general, I don’t think it’s possible to have a generic function take a generic type as parameter and then specialize it with a type only known within that function (the closure type); someone could let me know if I’m wrong. You could solve this by implementing your closure manually, i.e. with a struct containing state and Fn implementation, allowing you to name the required Fn trait in the function bounds. Alternatively, you could just use boxed closures (which you are doing anyway when you cast id to &Fn(B)->B…).

And yeah, this is one reason HKTs would be nice.