Working with arrays (flatten, transpose, verfify rectangular)

[ag0aep6g]

On 20.07.22 11:18, anonymouse wrote:
>          ````d
>          auto isRectangular(A)(A a) if (isArray!A)
>          {
>              bool result;
>              size_t length = a[0].length;
> 
>              foreach (e; a) {
>                  result = e.length == length;
>              }
>              return result;
>          }
>          ````
> 
> This only works if ````a```` is a 2D array, how do I extend this to 
> support arrays with larger dimensions (3D, 4D, 5D, etc.)?

(Aside: You don't need that many backticks to mark code fragments.)

You've got a bug there. This should pass, but fails with your version:

     assert(!isRectangular([[1, 2], [], [3, 4]]));

Once `result` becomes false, you cannot let it switch to true again.

As for generalizing the function, instead of comparing the lengths of 
the elements, you want to compare their "shapes". The shape of a `Foo[] 
a1;` is `[a1.length]`. The shape of a rectangular `Foo[][] a2;` is 
`[a2.length, a2[0].length]`. And so on.

Start by extending `isRectangular` to also (optionally) return the shape 
of the array:

     bool isRectangular(A)(A a) if (isArray!A)
     {
         size_t[] dummy;
         return isRectangular(a, dummy);
     }
     bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
     {
         size_t first_length = a[0].length;
         foreach (e; a)
         {
             if (e.length != first_length) return false;
         }
         shape = [a.length, first_length];
         return true;
     }
     unittest
     {
         size_t[] shape;
         assert(isRectangular([[1, 2], [3, 4], [5, 6]], shape));
         assert(shape == [3, 2]);
         assert(!isRectangular([[1, 2], [], [3, 4]]));
     }

Extend it to one-dimensional arrays:

     bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
     {
         shape = [a.length];
         alias E = typeof(a[0]);
         static if (isArray!E)
         {
             size_t first_length = a[0].length;
             shape ~= first_length;
             foreach (e; a)
             {
                 if (e.length != first_length) return false;
             }
         }
         return true;
     }
     unittest /* one dimension */
     {
         size_t[] shape;
         assert(isRectangular([1, 2, 3], shape));
         assert(shape == [3]);
     }

Finally, use the magic of recursion to conquer higher dimensions:

     bool isRectangular(A)(A a, out size_t[] shape) if (isArray!A)
     {
         shape = [a.length];
         alias E = typeof(a[0]);
         static if (isArray!E)
         {
             size_t[] first_shape;
             if (!isRectangular(a[0], first_shape)) return false;
             shape ~= first_shape;
             foreach (e; a)
             {
                 size_t[] e_shape;
                 if (!isRectangular(e, e_shape)) return false;
                 if (e_shape != first_shape) return false;
             }
         }
         return true;
     }
     unittest /* higher dimensions */
     {
         size_t[] shape;
         assert(isRectangular([
             [[ 1,  2,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12]],
             [[13, 14, 15, 16], [17, 18, 19, 20], [21, 22, 23, 24]]
         ], shape));
         assert(shape == [2, 3, 4]);
     }

I'm sure the function can be improved further, but I'm not going to get 
into that.

> For task 3, I can visit each element of the array, but I have no idea 
> how to compose the flattened (1D) version:
> 
>          ````d
>          import std.range.primitives: ElementType;
>          auto flatten(A)(A a) if (isArray!A)
>          {
>              //ElementType!(A)[] result; //[1]
>              foreach (i; a) {
>                  static if (isArray!(typeof(i)))
>                     flatten(i);
>                  else {
>                      writeln(i);
>                      // result ~= i; //[2]
>                  }
>              }
>              //return result; // [3]
>          }
>          ````

You've got the right idea there with `flatten` calling itself on each 
element. You only need to apply that idea when getting the element type, 
too (and actually append the result of the recursive call to `result`):

         import std.range.primitives: ElementType;
         template FlatElementType(A) if (isArray!A)
         {
             alias E = ElementType!A;
             static if (isArray!E)
             {
                 alias FlatElementType = FlatElementType!E;
             }
             else
             {
                 alias FlatElementType = E;
             }
         }
         unittest
         {
             static assert(is(FlatElementType!(int[]) == int));
             static assert(is(FlatElementType!(int[][]) == int));
             static assert(is(FlatElementType!(int[][][]) == int));
         }
         auto flatten(A)(A a) if (isArray!A)
         {
             FlatElementType!A[] result;
             foreach (i; a)
             {
                 static if (isArray!(typeof(i)))
                     result ~= flatten(i);
                 else
                     result ~= i;
             }
             return result;
         }
         unittest
         {
             assert(flatten([[1, 2], [3, 4, 5], [6]]) ==
                 [1, 2, 3, 4, 5, 6]);
             assert(flatten([[[1, 2], [3, 4]], [[5, 6], [7, 8]]]) ==
                 [1, 2, 3, 4, 5, 6, 7, 8]);
         }

[...]
> As for task 3, while I understand the concept of transposing a matrix, 
> I'm not sure how to even begin.

I'm gonna leave that one for someone else.