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.


Show source
| generics   | rust   | higher-kinded-types   2017-01-06 16:01 2 Answers

Answers ( 2 )

  1. 2017-01-06 16:01

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

    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".

    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:


    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.

  2. 2017-01-06 17:01

    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

◀ Go back