std.multidimarray

[Vlad Levenfeld via Digitalmars-d]

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.