Generalized Ranges

[Joakim via Digitalmars-d]

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.