Idea: Existential trait bounds

language design
1

I've run into a problem with unconstrained type parameters where it turns out that the unconstrained type parameter is never even used. Let's say we have code like this:

trait Trait {
    type Assoc: AssocTrait;
    // items
}

trait SuperTrait {
    fn super_fn() -> Self;
}

trait AssocTrait {
    fn assoc_fn() -> Self;
}

trait Hktrait<T>: SuperTrait { /* items */ }

struct Struct<A: AssocTrait, U> {
    a: A,
    u: U,
}

impl<T: Trait, U: Hktrait<T>> SuperTrait for Struct<T::Assoc, U>
where
    T::Assoc: AssocTrait
{
    fn super_fn() -> Self {
        Self {
            a: T::Assoc::assoc_fn(),
            u: U::super_fn(),
        }
    }
}

The type parameter T is unconstrained. If the same type U implements Hktrait<T> for two different types T, then the compiler would have to guess what T is, so RFC #447 was made to avoid that. However, in this case, T is never used. The implementation can almost be written as

impl<A: AssocTrait, U: Hktrait<T>> SuperTrait for Struct<A, U>
{
    fn super_fn() -> Self {
        Self {
            a: A::assoc_fn(),
            u: <U as SuperTrait>::super_fn(), // expanded for emphasis
        }
    }
}

After all, T::Assoc is just A, and U has just one implementation of SuperTrait no matter how many implementations it has of Hktrait<T> for different T. Unfortunately, there's still a pesky little T in the impl type parameters. If we could write something like

impl<A: AssocTrait, U: exists<T> Hktrait<T>> SuperTrait for Struct<A, U>
{
    fn super_fn() -> Self {
        Self {
            a: A::assoc_fn(),
            u: U::super_fn(),
        }
    }
}

and then enforce that the implementation cannot depend on T, that would solve the issue and even allow us to constrain U in Struct without a PhantomData:

struct Struct<A: AssocTrait, U: exists<T> Hktrait<T>> {
    a: A,
    u: U,
}

and then still be able to write an implementation of some other trait Hktrait2<T> for Struct<T::Assoc, U>.

However, the issue could just as well be solved by relaxing the bound on the implementation of SuperTrait to U: SuperTrait instead of U: Hktrait<T>. In addition, it introduces new syntax, and the logic for checking whether a type parameter satisfies an existential trait bound, especially if it satisfies another existential trait bound, would need to be figured out. So is this feature interesting and useful enough for an RFC?

For context, the problem was encountered in cgmath attempting to implement One for Decomposed. It turned out in that case that since Mul needed to be implemented too and that implementation depended on T, this wouldn't work in that case.

2

Seems like exactly what you’d want here.

I think your feature just doesn’t work. What would U: exists<T> Hktrait<T> offer you in a function definition? Sure, all the supertraits that don’t mention T anymore, but you could just write those supertraits instead then. Anything else? One could think, maybe methods of Hktrait that don’t mention T, but that won’t work since the implementation of those can still depend on the choice of T. One case that I think should work is when we have U: Hktrait<T> for all T, since then there’s the canonical choice of just using methods from the generic (over T) implementation (even in the presence of specialization), but I don’t think that was your intention in the example. Or, if U: Hktrait<T> is only implemented for a single T per U, you can make T an associated type.

Having talked about generic implementations, I think there is a case to be had for a feature allowing U: for<T> Hktrait<T>, especially for Fn-traits, where this would go hand in hand with support for generic closures.

3

About generic closures, I saw the RFC pull request for that, and it seems like it was blocked by not having HRTBs for types and a trait checking revamp. Would it be a good idea to write a draft about how U: for<T> Hktrait<T> should work?

4

I’ve wanted this a few times when defining supertraits. If I have a trait definition like this:

trait Trait {
    type Result;
    fn foo<T:OtherTrait>(&self, t:T)->Self::Result;
}

It would be nice to be able to lift the type parameter up to the trait level so that Result can be dependent on T and we have a trait that can be object-safe:

trait Trait: for<T:OtherTrait> Foo<T> {}
trait Foo<T:OtherTrait> {
    type Result;
    fn foo(&self, t:T)->Self::Result;
}
5

Or you could just use a blanket implementation

trait Trait {
    type Result;
    fn foo<T:OtherTrait>(this: &Self, t:T)->Self::Result // no `self` to avoid name conflict
    where Self: Sized; // if you don’t like this constraint, you could put `Result` into a common supertrait of `Trait` and `Foo`
}

trait Foo<T: OtherTrait>: Trait {
	fn foo(&self, t: T) -> Self::Result;
}

impl<T: OtherTrait, This: Trait> Foo<T> for This {
    fn foo(&self, t: T) -> Self::Result { Trait::foo(self, t) }
}

fn main() {
    let x: Box<dyn Foo<u8, Result = i32>> = todo!();
}

Also, in your second code example Result depends on T, while it doesn’t in the first example.

1 Like
6

That’s usually what I want, but I end up compromising that to ensure all Trait implementors can call foo with any of the valid arguments. The concrete case I ended up with was something like this:

trait Relation {
    type Row;
    type Ordered: Relation<Row=Self::Row>;
    fn order_by<SortKey: From<&Self::Row>+Ord>(self)->Self::Ordered;
}

This works, but I’d prefer to keep track of the sort order in the type system so that redundant sorts can be bypassed at compile time. That takes a backseat to ensuring that every Relation supports order_by on all relevant types, though.

7

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.