Making trait implementations transitive

1

Suppose I have something like this:

trait Extend<T> {
    const EXTRA: usize;
}

trait ExtendBase: Extend<Base> {}

Now I'd like to make Extend<Extend<Base>> have the trait Extend<Base> as well. E.g. for some functions I'd have to write

fn bla<T: ExtendBase, U: Extend<T> + ExtendBase>

whereas I'd prefer to write

fn bla<T: ExtendBase, U: Extend<T>>

because "naturally" something like this should work:

impl<T, U> ExtendBase for U
where
    T: ExtendBase,
    U: Extend<T>,
{const EXTRA = T::EXTRA + <U as Extend<T>>::EXTRA}

Is it possible to do something like this?

2

As written this is not possible because it's ambiguous. Imagine if some T implemented both Extend<A> and Extend<B> where A: ExtendBase and B: ExtendBase. Which of A and B should be picked for the transitive implementation?

3

Well, if you really, REALLY[1] want transitive trait implementations, you can introduce extra generic parameter to disambiguate the path.

Like this:

struct Base;

// Single step version
trait Extend<T> {
    const EXTRA: usize;
}

// Transitive version -- with the extra parameter to disambiguate path
trait ExtendBase<W> {
    const EXTRA: usize;
}

// Base case    
impl ExtendBase<()> for Base {
    const EXTRA: usize = 0;
}

// Inductive step case
impl<T, U, W> ExtendBase<(T, W)> for U
where
    U: Extend<T>,
    T: ExtendBase<W>,
{
    const EXTRA: usize = T::EXTRA + U::EXTRA;
}


// Example single step impls
impl Extend<Base> for u8 { const EXTRA: usize = 1; }
impl Extend<u8> for u16 { const EXTRA: usize = 2; }
impl Extend<u16> for u32 { const EXTRA: usize = 4; }
impl Extend<u32> for u64 { const EXTRA: usize = 8; }

fn bla<W, T: ExtendBase<W>, U: Extend<T>>() -> usize {
    // just an example to show that U: ExtendBase<_>
    <U as ExtendBase<_>>::EXTRA
}

#[test]
fn test() {
    assert_eq!(bla::<_, u32, u64>(), 15)
}

But there are limitations:

  • The extra parameter W will spread through everything similarly to lifetimes in structs
  • The inference of that parameter seems to be extremely fragile, so you may often need to add at least some type annotations (basically, the above example was fine-tuned not to need them)

... so if your overall goal is to simplify stuff, this is probably not the way ...

  1. one capslock is not enough, but that's all I've got ↩︎

4

I guess the concrete model I have in mind are finite sets, which you can make bigger and where EXTRA denotes the total number of elements added to the base set. In this case there would be no ambiguities - a set might indeed have two subsets which contain the base set, but EXTRA would not depend on this.

5

It would still be ambiguous (which subset do you pick for the construction?), it's just that it would not matter because the result would be the same in any case. However there's no way to write this proof in the type system, so the impl remain impossible.

1 Like
6

While that may be true in a mathematical sense, rustc is not a proof solver. You would need to prove that <T as Extend<U>>::EXTRA is equivalent for all T: Extend<U>, which would be nontrivial even if the compiler was "trying".

Note though that it is possible to model finite sets in the type system, but for that you would need to use structs as your sets, which transforms the impl you need from transitive to simply recursive. [1]

struct EmptySet;

struct Element<T, Set> (pub T, pub Set);

trait Set {
    const SIZE: usize;
}

impl Set for EmptySet {
    const SIZE: usize = 0;
}

impl<T, S: Set> Set for Element<T, S> {
    const SIZE: usize = S::SIZE + 1;
}

playground

Also note that the type system can be very flexible if you use it "correctly". It may be helpful if you describe a concrete use case, maybe we could find a model that better fits that.

  1. what I wrote up with here is an ordered multiset, normal sets are more complicated ↩︎