Unsatisfied bound on associated type in generic trait method

help
1

Basically, I'm trying to make a simple nested tuple type in the vein of generic-array and am at an impasse (yes I know that if I wait long enough I will get type-level integers...also that chalk or proper GATs will probably fix these issues). Skip to the end for the specific error I'm stuck on and associated simplified code, otherwise I'll run through the actual code I'm trying to implement.

My main problem is figuring out how to implement a map method with minimal bounds needed from the user:

// convenience alias to make things more readable
pub type TupN<T, N> = <N as TupLen<T>>::Tuple;

// Trait for types representing *lengths* of tuples, in practice the types 
// would be from typenum, but for easier testing I'm just using a bunch of 
// empty tuples, e.g.
//   ()             => Tuple of length 0: ()
//   ((), ())       => Tuple of length 1: (T, ())
//   ((), ((), ())) => Tuple of length 2: (T, (T, ()))
//                  ...etc
pub trait TupLen<T> {
    // the variable length tuple associated with this length
    type Tuple;
    // length for a tuple shorter by 1 element
    type LenMinusOne: TupLen<T>;

    // the main thing I'd like to achieve is implementing this
    fn map<F, U>(tuple: TupN<T, Self>, f: F) -> TupN<U, Self>
    where
        F: FnMut(T) -> U,
        Self: TupLen<U>;
}

The obvious approach for the non-base-case implementation (aka length != 0, aka the only one giving problems), looks something like this:

impl<T, B> TupLen<T> for ((), B)
where
    B: TupLen<T>,
{
    type Tuple = (T, TupN<T, B>);
    type LenMinusOne = B;

    fn map<F, U>(tuple: TupN<T, Self>, mut f: F) -> TupN<U, Self>
    where
        F: FnMut(T) -> U,
        Self: TupLen<U>,
    {
        // gives a relatively misleading error unless we explicitly specify
        // all the types here
        (f(tuple.0), <B as TupLen<T>>::map::<F, U>(tuple.1, f))
    }
}

(Playground)

But results in a two errors. The first one has to do with rust not being able to figure out that the form of TupN<U, N> is the same as TupN<T, N> despite being inside of a blanket impl:

error[E0308]: mismatched types
  --> src/lib.rs:39:9
   |
32 |     fn map<F, U>(tuple: TupN<T, Self>, mut f: F) -> TupN<U, Self>
   |                                                     ------------- expected `<((), B) as TupLen<U>>::Tuple` because of return type
...
39 |         (f(tuple.0), <B as TupLen<T>>::map::<F, U>(tuple.1, f))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found tuple
   |
   = note: expected type `<((), B) as TupLen<U>>::Tuple`
              found type `(U, _)`

This one can be fixed by adding a helper trait, since if the U type is in the trait instead of the method, rust manages to figure out the blanket impl. Using the helper trait:

trait MapHelper<N, T, U>: FnMut(T) -> U
where
    N: TupLen<T> + TupLen<U>,
{
    fn apply(&mut self, tuple: TupN<T, N>) -> TupN<U, N>;
}

impl<F, T, U, B> MapHelper<((), B), T, U> for F
where
    Self: FnMut(T) -> U,
    B: TupLen<T> + TupLen<U>,
{
    fn apply(&mut self, tuple: TupN<T, ((), B)>) -> TupN<U, ((), B)> {
        (self(tuple.0), <B as TupLen<T>>::map(tuple.1, self))
    }
}

and updating the map function to use it, we get rid of the first error. (Playground)

Unfortunately the second one is still there:

error[E0277]: the trait bound `B: TupLen<U>` is not satisfied
  --> src/lib.rs:44:11
   |
44 |         f.apply(tuple)
   |           ^^^^^ the trait `TupLen<U>` is not implemented for `B`
   |
   = help: consider adding a `where B: TupLen<U>` bound
   = note: required because of the requirements on the impl of `MapHelper<((), B), T, U>` for `F`

This is despite the fact that there's clearly a bound of Self: TupLen<U>, which implies that Self::LenMinusOne: TupLen<U> (aka B).

I did try, among other things, to change the bounds on the helper trait to be ((), B): TupLen<T> + TupLen<U> instead of on B, but then rust forgets that we know what the associated type looks like
(Playground).

Simplified Code

I wanted to give the full context in case anyone had any ideas, but the distilled code to reproduce the current error looks like this:

pub trait Foo<T> {
    type Bar: Foo<T>;
    fn foo<U>() where Self: Foo<U>;
}

pub struct Baz<T>(T);
impl<T, N: Foo<T>> Foo<T> for Baz<N> {
    type Bar = N;

    fn foo<U>()
    where
        Self: Foo<U>,
    {
        <N as Foo<U>>::foo()
    }
}
// error[E0277]: the trait bound `N: Foo<U>` is not satisfied
//   --> src/lib.rs:17:9
//    |
// 17 |         <N as Foo<U>>::foo()
//    |         ^^^^^^^^^^^^^^^^^^ the trait `Foo<U>` is not implemented for `N`
//    |
//    = help: consider adding a `where N: Foo<U>` bound

(Playground)

Any ideas? or is this even possible for the current type system?

2

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