Strategies for dealing with a recursive trait bound

I'm curious if there's a better strategy for dealing with a recursive trait bound when we need a bound on both a value as well as its reference. The following code will compile and run correctly:

// Create a trait with some methods
pub trait Foo1 {
    type Output;
    fn sqrt(self) -> Self::Output;
}

// Create a composite trait that potentially contains multiple traits
trait Buz<NonRef>:
    Foo1<Output = NonRef>
{}
impl<T, NonRef> Buz<NonRef> for T where T:
    Foo1<Output = NonRef>
{}

// Implement this trait for f32
impl Foo1 for f32 {
    type Output = f32;
    fn sqrt(self) -> Self::Output {
        self.sqrt()
    }
}
impl Foo1 for &f32 {
    type Output = f32;
    fn sqrt(self) -> Self::Output {
        <f32>::sqrt(*self)
    }
}

// Create a struct with a generic float inside
#[derive(Debug)]
struct Bar<Float> {
    x: Float,
}

// Lifts a variable into Bar
fn lift<Float>(x: Float) -> Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz <Float>,
{
        Bar { x }
}

// Implement to Foo1 trait for Bar
impl<Float> Foo1 for Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn sqrt(self) -> Self::Output {
        Bar {
            x: <Float>::sqrt(self.x),
        }
    }
}
impl<Float> Foo1 for &Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn sqrt(self) -> Self::Output {
        Bar {
            x: <&Float>::sqrt(&(self.x)),
        }
    }
}

// Create an element
fn main() {

    // Doesn't work
    //let bar = lift(4.0_f32).sqrt();
    // Works
    let bar = lift::<f32>(4.0_f32).sqrt();
    println!("{:?}", bar.x);
}

That said, in main, if we remove the fully qualified syntax let bar = lift::<f32>(4.0_f32).sqrt(); and replace it with let bar = lift(4.0_f32).sqrt(); we get the compiler error:

error[E0275]: overflow evaluating the requirement `&'a Bar<_>: Foo1`
 --> src/test02.rs:77:15
  |
39| fn lift<Float>(x: Float) -> Bar<Float>
  |    ----
...
42|     for<'a> &'a Float: Buz <Float>,
  |                        ----------- required by this bound in `lift`
...
77|     let bar = lift(4.0_f32).sqrt();
  |               ^^^^
  |
  = help: consider adding a `#![recursion_limit="256"]` attribute to your crate
  = note: required because of the requirements on the impl of `for<'a> Buz<Bar<_>>` for `&'a Bar<_>`
  = note: required because of the requirements on the impl of `Foo1` for `&'a Bar<Bar<_>>`
  = note: required because of the requirements on the impl of `for<'a> Buz<Bar<Bar<_>>>` for `&'a Bar<Bar<_>>`
  = note: required because of the requirements on the impl of `Foo1` for `&'a Bar<Bar<Bar<_>>>`
  = note: required because of the requirements on the impl of `for<'a> Buz<Bar<Bar<Bar<_>>>>` for `&'a Bar<Bar<Bar<_>>>`

I'm wondering whether there's a better way to handle this ambiguity other than using fully qualified syntax. Part of the reason I'm asking is that even though the situation here can be quickly resolved, I've a different code that requires a massive number of these annotations because the bound checker gets confused. I'd rather have something cleaner if possible.

Also, in case it's not clear from the context, the reason for the redundancy in the bounds

    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>

Is because I'd like to have the methods from the trait Buz be available to both the value of Float as well as its reference. I believe we need to pass in Float specifically here because we need the output type in Foo1 to be a non-reference. Since I don't know of a way to get a non-reference form of Self when Self itself is a reference, we pass in the non-reference version of the type directly.

Anyway, thanks for the help!

You give a one to many implementation where only a one to one can exist (compiler can't/doesn't deduce.)

impl<T> Buz<<T as Foo1>::Output> for T where T: Foo1 {}

Ah, nice! Thanks! Alright, so I tried to generalize the same thing to a piece of code that also contains binary methods. In this case, does a similar trick apply? For concreteness, consider a similar code:

// Create a trait with some methods
pub trait Foo1 {
    type Output;
    fn sqrt(self) -> Self::Output;
}
pub trait Foo2<Other> {
    type Output;
    fn min(self, other: Other) -> Self::Output;
}

// Create a composite trait that contain multiple traits
trait Buz<NonRef>:
    Foo1<Output = NonRef> +
    Foo2<NonRef,Output = NonRef> +
    for <'a> Foo2<&'a NonRef,Output = NonRef>
{}
impl<T> Buz<<T as Foo1>::Output> for T
where
    T:
        Foo1 +
        Foo2<<T as Foo1>::Output> +
        for <'a> Foo2<&'a <T as Foo1>::Output>
{}

// Implement this trait for f32
impl Foo1 for f32 {
    type Output = f32;
    fn sqrt(self) -> Self::Output {
        self.sqrt()
    }
}
impl Foo1 for &f32 {
    type Output = f32;
    fn sqrt(self) -> Self::Output {
        <f32>::sqrt(*self)
    }
}
impl Foo2<f32> for f32 {
    type Output = f32;
    fn min(self, other: f32) -> Self::Output {
        self.min(other)
    }
}
impl Foo2<f32> for &f32 {
    type Output = f32;
    fn min(self, other: f32) -> Self::Output {
        (*self).min(other)
    }
}
impl Foo2<&f32> for f32 {
    type Output = f32;
    fn min(self, other: &f32) -> Self::Output {
        self.min(*other)
    }
}
impl Foo2<&f32> for &f32 {
    type Output = f32;
    fn min(self, other: &f32) -> Self::Output {
        (*self).min(*other)
    }
}

// Create a struct with a generic float inside
#[derive(Debug)]
struct Bar<Float> {
    x: Float,
}

// Define a constructor
impl<Float> Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    fn new(x: Float) -> Bar<Float> {
        lift(x.sqrt())
    }
}

// Lifts a variable into Bar
fn lift<Float>(x: Float) -> Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz <Float>,
{
        Bar { x }
}

// Implement to Foo1 trait for Bar
impl<Float> Foo1 for Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn sqrt(self) -> Self::Output {
        Bar::<Float> {
            x: <Float>::sqrt(self.x),
        }
    }
}
impl<Float> Foo1 for &Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn sqrt(self) -> Self::Output {
        Bar::<Float> {
            x: <&Float>::sqrt(&(self.x)),
        }
    }
}
impl<Float> Foo2<Bar<Float>> for Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn min(self, other: Bar<Float>) -> Self::Output {
        Bar::<Float> {
            x: self.x.min(other.x),
        }
    }
}
impl<Float> Foo2<Bar<Float>> for &Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn min(self, other: Bar<Float>) -> Self::Output {
        Bar::<Float> {
            x: (&self.x).min(other.x),
        }
    }
}
impl<Float> Foo2<&Bar<Float>> for Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn min(self, other: &Bar<Float>) -> Self::Output {
        Bar::<Float> {
            x: self.x.min(&other.x),
        }
    }
}
impl<Float> Foo2<&Bar<Float>> for &Bar<Float>
where
    Float: Buz <Float>,
    for<'a> &'a Float: Buz<Float>
{
    type Output = Bar<Float>;
    fn min(self, other: &Bar<Float>) -> Self::Output {
        Bar::<Float> {
            x: (&self.x).min(&other.x),
        }
    }
}

// Create an element
fn main() {
    let bar = Bar::<f32>::new(16.0_f32).sqrt().min(
        Bar::<f32>::new(256.0_f32).sqrt());
    println!("{:?}", bar.x);
}

This generates the compiler error:

   Compiling rust_recursive_trait v0.1.0 (/home/josyoun/code/rust_recursive_trait)
error[E0271]: type mismatch resolving `for<'a> <T as Foo2<&'a <T as Foo1>::Output>>::Output == <T as Foo1>::Output`
 --> src/test05.rs:20:9
  |
20| impl<T> Buz<<T as Foo1>::Output> for T
  |         ^^^^^^^^^^^^^^^^^^^^^^^^ expected Foo2::Output, found Foo1::Output
  |
  = note: expected type `<T as Foo2<&<T as Foo1>::Output>>::Output`
             found type `<T as Foo1>::Output`

error[E0271]: type mismatch resolving `<T as Foo2<<T as Foo1>::Output>>::Output == <T as Foo1>::Output`
 --> src/test05.rs:20:9
  |
20| impl<T> Buz<<T as Foo1>::Output> for T
  |         ^^^^^^^^^^^^^^^^^^^^^^^^ expected Foo2::Output, found Foo1::Output
  |
  = note: expected type `<T as Foo2<<T as Foo1>::Output>>::Output`
             found type `<T as Foo1>::Output`

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0271`.
error: could not compile `rust_recursive_trait`.

Ok, taking the compiler's advice and switching the type, we generate a new error:

   Compiling rust_recursive_trait v0.1.0 (/home/josyoun/code/rust_recursive_trait)
error[E0271]: type mismatch resolving `<T as Foo1>::Output == <T as Foo2<<T as Foo1>::Output>>::Output`
 --> src/test05.rs:20:9
  |
20| impl<T> Buz<<T as Foo2<<T as Foo1>::Output>>::Output> for T
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected Foo1::Output, found Foo2::Output
  |
  = note: expected type `<T as Foo1>::Output`
             found type `<T as Foo2<<T as Foo1>::Output>>::Output`

error[E0277]: the trait bound `T: Foo2<<T as Foo2<<T as Foo1>::Output>>::Output>` is not satisfied
 --> src/test05.rs:20:9
  |
20| impl<T> Buz<<T as Foo2<<T as Foo1>::Output>>::Output> for T
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Foo2<<T as Foo2<<T as Foo1>::Output>>::Output>` is not implemented for `T`
  |
  = help: consider adding a `where T: Foo2<<T as Foo2<<T as Foo1>::Output>>::Output>` bound

error[E0277]: the trait bound `T: Foo2<&'a <T as Foo2<<T as Foo1>::Output>>::Output>` is not satisfied
 --> src/test05.rs:20:9
  |
20| impl<T> Buz<<T as Foo2<<T as Foo1>::Output>>::Output> for T
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Foo2<&'a <T as Foo2<<T as Foo1>::Output>>::Output>` is not implemented for `T`
  |
  = help: consider adding a `where T: Foo2<&'a <T as Foo2<<T as Foo1>::Output>>::Output>` bound

error: aborting due to 3 previous errors

As such, is there a reasonable fix?

By the way, in case the code seems arbitrary, I'm trying to encapsulate all combinations of reference and value types for a series of unary and binary functions. I'm trying to understand how to generate a trait that encapsulates these combinations.

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