rusttraitshigher-kinded-types

Defining a trait which takes a higher-kinded type generic


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.


Solution

  • 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}");
        }
    }