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.
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)
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.
Unfortunately that can potentially be millions. Usually it won't be, but sometimes it can be. So a hard limit is a non-starter.
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.