Generalized Ranges

[Pie? via Digitalmars-d]

In a mathematical space we can define operators that allow us to 
move around in it. Take your typical Euclidean N space. We can 
define a set of orthogonal motions for each dimension. These can 
be represented by vectors(your typical orthogonal matrix), 
derivatives(infinitesimal differential increments), etc.

We can generalize this to many other spaces of dimension N by 
providing a set of N movement operators M_j.

Each M_j represents an incremental movement in the jth dimension.

In D, we can represent these as lambdas. The user provides how to 
move to the next element on the space. Iterators are a simple 
concept of this as they blindly step to the next element. In 
general though, we can have very complex spaces and move through 
those spaces in very complex ways depending on our Lambdas.

For example, suppose we have a Tree structure. In this case we 
have two orthogonal operators "sibling" and "ancestor". One moves 
us "up and down" levels of the tree and the other moves us along 
the "leafs". We can even visualize this by embedding the tree in 
to R^2 and correlating sibling movement with vertical movement in 
R^2 and ancestor movement with horizontal movement. Traversing 
the Tree can then be mapped out in R^2 and visualized.

Most common computer programming data structures have simple 
movement operators:

Single dimension spaces:
     List: Incremental: (list, k) => { return list[k]; }
     Stack: Incremental: (stack) => { return stack.pop(); }
     Queue: etc.

The movement operators can be written quite simply because they 
are generally internally defined and the language supports it. 
The point here is that most of the basis structures are 
"linear"... that is, use a single movement operator to define how 
to "move" from one position in the space to another. (e.g., 
list[k] move k steps from the origin and returns the "point" at k)

The above cases generally are all the same but only tailor the 
movement operator to specific performance or behavioral 
characteristics.

Two dimension spaces:
     Tree: Incremental, Incremental: (Tree) => { return 
Tree.Child; }, (Tree) => { return Tree.Sibling; }
     The Single dimension product cases(List^2 = List[List[]], 
etc).

etc.

The point I'm trying to make is that when we deal with 
structures, the motions specify the structure. Most of the time 
we deal with simple motions(linear/incremental).

Can D deal with the general case?

i.e., Can I specify a series of movement operators/lambdas that 
describe how I want to move through the space(maybe very complex 
where the operators are more like tensors(position dependent)) 
and then leverage D ranges to access the space?

A simple example could be a 2D List, where instead of 
incremental, I have:
(x,y) => { if (x % 2 == 0) return list[0, y]; return list[x, y % 
2]; }

Here the movement operator is cannot be written orthogonality. 
(e.g., we can't separate it as movement in the "x" direction then 
in the "y")

An orthogonal case might be
(x) => { l = list[x, Y]; X = x; return l; } (y) => { list[X, y]; 
y = Y; return l; }

Then call (x) then (y), or vice versa gives us our element at 
(x,y). (the intermediate results are projections which are only 
"half-solutions")


I noticed that when I was recursing a tree structure:

var Tree = new Dictionary<string, object>();

Where each object may be another Dictionary<string, tree>(), it 
would be much easier to be able to specify the motions in this 
space in which case I could simply "iterate" over it rather than 
use recursion directly. While we can abstract away the explicit 
recursion for simple cases, it becomes much harder when there are 
many "paths" to take at once.

In terms of iterators though, it is simply specifying the 
movement operators then the action to take at the point. If a 
nice generic set of tools existed(maybe D's ranges are suitable 
as a foundation?) then I could do something like

Tree.Traverse(
(x, T) => { foreach(var child in T) yield child; },
(y, T) => { if (y is Dictionary<string, object>) yield y; else 
Eval(y); },
(e, T) => { ... do something with e, a leaf ... })

or equivalently

void recurse()
{
    foreach(var child in T)
    {
       if (child is Dictionary<string, object>)
          recurse();
       else
          Eval(child);
    }
}

If you were paying attention you could essentially see the two 
orthogonal movements(the foreach is a motion in one direction and 
the recurse is the other). What is nice about the first example 
is that it separates the traversing of the space from the "work" 
done on the "points" in the space. For complex cases this is a 
benefit, although there may be some cross referencing between 
evaluation and movement. E.g., move left if point has some 
property, else move right.

Any Ideas?

PS. The above code is more like pseudo-code. I've been using .NET 
a lot lately and it shows! ;) Also, The idea is half baked... it 
may need some work.