## digitalmars.D - Generalized Ranges

• Pie? (102/102) Jun 04 2016 In a mathematical space we can define operators that allow us to
• Joakim (12/73) Jun 04 2016 D can be made to do so, but I don't think ranges can, as they
• Pie? (6/21) Jun 05 2016 I'll have to think about it more and next time I get a change to
Pie? <AmericanPie gmail.com> writes:
```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.
```
Jun 04 2016
Joakim <dlang joakim.fea.st> writes:
```On Sunday, 5 June 2016 at 00:28:36 UTC, Pie? wrote:
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?

D can be made to do so, but I don't think ranges can, as they
assume linear traversal.

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?

For structures where a consistent linear traversal can be
specified, perhaps you can map it to D ranges, though that may
not always make sense for that structure.

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.

It is an interesting idea, basically generalizing D's linear
range operators to other non-linear structures.  It might be
worthwhile to define such basic traversal functions for common
structures like trees or certain kinds of graphs, so they have a
common interface.  I don't think using D ranges underneath will
work most of the time though.
```
Jun 04 2016
Pie? <AmericanPie gmail.com> writes:
```On Sunday, 5 June 2016 at 03:17:43 UTC, Joakim wrote:
On Sunday, 5 June 2016 at 00:28:36 UTC, Pie? wrote:
[...]

D can be made to do so, but I don't think ranges can, as they
assume linear traversal.

[...]

For structures where a consistent linear traversal can be
specified, perhaps you can map it to D ranges, though that may
not always make sense for that structure.

[...]

It is an interesting idea, basically generalizing D's linear
range operators to other non-linear structures.  It might be
worthwhile to define such basic traversal functions for common
structures like trees or certain kinds of graphs, so they have
a common interface.  I don't think using D ranges underneath
will work most of the time though.

I'll have to think about it more and next time I get a change to
apply it I might try. Using lambdas makes working with arbitrary
structures quite easy but there is probably a performance issue.
With all the compile time logic D has, I imagine a lot of this
could be optimized away.
```
Jun 05 2016