How do I get the dimensions of multi-dimensional arrays?

Question

I want to get the size of all dimensions of an array in Rust but I'm not sure how to go about this. I'm able to get the length of the array using x.len() but I need to somehow do this recursively. I want to be able to do something like this:

let x = [[1, 2, 3], [4, 5, 6]];
println!("{:?}", x.dimensions());
// [2, 3]

A slice with a shape like [[1], [2, 3], [4, 5, 6]] should give an error.

Answer 1

It's not possible to do this in a generic fashion for every possible depth of nesting. Rust is a statically typed language, so you have to know your input and output types. What is an input type for [1] and what is the input type for [[1]]? Likewise, what are the corresponding output types?

The closest I know of is a trait with an associated type. This allows implementing it for a specific type which then associates another output type:

trait Thing {
    type Dimensions;
    fn thing(self) -> Self::Dimensions;
}

However, as soon as you implement it, you run into problems:

impl<'a, T> Thing for &'a[T] {
    type Dimensions = usize;

    fn thing(self) -> usize { 
        self.len() 
    }
}

impl<'a, T> Thing for &'a[&'a[T]] {
    type Dimensions = [usize; 2];

    fn thing(self) -> Self::Dimensions {
        [self.len(), self[0].len()]
    }
}

error[E0119]: conflicting implementations of trait `Thing` for type `&[&[_]]`:
  --> src/main.rs:14:1
   |
6  | impl<'a, T> Thing for &'a[T] {
   | - first implementation here
...
14 | impl<'a, T> Thing for &'a[&'a[T]] {
   | ^ conflicting implementation for `&[&[_]]`

That's because a &[[T]] is a &[T].

You may also think to try something recursive, but there's no way to say &[T] and know if T can be further iterated or not. If you had an HasLength trait and a DoesntHaveLength trait, nothing stops you from implementing both traits for a single type. Thus, you are stopped again.

---

Here's one partial attempt at using specialization:

#![feature(specialization)]

trait Dimensions: Sized {
    fn dimensions(self) -> Vec<usize> {
        let mut answers = vec![];
        self.dimensions_core(&mut answers);
        answers
    }
    fn dimensions_core(self, &mut Vec<usize>);
}

impl<'a, T> Dimensions for &'a [T] {
    default fn dimensions_core(self, answers: &mut Vec<usize>) {
        answers.push(self.len());
    }
}

impl<'a, T> Dimensions for &'a [T]
    where T: Dimensions + Copy
{
    fn dimensions_core(self, answers: &mut Vec<usize>)  {
        answers.push(self.len());
        self[0].dimensions_core(answers);
    }
}

impl<'a, T> Dimensions for [T; 2] {
    default fn dimensions_core(self, answers: &mut Vec<usize>)  {
        answers.push(2)
    }
}

impl<'a, T> Dimensions for [T; 2] 
    where T: Dimensions + Copy
{
    fn dimensions_core(self, answers: &mut Vec<usize>)  {
        answers.push(2);
        self[0].dimensions_core(answers);
    }
}

impl<'a, T> Dimensions for [T; 3] {
    default fn dimensions_core(self, answers: &mut Vec<usize>)  {
        answers.push(3)
    }
}

impl<'a, T> Dimensions for [T; 3] 
    where T: Dimensions + Copy
{
    fn dimensions_core(self, answers: &mut Vec<usize>)  {
        answers.push(3);
        self[0].dimensions_core(answers);
    }
}

// Also implement for all the other sizes of array as well as `Vec`

fn main() {
    let x = [[1, 2, 3], [4, 5, 6]];
    println!("{:?}", x.dimensions());

    let x = [[1, 2], [3, 4], [5, 6]];
    println!("{:?}", x.dimensions());
}

It has the obvious downside that you still have to implement the trait for each array size in order to get specialization to kick in.

---

I'm guessing that you are coming from a language that is highly dynamic. Different languages have different strengths and weaknesses. In Rust, you know your input types, so there's no way the function wouldn't know the nesting of my type. If it's going to receive a Vec<T> or a Vec<&[Vec<T>]>, I will know the depth of nesting ahead of time, so I can write a function that returns the lengths of each one:

fn depth3<A, B, C, T>(a: A) -> [usize; 3]
    where A: AsRef<[B]>,
          B: AsRef<[C]>,
          C: AsRef<[T]>
{
    let a = a.as_ref();
    // All of these should check that the length is > 1
    // and possibly that all children have same length
    let b = a[0].as_ref();
    let c = b[0].as_ref();
    [a.len(), b.len(), c.len()] 
}

fn main() {
    let x = [[[1], [2], [3]], [[4], [5], [6]]];
    println!("{:?}", depth3(&x));
}

This function is as generic as I think it can be - you pass in references to arrays, slices, vectors, or direct values for those types. In fact, I can't think of a way to even define a slice/vector/array with an unknown depth. I think to do something like that you'd have to introduce some new type (likely an enum) with some indirection so that you could have a non-infinite size.

Answer 2

An array is defined as [T], T can't be both [U; 2] and [U; 3]. This means that you wouldn't even be able to get past compilation with this.

If you instead used a Vec<Vec<T>> as @Shepmaster hints, you could do something like this.

fn main() {
    let x = vec![vec![1, 2, 3], vec![4, 5]];
    println!("{:?}", get_2d_dimension(&x));
}

fn get_2d_dimension<T>(arr: &[Vec<T>]) -> Result<(usize, usize), &str> {
    let rows = arr.len();
    if rows <= 1 {
        return Err("Not 2d");
    }
    let cols = arr[0].len();
    if arr.iter().skip(1).filter(|v| v.len() == cols).count() != rows - 1 {
        Err("Not square.")
    } else {
        Ok((rows, cols))
    }
}