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

⇒ This is currently impossible to express in Rust's type system ☹

Fortunately, it will be possible in the future thanks to "Generic Associated Types" as proposed in this RFC. You can track the status of implementation and stabilization in the corresponding tracking issue.

---

The important term here is "HKT" (higher kinded types). It's a feature of a type system which is not yet implemented in Rust. Haskell offers HKTs. In the C++ world HKTs are known as "template templates". The generic associated types mentioned above are also a form of HKTs.

But what are HKTs, really?

Let's start slowly: what is a simple type as we know it? Let's list some types: i32, bool, String. These are all types... you can have a value (variable) of these types. What about Vec<i32>? It's also a simple type! You can have a variable of type Vec<i32>, no problem!

We want to group these types together; we call this categorisation a "kind of a type". If we want to talk in a very abstract way (about types of types) we choose other words, kind in this case. There is even a notation for kinds of types. For our simple types from above, we say: the kind of those types is

*

Yes, just a star, very easy. The notation makes more sense later!

---

Let's search for types that are of a different kind than our simple types. Mutex<HashMap<Vec<i32>, String>>? Nope, it's fairly complex maybe, but it's still of kind * and we still can have a variable of that type.

What about Vec? Yes, we omitted the angle-brackets. Yes, this is indeed another kind of type! Can we have a variable of type Vec? No! A vector of what?!

This kind is donated as:

* -> *

This just says: give me a normal type (*) and I will return a normal type! Give a normal type i32 to this thing (Vec) and it will return a normal type Vec<i32>! It's also called a type constructor, because it is used to construct types. We can even go further:

* -> * -> *

This is a bit strange, because it has to do with currying and reads odd for a non-Haskell programmer. But it means: give me two types and I will return a type. Let's think about an example... Result! The Result type constructor will return a concrete type Result<A, B> after you provided two concrete types A and B.

The term higher kinded types just refers to all kinds of types which are not *, which are type constructors.

In your example

When you write struct Bar<T: Foo> you want T to be of the kind * -> *, meaning: you can give one type to T and receive a simple type. But as I said, this is not yet expressible in Rust. To use a similar syntax, one might imagine that this could work in the future:

// This does NOT WORK!
struct Bar<for<U> T> where T<U>: Foo {
    a: T<A>,
    b: T<B>,
}

The for<> syntax is borrowed from "higher-ranked trait bounds" (HRTB), which can be used today for abstracting over lifetimes (most commonly used with closures).

Links

In case you want to read more about this topic, here are some links:

• Niko Matsakis' great series of blog posts discussing one possible solution (associated type constructors) to the HKT problem
• The RFC proposing generic associated types (just a less scary name for "associated type constructors")
• HRTB explanation

---

Bonus: the solution to your problem in case associated type constructors will be implemented (I think, as there is no way to test)!

We have to take a detour in our implementation since the RFC wouldn't allow to pass Rc as a type parameter directly. It doesn't introduce HKTs directly, so to speak. But as Niko argues in his blog post, we can have the same flexibility and power as HKTs with associated type constructors by using so called "family traits".

/// This trait will be implemented for marker types, which serve as
/// kind of a proxy to get the real type.
trait RefCountedFamily {
    /// An associated type constructor. `Ptr` is a type constructor, because
    /// it is generic over another type (kind * -> *).
    type Ptr<T>;
}

struct RcFamily;
impl RefCountedFamily for RcFamily {
    /// In this implementation we say that the type constructor to construct
    /// the pointer type is `Rc`.
    type Ptr<T> = Rc<T>;
}

struct ArcFamily;
impl RefCountedFamily for ArcFamily {
    type Ptr<T> = Arc<T>;
}

struct Graph<P: RefCountedFamily> {
    // Here we use the type constructor to build our types
    nodes: P::Ptr<Node>,
    edges: P::Ptr<Edge>,
}

// Using the type is a bit awkward though:
type MultiThreadedGraph = Graph<ArcFamily>;

For more information, you should really read Niko's blog posts. Difficult topics explained well enough, that even I can understand them more or less!

EDIT: I just noticed that Niko actually used the Arc/Rc example in his blog post! I totally forgot that and thought of the code above myself... but maybe my subconscious still remembered, as I choose a few names exactly as Niko did. Anyway, here is his (probably way better) take on the issue.