digitalmars.D - On Iteration
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I consider changing a bit D's range model following the better understanding reflected in this article: http://erdani.com/publications/on-iteration.html If you have any thoughts and if you can help with the implementation, please let us know. Andrei
Nov 09 2009
Lutger <lutger.blijdestijn gmail.com> writes:
Andrei Alexandrescu wrote:I consider changing a bit D's range model following the better understanding reflected in this article: http://erdani.com/publications/on-iteration.html If you have any thoughts and if you can help with the implementation, please let us know. Andrei
I thoroughly enjoyed the article, thank you in particular for making this material accessible to non computer scientists like myself. More questions than thoughts if I may, do feel free to ignore them, these are just things I wonder about: - how to do ranges over a tree? My first thought was that a tree would define preorder / inorder / postorder ranges, and then perhaps visitors for more complex algorithms. But in the 'iterators must go' keynote you mentioned implementing traversal over trees by popFront() taking a parameter indicating the branch to go to. Can you or anybody else shed more light on how this will work out? What about graphs? - ranges over immutable data structures I tried making an immutable linked list and stack (not as simple as I thought) with range support. Ranges must be mutable though. So I take it that ranges are not usually supposed to be shared, rather they be consumable, local views into immutable data structures instead? This leads to a broader question: is it possible to model some support for concurrency in ranges? So that algorithms can possibly choose a particular implementation based on the concurrent properties of a range? Perhaps this relates to the separation between iteration and access as well. - why is a UTF-string iterator bidirectional and why is that unexpected? - Is there already a standard way to implement a default range for a container? I have tons more questions, but I'll try to work them out for myself first or post them in .learn.
Nov 10 2009
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 09 Nov 2009 20:53:01 -0500, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:I consider changing a bit D's range model following the better understanding reflected in this article: http://erdani.com/publications/on-iteration.html If you have any thoughts and if you can help with the implementation, please let us know.
Very good article. I think the idea of separating access from traversal is a very good one. I still don't like the idea of having a "save" method vs. just assignment but I don't have a better idea right now. One note: As you know I think iterators are still useful for keeping pointers to individual elements. One other drawback from storing 1-element ranges as a substitute is that they may not remain one-element ranges. For instance, if you had a sorted map, stored as a RB-tree, a one element range would undoubtedly consist of a begin element and an end element, which would be the next largest element. If you inserted an element that was between those two, suddenly your 1-element range becomes a 2-element range. Although you can simply say that all ranges are invalidated when the underlying container is modified, an iterator-based solution can say that iterators always remain valid when the container is added to. That allows certain types of logic that wouldn't be as efficient with ranges. What about adding a "marker" type that has the ability to reference the data but not to traverse to another element (except by assignment)? Basically a rebindable reference. You can always get a marker to a copyable range's front element, and then a container can use 2 markers to make a traversable range, or use it as the primitive for functions like remove or insert (as an insert location), and 3-legged functions that don't map easily into 2-range functions. I'm thinking this is how I'm going to implement ranges in dcollections. Currently I support cursors, which are akin to C++ iterators (my Iterator objects are akin to Java iterators, and support only foreach). But what I might do is change them into markers, and make ranges out of 2 of them. -Steve
Nov 10 2009