digitalmars.D - Generalized Ranges
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
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> On Sunday, 5 June 2016 at 03:17:43 UTC, Joakim wrote:On Sunday, 5 June 2016 at 00:28:36 UTC, Pie? wrote: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.[...]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.
Jun 05 2016