# Generic arrays in Rust

Recently, I decided to try and "translate" the black hole simulator into Rust as an exercise. Initially I wanted to create a library implementing differential geometry, like tensor calculus, metric etc. I quickly encountered a problem.

## Rust and arrays

Tensors are objects with some constant number of coordinates, depending on the dimension of the space they function in. For example, in an n-dimensional space, vectors have $n$ coordinates, rank-2 tensors have $n^2$ etc. Arrays are perfect for representing such objects.
Rust handles arrays without problems. An array of N elements of type T is written in Rust as [T; N]. Everything would be fine, except for one tiny detail - I would like my code not to depend on the dimension of the space.

## The problem

It is possible to define so-called generic types in Rust. They are datatypes that have internal details parametrized by some other type. For example, we could easily create a generic 3-dimensional vector:

What if we wanted to create an n-dimensional vector, though?

Nope. You can't express an integer type parameter in Rust.
It looked hopeless, but I accidentally stumbled upon some code that suggested the existence of a solution.

## dimensioned and Peano types

In the dimensioned library the author has implemented natural numbers arithmetic... on datatypes. It basically looks like this:
Firstly, we define zero:

Then we say that zero is a natural number:

Next, we define the successor of a natural number:

Fourth: the successor of a natural number is also a natural number:

And that would be it. We can also name some types:

A function returning an actual number can also prove useful:

This way we defined datatypes representing the natural numbers. They are actual types - so they can be used as parameters in generics. Unfortunately, [T; Two] still won't work.

However, we can do this: for the type representing zero we define an empty structure, and for every successor we create a structure with two fields - the predecessor structure and one value of type T. This way, the structure defined for a type representing, for example, number 5 will have space for 5 elements of type T in it - so we will be able to treat it as a 5-element array! Let's get to work.

First, we have to somehow define an association between a structure and a given type:

Now - structures for zero and the successors:

Ok, so we defined arrays associated with the number types, which should be enough. It will be nice to have syntax resembling [T; N], though:

And so now GenericArray will work. We could now define Vector>, too. Those are real generic arrays :)

## A problem again

It turns out that such a system has one serious limitation. The number types are defined recursively and so they hit the limits of the compiler pretty quickly - that is, around 64. It can be increased, but still not even to numbers around 1000, and it is too much for the compiler anyway. It would be wise to change it somehow.

In the thread on reddit the user llogiq suggested using a binary system, similar to that used in shoggoth.rs. After some looking at this way, I decided to try it.

The beginning is very similar, except that we define not one, but two types:

Then, instead of successors, we define binary numbers:

This way we have _0, _1, (_1, _0), (_1, _1), ((_1, _0), _0), ... as the natural numbers - that is, we implemented the binary system! Of course, again we could use a conversion to an actual number:

The rest is again very similar. We assign an empty structure to zero and a structure with one field to one. Then, to each tuple (N, _0) we assign a structure with two fields of type N::Array, and to each tuple (N, _1) - with two fields N::Array and one additional element. And so we have generic arrays described in binary.

The actual implementation in the repository differs a bit from this presented here (mainly in the names of the structures) - I encourage you to look through it! :)