Generic struct over a generic type without type parameter

Question

Is it possible to do something like this in Rust?

trait Foo<T> {}

struct A;
struct B;

struct Bar<T: Foo> {
    a: T<A>,
    b: T<B>
}

I know I could just use two parameters for Bar, but I think there has to be a better way to do this.

I want to implement a Graph structure. As I can't just bind the nodes and edges to their parents lifetime, I want to have something like Rc. However, sometimes one may need a Graph with access from multiple threads. So I'd have to have both an implementation with Rc and Arc.

That's what Foo is good for: I implement Foo for both Rc and Arc (Foo would require Deref) and I use a parameter T bound to Foo. That's how I wanted to have one struct for single thread and multi thread usage.

Answer 1

You can use generic associated types (GATs) and the family pattern for that:

trait Family {
    type Container<T>;
}

struct A;
struct B;

struct Bar<T: Family> {
    a: T::Container<A>,
    b: T::Container<B>,
}

Then you can define two families:

struct BoxFamily;
impl Family for BoxFamily {
    type Container<T> = Box<T>;
}

struct VecFamily;
impl Family for VecFamily {
    type Container<T> = Vec<T>;
}

And use it:

let boxes: Bar<BoxFamily> = Bar {
    a: Box::new(A),
    b: Box::new(B),
};

let vecs: Bar<VecFamily> = Bar {
    a: vec![A, A],
    b: vec![B],
};

(Playground)

As you can see, it's slightly more involved than one would hope for: you can't just say Bar<Vec> for example, but have to go through the extra family type. But it works!

For an older answer (before GATs existed) containing more general information about the topic, click here.

Answer 2

In a way Rust does have what looks a lot like HKT (see Lukas's answer for a good description of what they are), though with some arguably awkward syntax.

First, you need to define the interface for the pointer type you want, which can be done using a generic trait. For example:

trait SharedPointer<T>: Clone {
    fn new(v: T) -> Self;
    // more, eg: fn get(&self) -> &T;
}

Plus a generic trait which defines an associated type which is the type you really want, which must implement your interface:

trait Param<T> {
    type Pointer: SharedPointer<T>;
}

Next, we implement that interface for the types we're interested in:

impl<T> SharedPointer<T> for Rc<T> {
    fn new(v: T) -> Self {
        Rc::new(v)
    }
}
impl<T> SharedPointer<T> for Arc<T> {
    fn new(v: T) -> Self {
        Arc::new(v)
    }
}

And define some dummy types which implement the Param trait above. This is the key part; we can have one type (RcParam) which implements Param<T> for any T, including being able to supply a type, which means we're simulating a higher-kinded type.

struct RcParam;
struct ArcParam;

impl<T> Param<T> for RcParam {
    type Pointer = Rc<T>;
}

impl<T> Param<T> for ArcParam {
    type Pointer = Arc<T>;
}

And finally we can use it:

struct A;
struct B;

struct Foo<P: Param<A> + Param<B>> {
    a: <P as Param<A>>::Pointer,
    b: <P as Param<B>>::Pointer,
}

impl<P: Param<A> + Param<B>> Foo<P> {
    fn new(a: A, b: B) -> Foo<P> {
        Foo {
            a: <P as Param<A>>::Pointer::new(a),
            b: <P as Param<B>>::Pointer::new(b),
        }
    }
}

fn main() {
    // Look ma, we're using a generic smart pointer type!
    let foo = Foo::<RcParam>::new(A, B);
    let afoo = Foo::<ArcParam>::new(A, B);
}

Playground