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/ulhtlyxxclihaseef...@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.
