#Instantiating circularly referential generics

10 messages · Page 1 of 1 (latest)

somber ledge
#

Hello! I've been working in rust for a decent while, but this is my first time trying to work with generics to this extent, and I've been running into some trouble.

I'm trying to write a generic graph data structure for a cs class. I have a couple structs that look smthg like this:

trait IVertex<E> {
    ...
}
trait IEdge<V> {
    ...
}
// `IVertex` and `IEdge` were given by the professor. They're not very idiomatic, but I can't change them

struct Vertex<E> {
    edges: Vec<E>,
}
impl<E> Vertex<E> {
    fn new(edges: Vec<E>) -> Self {
        Vertex { edges }
    }
}
impl<E> IVertex<E> for Vertex<E>
where
    E: IEdge<Vertex<E>>,
{
    ...
}

struct Edge<V> {
    destination: Weak<RefCell<V>>,
}
impl<V> Edge<V> {
    fn new(destination: Weak<RefCell<V>>) -> Self {
        Edge { destination }
    }
}
impl<V> IEdge<V> for Edge<V>
where
    V: IVertex<Edge<V>>,
{
    ...
}

I'm able to use them generically as inputs into functions like this:

fn some_function<V, E>(vertex1: V)
where
    V: IVertex<E>,
    E: IEdge<V>,
{
  ...
}

But whenever I try to actually use them the compiler insists on explicit type annotations indefinitely, making them impossible to instantiate:

fn main() {
    let vertex1: Vertex<Edge<Vertex<Edge<...>>>> = Vertex::new(Vec::new());
}

I know this would be possible by removing Edge entirely and just having Vertexs hold references to each other directly, but I can't change the interface.

I've also gotten it to work by changing Vertex and Edge to refer to each other specifically rather than referring to generic V and E, but that's not ideal since it inseparably links them when theoretically every Vertex could be compatible with any IEdge and every Edge could be compatible with any IVertex.

Is it possible to work with circularly referential generics like these?

winter roost
#

just have them refer to each other specifically

#

the design is kinda fucked to begin with so you shouldn’t worry about making your implementation perfect tbh

somber ledge
#

fair enough, lol

somber ledge
#

hmm, ig it would also work even if I only made 1 refer to the other specifically
So making edge refer to a specific vertex, but leaving vertex to reference a generic E

That makes it all the more strange that they would be impossible to use when both vertex and edge are generic

cyan timber
# somber ledge hmm, ig it would also work even if I only made 1 refer to the other specifically...

There are two general solutions.

The reasonable one is to do exactly what languages in which IVertex and IEdge would be idiomatic design do: don't be generic and use boxed dynamic dispatch instead:

struct Vertex {
  edges: Vec<Box<dyn IEdge<Vertex>>>,
}
struct Edge {
  destination: Weak<RefCell<dyn IVertex<Edge>>>
}

Alternatively, if you want to take a trip into ludicrous generic (I would not advise doing this in practical Rust code, but it's neat that it's possible), this problem is solved by the type-level version of the fixpoint combinator. Doing this in Rust is possible but tricky, so here's some Haskell instead:

data Fix f = FixC (f (Fix f))
````FixC` is the data constructor: You type `FixC some_value` to create a value, and `Fix SomeType` to refer to a type. The core trick is `f (Fix f)`, in which we "pass a type to itself" (after a fashion, since you actually _can't_ literally pass a type to itself. Allowing this makes typechecking/inference _much harder_ for little good reason, so typecheckers usually go out of their way to prevent it). Here's an example, using it to create a list:
```hs
data ListF a l = Nil | Cons a l
type List a = Fix (ListF a)
```If we expand the definition of `List` and then treat `Fix` as sort of a function, we get a fun equation:
```hs
List a = Fix (ListF a)
List a = Fix (\l -> Nil | Cons a l)
List a = Nil | Cons a (Fix (ListF a))
List a = Nil | Cons a (Fix (\l -> Nil | Cons a l))
List a = Nil | Cons a (Nil | Cons a (Fix (ListF a)))
...
```Or in other words, we basically have the infinitely nested `ListF` type, as requested. 

This _can_ be done in Rust via sufficiently clever abuse of GATs (probably. I wouldn't be surprised if it ran aground on some weird edge case), but I somehow doubt your professor intended for you to translate a trick from advanced Haskell.
#

Of course, this design is pretty bad in Rust to begin with, so I'd probably just take Sabrina's solution

somber ledge
#

Oh, neat
I'd considered doing this with box<dyn>s near the start of working on this, but I thought that generics seemed like better practice. It's really interesting that boxed dyns may have been the correct solution, given that IVertex and IEdge are already fighting against rust design

The haskell idea is also very funny, but definitely out of scope of the project. I don't know much about Haskell, so it's a little out of my expertise, but maybe I'll take a shot at doing smthg like that at some point just as practice using and abusing generics, lol

cyan timber