Rectangular multidimensional arrays for D

[H. S. Teoh via Digitalmars-d]

On Mon, Dec 22, 2014 at 08:49:45AM +0000, Laeeth Isharc via Digitalmars-d wrote:
> On Friday, 11 October 2013 at 22:41:06 UTC, H. S. Teoh wrote:
> >What's the reason Kenji's pull isn't merged yet? As I see it, it does
> >not introduce any problematic areas, but streamlines multidimensional
> >indexing notation in a nice way that fits in well with the rest of
> >the language. I, for one, would push for it to be merged.

FYI, Kenji's merge has since been merged. So now the stage is set for
somebody to step up and write a nice multidimensional array
implementation.


> >In any case, I've seen your multidimensional array implementation
> >before, and I think it would be a good thing to have it in Phobos. In
> >fact, I've written my own as well, and IIRC one or two other people
> >have done the same. Clearly, the demand is there.
> >
> >See also the thread about std.linalg; I think before we can even talk
> >about having linear algebra code in Phobos, we need a
> >solidly-designed rectangular array API. As I said in that other
> >thread, matrix algebra really should be built on top of a solid
> >rectangular array API, and not be yet another separate kind of type
> >that's similar to, but incompatible with rectangular arrays. A
> >wrapper type can be used to make a rectangular array behave in the
> >linear algebra sense (i.e. matrix product instead of per-element
> >multiplication).
> 
> 
> Hi.
> 
> I wondered how things were developing with the rectangular arrays (not
> sure who is in charge of reviewing, but I guess it is not HS Teoh).
> It would be interesting to see this being available for D, and I agree
> with others that it is one of the key foundation blocks one would need
> to see in place before many other useful libraries can be built on
> top.
> 
> Let me know if anything I can help with (although cannot promise to
> have time, I will try).
[...]

Well, just like almost everything in D, it just takes somebody to step
up to the plate and do the work. :-) Now that language support is there,
all that's left is for a good, solid design to be made, a common API
that all (multi-dimensional) rectangular arrays will conform to, and a
nice Phobos module to go along with it.

What I envision is a set of traits for working generically with
multidimensional arrays, plus some adaptors for common operations like
subarrays (rectangular "windows" or "views"), and a concrete
implementation that serves both as a basic packed rectangular array
container and also an example of how to use the traits/adaptors.

The traits would include things like determining the dimensionality of a
given array, the size(s) along each dimension, and element type. Common
operations include a subarray adaptor that does index remappings,
iteration (in various orderings), etc.. 

The concrete implementation provides a concrete multidimensional
rectangular array type that implements the aforementioned traits. It
supports per-element operators via overloading, but not matrix algebra
(which belongs in a higher-level API).

Along with this, I have found in my own experiments that it is helpful
to include a standard 1-dimensional "short array" type that serves as a
common type for storing index sets, representing array dimensions, for
use in representing (sub)regions, etc.. This "short array" type, perhaps
we can call it a Vector, is basically an n-tuple of array indices
(whatever the array index type is -- usually size_t, but in some
applications it might make sense to allow negative array indices). A
rectangular range of array indices can then be represented as a pair of
Vectors (the n-dimensional equivalent of upperleft and lowerright
corners). Index remappings for subarrays can then be implemented via a
simple subtraction and bound on the incoming index (e.g., subarray[i1]
gets remapped to originalArray[i1 - subarray.upperleft], where i1 and
upperleft are Vectors). To allow convenient interoperability with
explicit index lists (e.g., array[i,j,k,l]), Vectors should easily
expand into argument tuples, so that writing array[v1] is equivalent to
writing array[v1[0], v1[1], v2[2], ...].

None of this is groundbreaking new territory; somebody just has to sit
down and sort out the API and write the code for it.


T

-- 
Why are you blatanly misspelling "blatant"? -- Branden Robinson