Recursive generic type parameters; full-featured union types?

help
1

I have a need for a structure that uses itself in its implementation. So my initial struct looked like this:

pub struct ExprMap<T> {
    sub: Option<Box<ExprMap<ExprMap<T>>>>,
    contents: Vec<T>
}

Obviously instantiating this will explode the type system because there is infinite recursion in the type definition. But what to do about it? I tried splitting it into two types, but it's still a circular definition. I tried making a trait object, but the trait needed a type parameter or associated type, so it's ultimately a circular definition. I tried the Any trait but I want to preserve internal lifetimes.

So I failed to make this work within Rust's static type system. I hit upon a solution by making the type effectively dynamic, using a union type.

pub struct ExprMap<T> {
    sub: Option<Box<Self>>,
    contents: NestedOrNotVec<T>,
}

enum NestedOrNotVec<T> {
    Nested(Vec<ExprMap<T>>),
    Not(Vec<T>),
}

But this explodes into a massive amount of boiler-plate code.

For example

impl<T> NestedOrNotVec<T> {
    pub fn get_t(&self, idx: &usize) -> Option<&T> {
        self.borrow_not().get(idx)
    }
    pub fn get_nested(&self, idx: &usize) -> Option<&ExprMap<T>> {
        self.borrow_nested().get(idx)
    }
}

It ends up effectively doubling the amount of code that needs to be written. Basically performing manual monomorphization.

So my questions are:
1.) Is there something I overlooked in Rust's static type system that would allow me to instantiate a type like this?
2.) If not, is there a mature crate for working with union types? (I spotted a few conveniences for defining union types, but I think I need something a bit more ambitious to cut down on all the boilerplate and redundancy)

Thank you.

2

This is actually fine. It compiles and you can use it. Not sure what you want it for though.

1 Like
3

It compiles and you can use it.

Ummm. Please show me how. :pray:

Not sure what you want it for though

I'm implementing this: https://arxiv.org/pdf/2302.08775.pdf

1 Like
4

How does this correspond to the types in the paper?

5

How does this correspond to the types in the paper?

Section 3.2: data ExprMap v = EM { em_var :: Map Var v, em_app :: ExprMap (ExprMap v) }

6

Okay, this makes sense. If you want this to work in the Rust type system, you will need to decide on a maximum depth, and then reduce the boilerplate with macros. I would probably have a separate struct for each level.

pub struct ExprMap1<T> {
    sub: Option<Box<ExprMap2<T>>>,
    contents: Vec<T>
}

pub struct ExprMap2<T> {
    sub: Option<Box<ExprMap3<T>>>,
    contents: Vec<ExprMap2<T>>
}

pub struct ExprMap3<T> {
    // this is the final depth, no sub
    contents: Vec<ExprMap3<T>>
}

The other method would be to make your own "type system" that can create types at runtime. But I don't know if this would be faithful to the paper.

1 Like
7

Thanks for the reply.

you will need to decide on a maximum depth

Unfortunately that can potentially be millions. Usually it won't be, but sometimes it can be. So a hard limit is a non-starter. :frowning:

The other method would be to make your own "type system" that can create types at runtime. But I don't know if this would be faithful to the paper.

That's essentially what I'm trying to do with the union types. I'm pretty sure the type I have using the union type is isomorphic to the type in the paper.

But using the union type is extremely unergonomic. Lots and lots of boiler plate. So I'm hoping somebody has written a crate with macros for exactly this case. If not I guess I'll write one but that feels like it might be a yak-shave.

Thanks again.

8

that feels like it might be a yak-shave.

The shorn yak is here: crates.io: Rust Package Registry

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.