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.

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.

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!