Recursive Structs with Base Case

#1

Hi there, I’m new to Rust: most of my background is in C, and reading about the Rust type system I fell in love with the Enums and Structs rust has.

I was wondering if maybe I could use this power to model problems in a more direct way than what’s usually done. Specifically, I’m thinking about recursive structures.

In C - and as far as I understand - in Rust, if you want to have a recursive struct, you will have to use pointers so the compiler can figure out the size of the struct on compile time. But what if I know the struct has a base case, and the instances of this struct are defined with constants?

I wanted to use this to model some multidimensional geometry for a project I have:

In terms of points only, if we are in an M-dimensional space:

A 0-D hypercube is an M-D vector (also known as point)
A 1-D hypercube is two 0-D hypercubes (also known as line segment)
A 2-D hypercube is two 1-D hypercubes (also known as square)
A 3-D hypercube is two 2-D hypercubes (also known as cube)
…
A N-D hypercube is two (N-1)-D hypercubes.

I want to be able to define this struct in a recursive manner using generics, specifying the base case: 0-D.


// An M-Dimensional vector
struct vector<M : usize> {
  coords: f64[M],
}

// A 0-dimensional hypercube living in an M-dimensional space
struct hypercube<0, M> {
  point: vector<M>,
}

// An N-dimensional hypercube living in an M-dimensional space
struct hypercube<N : usize, M : usize> {
  left: hypercube<N - 1, M>,
  right: hypercube<N - 1, M>,
}

If then in my code I create a hypercube specifying a constant, the compiler should be able to unroll it using the base case and figure out the size of that struct. For example:


fn main() {
    let cube_in_4d: hypercube<3, 4>; // This will have 2^3 = 8 4-dimensional vertices
}

I know Rust has generics, and this led me to find out that they are working in genericity over constants, and this is very close to what I’m thinking about, but my main issue is about defining a base case so we can have more complex, recursive structs, without losing the power of figuring them out on compile time.

Is there or will there be any way to do this?

#2

Here you meant something like this, right? For a binary Tree:

  • C: struct Tree that contains two struct *Tree, and
  • Rust: struct Tree that contains two Box<Tree>

(Being recursive structs, their layout and size can’t be known at compile time if you don’t use some sort of indirection)

#3

You might want to ping one of the const generics github threads, perhaps the one you linked. It’d be great if support for compile-time recursion of structs was included but I’ve not heard of any discussion around this myself.

#4

You can model this easily with a separate struct. (just not with constant generics)

(constant generics for the dimensionality of the vector space it is embedded in should be possible eventually in a future version of rust; but not of the ‘n’ of the ‘n-cube’ )

struct Point<T>(T);
struct Hyper<T> { left: T, right: T }

type LineSegment<T> = Hyper<Point>;
type Rectangle<T> = Hyper<LineSegment>;
type Cuboid<T> = Hyper<Rectangle>;

type Cuboid3d = Cuboid<[f64; 3]>;

If you really need to be generic over dimensionality, it will probably be easiest to accomplish this by representing dimensionality with Peano-encoded typelevel integers. (I would love to elaborate, but it’ll have to wait until I’m not typing from my phone!)

(there is also the typenum crate, but it would be overkill for this, and it would be difficult to write impls for your recursive cases in typenums binary encoding)

#5

Elaborating as promised:

Note: this is probably not something you want to do; especially when starting out; I’m just showing that it is possible. Even after you do this, you’ll have difficulty implementing functions on the generic type as you’ll need to come up with suitable traits up-front for N and T. (this is in contrast to C++'s SFINAE, which lets you get away with writing much weaker abstractions, at the cost of having incomprehensible errors when you mess up).

The end goal: We want to be able to write something like this:

type LineSegment<T> = HyperN<P1, T>;
type   Rectangle<T> = HyperN<P2, T>;
type      Cuboid<T> = HyperN<P3, T>;
type HyperCuboid<T> = HyperN<P4, T>;

To get there, we define a Peano encoding of integers…

struct Zero(());    // represents 0
struct Succ<N>(N);  // represents N + 1

type P0 = Zero;
type P1 = Succ<P0>;
type P2 = Succ<P1>;
type P3 = Succ<P2>;
type P4 = Succ<P3>;

…and do some ugly type level programming. (welcome to the dark side of rust):

/// A trait used to compute the type you get by repeatedly applying `Hyper<...>` to something
trait GetHyperN<N> {
    /// The type `Hyper<Hyper<...Hyper<Point<T>>...>>`, with `N` nested copies of `Hyper`.
    type Ty;
}

impl<T> GetHyperN<Zero> for T {
    type Ty = Point<T>;
}

impl<T, N> GetHyperN<Succ<N>> for T
where T: GetHyperN<N>
{
    type Ty = Hyper<<T as GetHyperN<N>>::Ty>;
}

// ...and some much-needed sugar
type HyperN<N, T> = <T as GetHyperN<N>>::Ty;

And there you go. It’s certainly not nice… but it’s possible.

Since I said you probably shouldn’t do the above, what should you do? Just stick to what’s in my first post, and when you need to implement a method on the type(s), you can implement it as a trait instead:

// what you would ideally be able to write (you can't write this)
// impl hypercube<N : usize, M: usize> {
//     fn num_points(&self) -> usize { 2usize.pow(N) }
// }

// what you CAN write:
trait NumPoints {
    fn num_points(&self) -> usize;
}

impl<T> NumPoints for Point<T> {
    fn num_points(&self) -> usize { 1 }
}

impl<C> NumPoints for Hyper<C>
where C: NumPoints,
{
    fn num_points(&self) -> usize { 2 * self.left.num_points() }
}