www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - On Iteration

reply 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
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 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


Can you detail a little more what you're proposing?  I read your article this
morning, though admittedly I skimmed over some of the examples that looked like
things I had already been using in my code since ranges were released.  The only
thing I noticed was the save() function for forward ranges.  This resolves the
old
wart that input ranges vs. forward ranges are strictly a convention, and I think
it's a good idea.  Other than that, again, please distill what you're proposing.
Nov 09 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 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


 
 Can you detail a little more what you're proposing?  I read your article this
 morning, though admittedly I skimmed over some of the examples that looked like
 things I had already been using in my code since ranges were released.  The
only
 thing I noticed was the save() function for forward ranges.  This resolves the
old
 wart that input ranges vs. forward ranges are strictly a convention, and I
think
 it's a good idea.  Other than that, again, please distill what you're
proposing.


One is indeed save(), the other is separation of iteration from access. 
These are the only major changes. The second is quite hefty.

BTW, just saw on the announce group that the article was reddited - 
please vote up: http://www.reddit.com/r/programming/comments/a2hv3/


Andrei
Nov 09 2009
parent reply Bill Baxter <wbaxter gmail.com> writes:
On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 dsimcha wrote:

 =3D=3D Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article

 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


 Can you detail a little more what you're proposing? =A0I read your artic=




le

 this
 morning, though admittedly I skimmed over some of the examples that look=




ed

 like
 things I had already been using in my code since ranges were released.
 =A0The only
 thing I noticed was the save() function for forward ranges. =A0This reso=




lves

 the old
 wart that input ranges vs. forward ranges are strictly a convention, and=




 I

 think
 it's a good idea. =A0Other than that, again, please distill what you're
 proposing.


 One is indeed save(), the other is separation of iteration from access.
 These are the only major changes. The second is quite hefty.

 BTW, just saw on the announce group that the article was reddited - pleas=


e

 vote up: http://www.reddit.com/r/programming/comments/a2hv3/


 Andrei


I'm not sure why this one is staying so far under the radar.  Just
marketing?  The title of the previous reddit story "Iterators must
die" got a lot more attention.  I'd hate to think it just comes down
to picking deliberately inflammatory titles.

--bb
Nov 10 2009
next sibling parent Moritz Warning <moritzwarning web.de> writes:
On Tue, 10 Nov 2009 06:59:31 -0800, Bill Baxter wrote:


 On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article

 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


 Can you detail a little more what you're proposing?  I read your
 article this
 morning, though admittedly I skimmed over some of the examples that
 looked like
 things I had already been using in my code since ranges were released.
  The only
 thing I noticed was the save() function for forward ranges.  This
 resolves the old
 wart that input ranges vs. forward ranges are strictly a convention,
 and I think
 it's a good idea.  Other than that, again, please distill what you're
 proposing.


 One is indeed save(), the other is separation of iteration from access.
 These are the only major changes. The second is quite hefty.

 BTW, just saw on the announce group that the article was reddited -
 please vote up: http://www.reddit.com/r/programming/comments/a2hv3/


 Andrei


 I'm not sure why this one is staying so far under the radar.  Just
 marketing?  The title of the previous reddit story "Iterators must die"
 got a lot more attention.  I'd hate to think it just comes down to
 picking deliberately inflammatory titles.
 
 --bb


I think it's another case of "Iterators? Again?".
The announcement to finish the topic is likely to have a better 
perception.
Nov 10 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:

 On Mon, Nov 9, 2009 at 6:17 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 dsimcha wrote:

 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 article

 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


 Can you detail a little more what you're proposing?  I read your article
 this
 morning, though admittedly I skimmed over some of the examples that looked
 like
 things I had already been using in my code since ranges were released.
  The only
 thing I noticed was the save() function for forward ranges.  This resolves
 the old
 wart that input ranges vs. forward ranges are strictly a convention, and I
 think
 it's a good idea.  Other than that, again, please distill what you're
 proposing.


 One is indeed save(), the other is separation of iteration from access.
 These are the only major changes. The second is quite hefty.

 BTW, just saw on the announce group that the article was reddited - please
 vote up: http://www.reddit.com/r/programming/comments/a2hv3/


 Andrei


 
 I'm not sure why this one is staying so far under the radar.  Just
 marketing?  The title of the previous reddit story "Iterators must
 die" got a lot more attention.  I'd hate to think it just comes down
 to picking deliberately inflammatory titles.
 
 --bb


For one thing I couldn't even see the article on the "Programming" page 
after only a few hours after posting. I guess if it doesn't stay there 
for a couple of hours after posting to get primed, it never buoys to 
attention.

Andrei
Nov 10 2009
prev sibling next sibling parent reply 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
next sibling parent reply BLS <windevguy hotmail.de> writes:
On 10/11/2009 11:18, Lutger wrote:

 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




Very good read.


 - 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.



I asked the same question quit a while ago... I think we have to imagine 
a tree's branch as sub range. ( In other words, treat them like linear 
structures)

How to implement it? I dunno.

IMO it would make sense to implement some basic data structures for 
std.mutable.dtl. (Tree like structures) ...not production ready,  just 
as Range "proof of product" test.

atm I am implementing  two of them : skip lists and left leaning rb 
trees.  Would be nice to have some support btw.
Nov 10 2009
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Nov 10, 2009 at 16:07, BLS <windevguy hotmail.de> wrote:


 On 10/11/2009 11:18, Lutger wrote:

  - 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.



 I asked the same question quit a while ago... I think we have to imagine a
 tree's branch as sub range. ( In other words, treat them like linear
 structures)

 How to implement it? I dunno.


I had a Tree (and Graph) struct some month ago. In another module, I defined
depthFirst(Tree t) and breadthFirst(Tree t) functions, which just returned a
lazy range (a struct, as always), iterating in a depth-first/breadth-first
way on t. Except having them as methods of Tree/Graph, how would you do it?
Nov 10 2009
prev sibling parent reply "Phil Deets" <pjdeets2 gmail.com> writes:
On Tue, 10 Nov 2009 05:18:59 -0500, Lutger <lutger.blijdestijn gmail.com>  
wrote:


 - why is a UTF-string iterator bidirectional and why is that unexpected?


I think it is wouldn't support random access since accessing the nth code  
point (code points are similar to characters) is not a constant time  
operation since different code points can be made up of different numbers  
of bytes. That isn't necessarily intuitive since UTF-strings are stored  
contiguously in memory; so you might expect them to be random-accessible.
Nov 10 2009
parent Bill Baxter <wbaxter gmail.com> writes:
On Tue, Nov 10, 2009 at 11:34 AM, Phil Deets <pjdeets2 gmail.com> wrote:

 On Tue, 10 Nov 2009 05:18:59 -0500, Lutger <lutger.blijdestijn gmail.com>
 wrote:


 - why is a UTF-string iterator bidirectional and why is that unexpected?


 I think it is wouldn't support random access since accessing the nth code
 point (code points are similar to characters) is not a constant time
 operation since different code points can be made up of different numbers of
 bytes. That isn't necessarily intuitive since UTF-strings are stored
 contiguously in memory; so you might expect them to be random-accessible.


I thought the comment was about this:  you might expect it to be just
a forward iterator, but (surprise!) you can also find the previous
codepoint in O(1) time, due to lead units being in values ranges
distinct from following units.  But I still don't find it particularly
unexpected.  It's probably only unexpected if you don't know anything
about UTF other than the fact that each character is a variable number
of bytes.

--bb
Nov 10 2009
prev sibling next sibling parent "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
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Nov 10, 2009 at 02:53, 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 nice article, and a pleasure to read!
I'll try do do some comments, but right now what strikes me most is the
Ref!T (well, Ref<T>) idea, this separation between traversal and
access-mode.
For example, this bothers me immensely:

auto m =3D map!"a*a"([0,1,2,3][]);    // right-o, a lazy map, cool!
auto c  =3D cycle(m);   // boom! Doesn't work. Because map.front is not a
lvalue and cycle returns by ref.

Why can't I have my 0,1,4, 9,0,1,4, 9,0,1,4,9,... range? Must cycle.front
really return by ref?

I'd be delighted to have some ref-ranges for sorting, writing and such, but
I use simple non-ref ranges 9 times out of ten. And it seems std.range fall=
s
over itself to provide 'ref T front'. It makes for some interesting-to-stud=
y
code, but some ugly one as well.

So, could you elaborate on this idea ? Could this be a matter of policy?

struct Cycle(R, ByRefPolicy br =3D ByRef.ByRef) if (isForwardRange!(R))

And then, I guess, either having different implementation of .front (ugh,
but why not) or having something like:

Ref!(T, br) front() { ...} // Is this even possible?


Some comments:

p.5:
"When calling an algorithm with ranges, you write:

vector<int> v;
...
*// implicitly take the "all" range of v*
sort(v);"


Do you think containers shall routinely expose a .all method, returning
their content as a range, as simply as possible?

Btw, as an aside, std.range I guess should have some 'rangification'
functions for common constructs in D, like AA and static arrays. It's a bit
frustrating not to be able to write:

auto m =3D map!"a*a"([0,1,2,3]); // Though I know [0,1,2,3] is _not_ a rang=
e.
Maybe instead of isInputRange!R, having isInputRange!(AsRange!R) ?
or:
auto aa =3D ["a":1, "b":2, "cde":33];
auto someVal =3D filter!"a.value>3"(aa.all); // Or whatever, I'm all for
aa.all returning a lazy range with tuple(key.value) as elements.


p.7:

"The save method serves two purposes. First, in a language with reference
semantics (such as Java), lookIMadeACopy is not a copy at all=97it's an ali=
as,
another reference to the same underlying Range object. Copying the actual
object requires a method call. "

vote++. I was bitten by this just a few days ago, not thinking that
modifying an array inside a range struct would also modify the initial
array. I had to use some static if to either have _input =3D input.dup or
_input. Doing _input=3Dinput.save() could help me there.

Also p.7:

"So a random access range extends different concepts, depending on its
finiteness."

Yes indeed. It may be interesting to put this somewhere in the std.range
docs. Hell, it's obvious the entire article is a must read before using
std.algo and std.range.

Though it was interesting to re-discover this by myself. The first time you
start writing .back for an infinite range, you stop, frown, and then smile
:-)

p.9:

"Other, more exotic range capabilities are primitives such as lookahead or
putback."

I'd have liked to have lookahead sometimes...
What would putback do? Re-inject the last front value (and not some other
arbitrary value) into the range, returning it to its 'pristine' state?

p. 10:

"In keeping with higher-order functions that take and return other
functions, a higher-order range is one that aggregates and manipulates othe=
r
ranges, while itself still offering a range interface. Building ranges that
decorate other ranges is easy, useful, and fun."

Oh hell, yes! That has been the funniest coding I did this year.
Higher-order ranges is a nice name btw. You could also call them
meta-ranges, but it may be a bit too pretentious.

p. 10:

"As a rule, a higher-order range must offer the highest capability that it
can, subject to what the original range can offer."

Yes, but std.range/algo don't always do that. Would you be interested in
putting some .back/length/opIndex into map for example? That would make it
play nice with some other ranges/algorithms. I could put it into bugzilla..=
.

I was looking for a name for this kind of extensible range. It's a common
pattern, and I'm tired having to write in docs that such and such range wil=
l
also have a length if the input ranges have one, etc. As these are also
wrapper ranges, I call them 'tight wrappers', but will take any name
provided.

p. 10:
"If all contained ranges offer random access *and* length, then Chain offer=
s
random access as well."

Yes, but it's an 'if', not an 'iff'. I was bitten by this. A common test
range for me was:

auto c =3D chain([0,1,2][], cycle([3,4,5][])); // 0,1,2,3,4,5,3,4,5,3,4,5, =
...

Except it doesn't work as Chain is written right now. It doesn't even
compile: Chain.opIndex assumes all ranges have a length when they are
random-access. But cycle is RA and infinite!
The solution is trivial to code, obviously, but I routinely forget to make
it a bugzilla request (with a patch).
(Yes I know I should be putting it inside bugzilla right now. But one of my
daughters is sick and weeping, so once more it will have to wait. But now a=
t
least Andrei knows it).

p.11:

"I happen to think that bring_to_front would be a much more intuitive name
than rotate."

Indeed. rotate would be something like:

auto rotate(R)(size_t n, R range) {
   returns chain(range[n..$], range[0..n]); // for a random-access range.
}

rotate(3, [0,1,2,3,4,56][]) -> [3,4,5,6,0,1,2][]

p.12:

"Fortunately, this problem is easily solved by defining a new range type,
Until. Until is a range that takes another range r and a value v, starts at
the beginning of r, and ends just before r.front() =3D=3D v (or at the natu=
ral
end of r if v is not to be found). Lazy computation for the win!"

Nice. Is Until part of std.algo? (Gosh, this module is so big I can't get i=
t
in my head).

I personnaly use takeWhile or takeUntil.


You ask for limitation, at the end. One other limitation (though I don't
know if that's really one) is for higher-order ranges that produce/contains
two or more ranges.
Separate, for example, which separates a range into two sub-ranges, one
created by filtering the input range with predicate pred, the other by
not!pred

auto separate(alias pred, R) (R range) {
    return tuple(filter!pred(range), filter!(not!pred)(range));
}
I return a pair of ranges, but ideally would like a unique range, with a wa=
y
to address one subrange or another.
Maybe with a front(size_t index) method: front(0) returns subrange_0's
front, front(1) for the second one and so on...

  Philippe
Nov 10 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 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.


See my post about vectorized lazyness, it's almost orthogonal to the things you
talk about, but it may be a brick of the whole Range design.

(I have also written some comments about your article here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.annou
ce&article_id=17143 ).

Bye,
bearophile
Nov 10 2009