www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.multidimarray

reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
Hello everyone!

I want to know whether there are any plans for the inclusion of 
such a module in Phobos?

Documentation:
http://denis-sh.bitbucket.org/unstandard/unstd.multidimarray.html

Source:
https://bitbucket.org/denis-sh/unstandard/src/ab5e199797e809ba4668affdc4fc8e84f40d2440/unstd/multidimarray.d?at=master

I think that the foreach loop with Multi-iterators bring many new 
and exciting designs in D:

foreach(z, y, x, ref el; matrices) // using opApply
     el = cast(int) (z * 100 + y * 10 + x);

Of course, embedded in the language is not necessary, but why not 
create a separate module std.multidimarray.
May 24 2015
parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
Another good attempt to simplify operations with multidimensional 
arrays and matrices:
https://github.com/k3kaimu/carbon/blob/master/source/carbon/linear.d
May 24 2015
parent reply "Laeeth Isharc" <laeeth nospamlaeeth.com> writes:
On Sunday, 24 May 2015 at 17:46:40 UTC, Dennis Ritchie wrote:

 Another good attempt to simplify operations with 
 multidimensional arrays and matrices:
 https://github.com/k3kaimu/carbon/blob/master/source/carbon/linear.d


You might take a look at Vlad Levenfeld's work too, although I 
think he would say that it is still at an early stage (if I 
understand correctly - looks very interesting to me, although I 
have not yet properly had time to explore it in depth)

https://github.com/evenex/autodata
May 24 2015
parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Sunday, 24 May 2015 at 20:45:56 UTC, Laeeth Isharc wrote:

 You might take a look at Vlad Levenfeld's work too, although I 
 think he would say that it is still at an early stage (if I 
 understand correctly - looks very interesting to me, although I 
 have not yet properly had time to explore it in depth)

 https://github.com/evenex/autodata


Yes, at the moment it looks all pretty damp, but very 
interesting. For example, this really is not enough:

https://github.com/evenex/autodata/blob/master/source/spaces/matrix.d#L53-L68

The fact that no library will not arrange me. I need the tools to 
work with multidimensional arrays, which will necessarily be 
built into Phobos!
May 24 2015
parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Sunday, 24 May 2015 at 22:42:12 UTC, Dennis Ritchie wrote:

 On Sunday, 24 May 2015 at 20:45:56 UTC, Laeeth Isharc wrote:

 You might take a look at Vlad Levenfeld's work too, although I 
 think he would say that it is still at an early stage (if I 
 understand correctly - looks very interesting to me, although 
 I have not yet properly had time to explore it in depth)

 https://github.com/evenex/autodata


 Yes, at the moment it looks all pretty damp, but very 
 interesting. For example, this really is not enough:

 https://github.com/evenex/autodata/blob/master/source/spaces/matrix.d#L53-L68

 The fact that no library will not arrange me. I need the tools 
 to work with multidimensional arrays, which will necessarily be 
 built into Phobos!


The matrix implementation is really just a placeholder, when I 
have more time I would like to fill it out with compile-time 
swappable backend implementations using the same matrix frontend 
(eg forwarding arithmetic operations to gsl routines).

So yes, the matrix example is very raw (I assume by damp you 
meant "siroi"). The other structures are much more fleshed out 
and provide much better examples of what I'm going for (ie any of 
the reimplemented Phobos adaptors: cycle, stride, etc).

The library itself is meant to generate consistent, safe 
interfaces for all manner of multidimensional structures (or, at 
least those that resemble cartesian products of half open 
intervals).

I can drop in a naive backend later this week as a concrete 
demonstration.

Its unlikely, even in complete form, that this would be suitable 
for inclusion in Phobos (it adds a lot of nonstandard idioms), 
but many of the design issues surrounding multidimensional 
structures with not-necessarily-integral indices have been 
carefully addressed; their solutions may prove useful in the 
effort to build a standard library package.
May 25 2015
parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Monday, 25 May 2015 at 18:11:32 UTC, Vlad Levenfeld wrote:

 The matrix implementation is really just a placeholder, when I 
 have more time I would like to fill it out with compile-time 
 swappable backend implementations using the same matrix 
 frontend (eg forwarding arithmetic operations to gsl routines).

 So yes, the matrix example is very raw (I assume by damp you 
 meant "siroi"). The other structures are much more fleshed out 
 and provide much better examples of what I'm going for (ie any 
 of the reimplemented Phobos adaptors: cycle, stride, etc).


Yes crude meaning "raw".


 The library itself is meant to generate consistent, safe 
 interfaces for all manner of multidimensional structures (or, 
 at least those that resemble cartesian products of half open 
 intervals).

 I can drop in a naive backend later this week as a concrete 
 demonstration.

 Its unlikely, even in complete form, that this would be 
 suitable for inclusion in Phobos (it adds a lot of nonstandard 
 idioms), but many of the design issues surrounding 
 multidimensional structures with not-necessarily-integral 
 indices have been carefully addressed; their solutions may 
 prove useful in the effort to build a standard library package.


Yes, that's what I mean. Some common questions about working with 
multidimensional arrays need to be addressed. For example, the 
cycle `foreach` multiple iterators, etc.
May 25 2015
parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Monday, 25 May 2015 at 18:33:57 UTC, Dennis Ritchie wrote:

 Yes, that's what I mean. Some common questions about working 
 with multidimensional arrays need to be addressed. For example, 
 the cycle `foreach` multiple iterators, etc.


Cycle was tough. I was using T[2] to track slice boundaries but 
had to retrofit the library with an Interval!(L,R) type to admit 
the possibility of unbounded dimensions. This has resulted in a 
fairly easy implementation for cycle, though. 
https://github.com/evenex/autodata/blob/master/source/spaces/cyclic.d

Foreach is something I am still considering. It is 
straightforward to define a range adaptor that traverses a 
multidimensional array lexicographically, but another interesting 
possibility is to define traversable multidim arrays recursively, 
eg:

2d array = {1d row, 2d remainder}

This is cool, as it may enable us to write generic traversals for 
n-dim arrays and trees alike... However I have been struggling to 
find a way to make such a thing work with foreach cleanly.
May 25 2015
next sibling parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Monday, 25 May 2015 at 19:14:05 UTC, Vlad Levenfeld wrote:

 Cycle was tough. I was using T[2] to track slice boundaries but 
 had to retrofit the library with an Interval!(L,R) type to 
 admit the possibility of unbounded dimensions. This has 
 resulted in a fairly easy implementation for cycle, though. 
 https://github.com/evenex/autodata/blob/master/source/spaces/cyclic.d


Yes, it would be great to learn how to create recursive iterators 
for each subarray.


 Foreach is something I am still considering. It is 
 straightforward to define a range adaptor that traverses a 
 multidimensional array lexicographically, but another 
 interesting possibility is to define traversable multidim 
 arrays recursively, eg:

 2d array = {1d row, 2d remainder}

 This is cool, as it may enable us to write generic traversals 
 for n-dim arrays and trees alike... However I have been 
 struggling to find a way to make such a thing work with foreach 
 cleanly.


That recursive n-dimensional array, but I think that recursion 
will not be effective.
http://forum.dlang.org/thread/ulhtlyxxclihaseefrot forum.dlang.org#post-mihl6m:241che:241:40digitalmars.com
May 25 2015
parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Monday, 25 May 2015 at 20:49:16 UTC, Dennis Ritchie wrote:

 That recursive n-dimensional array, but I think that recursion 
 will not be effective.
 http://forum.dlang.org/thread/ulhtlyxxclihaseefrot forum.dlang.org#post-mihl6m:241che:241:40digitalmars.com


I don't mean nested arrays, I mean an equivalent recursive 
definition for the sake of exposing a "natural" traversal 
strategy, which you get if your object admits the notion of a 
pointed element and of proper disjoint subobjects. For example:

T[0..$] = {T[0], T[1..$]}

T[0..$, 0..$]
   = {T[0, 0..$], T[1..$, 0..$]}
   = {{T[0, 0], T[0, 1..$]}, T[1..$, 0..$]}

And so on. The second definition is just lexicographic traversal 
expressed in recursive language.

If there were a way to write an adaptor to deduce such a 
recursive definition and then present it as an input range, you 
could have a uniform syntax for iterating over differently-shaped 
data structures.

The problem that I run into is presenting this as an input range 
for foreach. "front" obviously refers to the pointed element, but 
"popFront" typically returns void, not a smaller instance of the 
object - which means things like trees and multidim arrays need 
to eschew "front/popFront/empty" in favor of something like 
"head/tails[]" (with tails[].empty == true being the termination 
condition), but this isn't a viable solution for foreach loops.

I'm writing this in a bit of a hurry so I might be missing 
something essential but this is more or less the conclusion that 
I've reached after spending the last few months thinking about 
the problem. Fresh ideas are very welcome.
May 25 2015
parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Monday, 25 May 2015 at 23:40:46 UTC, Vlad Levenfeld wrote:

 I don't mean nested arrays, I mean an equivalent recursive 
 definition for the sake of exposing a "natural" traversal 
 strategy, which you get if your object admits the notion of a 
 pointed element and of proper disjoint subobjects. For example:

 T[0..$] = {T[0], T[1..$]}

 T[0..$, 0..$]
   = {T[0, 0..$], T[1..$, 0..$]}
   = {{T[0, 0], T[0, 1..$]}, T[1..$, 0..$]}

 And so on. The second definition is just lexicographic 
 traversal expressed in recursive language.

 If there were a way to write an adaptor to deduce such a 
 recursive definition and then present it as an input range, you 
 could have a uniform syntax for iterating over 
 differently-shaped data structures.

 The problem that I run into is presenting this as an input 
 range for foreach. "front" obviously refers to the pointed 
 element, but "popFront" typically returns void, not a smaller 
 instance of the object - which means things like trees and 
 multidim arrays need to eschew "front/popFront/empty" in favor 
 of something like "head/tails[]" (with tails[].empty == true 
 being the termination condition), but this isn't a viable 
 solution for foreach loops.

 I'm writing this in a bit of a hurry so I might be missing 
 something essential but this is more or less the conclusion 
 that I've reached after spending the last few months thinking 
 about the problem. Fresh ideas are very welcome.


The system of disjoint sets and D-ranges. Sounds great! I think 
about what ideas can be offered. The idea is very good!
May 25 2015
prev sibling parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Monday, 25 May 2015 at 19:14:05 UTC, Vlad Levenfeld wrote:

 https://github.com/evenex/autodata/blob/master/source/spaces/cyclic.d


And I think that the symbol `ℕ` in your code you need to replace 
some words.
May 25 2015
parent reply "Vlad Levenfeld" <vlevenfeld gmail.com> writes:
On Monday, 25 May 2015 at 20:52:33 UTC, Dennis Ritchie wrote:

 On Monday, 25 May 2015 at 19:14:05 UTC, Vlad Levenfeld wrote:

 https://github.com/evenex/autodata/blob/master/source/spaces/cyclic.d


 And I think that the symbol `ℕ` in your code you need to 
 replace some words.


Ok, done.
May 25 2015
parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Monday, 25 May 2015 at 23:14:39 UTC, Vlad Levenfeld wrote:

 And I think that the symbol `ℕ` in your code you need to 
 replace some words.


 Ok, done.


Your `cycle` - this is a very great and interesting idea!

It is necessary to implement such a foreach:

import std.algorithm : equal;

void main() {

	auto matrix = [[[1, 2, 3], [4, 5, 6]], [[7, 8, 9]], [[10, 11, 
12]]];

	foreach (idx, i, j, k..., el; matrix) {
		assert(equal(el[0], [1, 2, 3]); // el[1] == [4, 5, 6], el [2] 
== [7, 8, 9] el[3] == [10, 11, 12]
		assert(equal(i[0], 1)); // i[1] == 2, i[2] == 3, i[3] == 3
		assert(equal(j[0], 4)); // k[1] == 5, k[2] == 6
		// idx == 0 .. matrix.length
	}
}

Of course, this is just an idea. We need to think of something 
more general and better than my stub code. Ie create an array of 
iterators for each subarray. It may sound funny, but you can 
create a new foreach with advanced features for the n-dimensional 
arrays.


Also, for the n-dimensional arrays are important new advanced 
input methods, such as in Python, something like:

auto a = [[readln.split.map!(to!int)], 
[readln.split.map!(to!int)]];

// writeln(a); // [[[4, 5, 6, 3, 1, 5, 6]], [[4, 8, 6, 5, 6, 2, 
9]]] // map

writeln(a); // [[4, 5, 6, 3, 1, 5, 6]], [[4, 8, 6, 5, 6, 2, 9]] 
// without map

Ie you need to create aliases for this, for example, 
readlnArrayInt/readlnArrayStr/etc. And to finalize these input 
methods for correct and more convenient work with n-dimensional 
arrays.
May 25 2015