On Iteration

[Philippe Sigaud]

On Tue, Nov 10, 2009 at 02:53, Andrei Alexandrescu <
SeeWebsiteForEmail at 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 = map!"a*a"([0,1,2,3][]);    // right-o, a lazy map, cool!
auto c  = 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 falls
over itself to provide 'ref T front'. It makes for some interesting-to-study
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 = 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 = map!"a*a"([0,1,2,3]); // Though I know [0,1,2,3] is _not_ a range.
Maybe instead of isInputRange!R, having isInputRange!(AsRange!R) ?
or:
auto aa = ["a":1, "b":2, "cde":33];
auto someVal = 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—it's an alias,
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 = input.dup or
_input. Doing _input=input.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 other
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 will
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 offers
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 = 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 at
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() == v (or at the natural
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 it
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 way
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20091110/32623f04/attachment.html>