Defining a trait which takes a higher-kinded type generic

Question

I'd like to define a trait in Rust which has a generic type parameter - say, BorrowedValue, at the trait level, and a lifetime parameter, say 'a at the level of its method. The complication is that the actual type for the method argument is the combination of these two, ie BorrowedValue<'a>. This is probably best illustrated in code:

// Constructs a borrowed value with a specific lifetime
trait ConstructI32AsBorrowed<'a>: 'a {
    fn construct(x: &'a i32) -> Self;
}

// A struct which implements this
#[derive(Debug)]
struct BorrowedI32<'a> {
    value: &'a i32
}
impl<'a> ConstructI32AsBorrowed<'a> for BorrowedI32<'a> {
    fn construct(value: &'a i32) -> Self { Self { value } }
}

// This is the important bit
// A trait which represents BorrowedValue as a String, say in some special way
// note that the type parameter BorrowedValue exists at the trait level, but the
// lifetime 'a exists at the method level
trait ShowBorrowedValue<BorrowedValue: std::fmt::Debug> {
    fn show_debug(&self, borrowed: BorrowedValue) -> String
    where BorrowedValue: for<'a> ConstructI32AsBorrowed<'a>;
}

// Define a simple struct which implements ShowBorrowedValue by capitalizing the debug outputs
struct ShowsI32InCapitals;
impl<BorrowedValue: std::fmt::Debug> ShowBorrowedValue<BorrowedValue> for ShowsI32InCapitals {
    fn show_debug(&self, borrowed: BorrowedValue) -> String
    where BorrowedValue: for<'a> ConstructI32AsBorrowed<'a>
    {
        format!("{:?}", borrowed).to_string().to_uppercase()
    }
}

pub fn main() {
    // We have a single instance of our struct
    let shows_i32_in_capitals = ShowsI32InCapitals;
    // But we want to apply it to two different borrowed values with two different lifetimes;
    // this checks that the `'a ` lifetime argument is not fixed at the level of the struct
    {
        let val_a = BorrowedI32::construct(&0_i32);
        shows_i32_in_capitals.show_debug(val_a);
    }
    {
        let val_b = BorrowedI32::construct(&1_i32);
        shows_i32_in_capitals.show_debug(val_b);
    }
}

What I'm trying to tell the borrow checker here is that when I initialize show_i32_in_capitals, I'm happy to fix the (higher-kinded) type BorrowedValue - that's not going to change. However, I don't want to fix the lifetime 'a here: I want that to be set whenever I call show_debug.

Currently the compiler gives this intriguing error:

error: implementation of `ConstructI32AsBorrowed` is not general enough
  --> src/main.rs:43:9
   |
43 |         shows_i32_in_capitals.show_debug(val_a);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `ConstructI32AsBorrowed` is not general enough
   |
   = note: `ConstructI32AsBorrowed<'0>` would have to be implemented for the type `BorrowedI32<'_>`, for any lifetime `'0`...
   = note: ...but `ConstructI32AsBorrowed<'1>` is actually implemented for the type `BorrowedI32<'1>`, for some specific lifetime `'1

which implies that somehow my lifetimes are not matching up correctly.

Answer 1

Rust doesn't have proper HKT (and probably never will), but they can be emulated with GATs (Generic Associated Types), even if inconveniently:

#[derive(Debug)]
struct BorrowedI32<'a> {
    value: &'a i32
}
impl<'a> BorrowedI32<'a> {
    fn construct(value: &'a i32) -> Self { Self { value } }
}

trait BorrowedTypeConstructor {
    type Borrowed<'a>;
}

struct BorrowedI32TypeConstructor;
impl BorrowedTypeConstructor for BorrowedI32TypeConstructor {
    type Borrowed<'a> = BorrowedI32<'a>;
}

trait ShowBorrowedValue<BorrowedCtor: BorrowedTypeConstructor>
where
    for<'a> BorrowedCtor::Borrowed<'a>: std::fmt::Debug,
{
    fn show_debug(&self, borrowed: BorrowedCtor::Borrowed<'_>) -> String;
}

struct ShowsI32InCapitals;
impl<BorrowedCtor: BorrowedTypeConstructor> ShowBorrowedValue<BorrowedCtor> for ShowsI32InCapitals
where
    for<'a> BorrowedCtor::Borrowed<'a>: std::fmt::Debug,
{
    fn show_debug(&self, borrowed: BorrowedCtor::Borrowed<'_>) -> String {
        format!("{:?}", borrowed).to_string().to_uppercase()
    }
}

pub fn main() {
    let shows_i32_in_capitals = ShowsI32InCapitals;

    {
        let val_a = BorrowedI32::construct(&0_i32);
        let s = <ShowsI32InCapitals as ShowBorrowedValue<BorrowedI32TypeConstructor>>::show_debug(&shows_i32_in_capitals, val_a);
        println!("{s}");
    }
    {
        let val_b = BorrowedI32::construct(&1_i32);
        let s = <ShowsI32InCapitals as ShowBorrowedValue<BorrowedI32TypeConstructor>>::show_debug(&shows_i32_in_capitals, val_b);
        println!("{s}");
    }
}

Answer 2

I am no expert on lifetimes in Rust, but after tinkering around, the following compiled for me:

trait ShowBorrowedValue<BorrowedValue: std::fmt::Debug> {
    fn show_debug<'a>(&'a self, borrowed: BorrowedValue) -> String
    where BorrowedValue: ConstructI32AsBorrowed<'a>;
}

// Define a simple struct which implements ShowBorrowedValue by capitalizing the debug outputs
struct ShowsI32InCapitals;
impl<BorrowedValue: std::fmt::Debug> ShowBorrowedValue<BorrowedValue> for ShowsI32InCapitals {
    fn show_debug<'a>(&self, borrowed: BorrowedValue) -> String
    where BorrowedValue: ConstructI32AsBorrowed<'a>
    {
        format!("{:?}", borrowed).to_string().to_uppercase()
    }
}

I believe the problem is, that &self in show_debug() must outlive the value borrowed in ConstructI32AsBorrowed<'a>, but for<'a> does not indicate that, since the implicit lifetime given to &self is not related to 'a.

Edit: See @Chayim's comment