Comment on PEP-0322: Reverse Iteration Methods

[Raymond Hettinger]

Please comment on the new PEP for reverse iteration methods.
Basically, the idea looks like this:

for i in xrange(10).iter_backwards(): # 9,8,7,6,5,4,3,2,1,0
<do something with i>

The HTML version is much more readable than the ReST version.
See:
http://www.python.org/peps/pep-0322.html
Several interesting ideas surfaced in the pre-pep thread:

* Call it ireverse() instead of iter_backwards().

Good idea. This is much more pithy.
* Use object properties instead of methods.

I can't yet claim to understand what the author is really
proposing. It has something to do which providing
access to an object that responds to iter, getitem, and
getslice with reversed indices.
* using a single function that looks for an __riter__ magic
method and, if not found, use __getitem__ and __len__
to build a reverse iterator.

A workable version of this was posted.
It saves implementing some object methods at the
expense of adding a new builtin function and of
creating a new magic method name.
It is slower than direct access to the underlying object.
It crashes when applied to an infinite iterator.
It produces bizarre results when applied to mappings.
* special markers for infinite iterators

This idea is interesting but doesn't extend well
when the object is wrapped by another iterator.
Also, there is no automatic way to determine
which generators can be infinite.
Raymond Hettinger

[Stephen Horne]

On Sat, 27 Sep 2003 12:17:53 -0400, David Abrahams
<da**@boost-consulting.com> wrote:

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

Somehow I think David is mistaken here - I cannot believe that
dereferencing an iterator returns a different datatype depending on
which item it happens to point to at runtime in statically typed
C++,

You didn't read carefully enough: I said std::pair<T,T>, not
std::pair<T,U>.

and without that ability to dereference the iterator (1) I cannot see
the point of iterating through a pair, and (2) the 'iterator' would
not be a true iterator as C++ iterators have to comply with one of a
set of standard protocols (forward, bidirectional, random etc) which
all include subscripting.

I'm pretty well familiar with those protocols - I've been working on
the C++ standards committee since 1997 and have written several
related proposals, c.f. http://tinyurl.com/ovpe.

OK - sorry for that.

I remain surprised that this degree of specialisation occurs, but it's
a case of live and learn I suppose.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

[David Abrahams]

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

and without that ability to dereference the iterator (1) I cannot see
the point of iterating through a pair, and (2) the 'iterator' would
not be a true iterator as C++ iterators have to comply with one of a
set of standard protocols (forward, bidirectional, random etc) which
all include subscripting.
I'm pretty well familiar with those protocols - I've been working on
the C++ standards committee since 1997 and have written several
related proposals, c.f. http://tinyurl.com/ovpe.

OK - sorry for that.

No prob.
I remain surprised that this degree of specialisation occurs, but
it's a case of live and learn I suppose.

Sorry, what specialization?

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

[Stephen Horne]

On Sat, 27 Sep 2003 19:48:24 -0400, David Abrahams
<da**@boost-consulting.com> wrote:

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

and without that ability to dereference the iterator (1) I cannot see
the point of iterating through a pair, and (2) the 'iterator' would
not be a true iterator as C++ iterators have to comply with one of a
set of standard protocols (forward, bidirectional, random etc) which
all include subscripting.

I'm pretty well familiar with those protocols - I've been working on
the C++ standards committee since 1997 and have written several
related proposals, c.f. http://tinyurl.com/ovpe.

OK - sorry for that.

No prob.

I remain surprised that this degree of specialisation occurs, but
it's a case of live and learn I suppose.

Sorry, what specialization?

Presumably template specialisation - such that the special case of
std::pair<T,T> picks up the iterating functionality that
std::pair<T,U> lacks (begin, end etc). That is what I thought you were
saying.

Or am I still getting this wrong?
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

[David Abrahams]

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

Sorry, what specialization?

Presumably template specialisation - such that the special case of
std::pair<T,T> picks up the iterating functionality that
std::pair<T,U> lacks (begin, end etc). That is what I thought you were
saying.

Or am I still getting this wrong?

Yeah, slightly. You don't need a begin() member function in order to
make an iterator. The interface might look like:

std::for_each(pair_iterator<T>(my_pair), pair_iterator<T>(), f);

Decoupling is the way to go, man! :^)

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

[Stephen Horne]

On Sun, 28 Sep 2003 11:22:11 -0400, David Abrahams
<da**@boost-consulting.com> wrote:

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

Sorry, what specialization?

Presumably template specialisation - such that the special case of
std::pair<T,T> picks up the iterating functionality that
std::pair<T,U> lacks (begin, end etc). That is what I thought you were
saying.

Or am I still getting this wrong?

Yeah, slightly. You don't need a begin() member function in order to
make an iterator. The interface might look like:

std::for_each(pair_iterator<T>(my_pair), pair_iterator<T>(), f);

Decoupling is the way to go, man! :^)

Ah - I get it! - std::pair doesn't exactly support iteration itself,
but a support class can be used to add that capability.

You can do this in any language. For instance, did you know that
Python classes supports iterating through the subset of their
attribute that have names beginning with "a", interleaved with
insults? Yes, all you need is to use this generator...

def A_Attrib_Gen (p_Instance) :
for i in dir (p_Instance) :
if i[0] = "a" :
yield i
yield "stupid stupid stupid"

Well, OK, maybe this is a little unfair - this generator isn't exactly
in the library, but with a little luck you see my point.

When you say "you can in fact iterate on std::pair<T,T> with the usual
C++ iterator protocol" it implies to me that std::pair<T,T> provides
the iterator protocol itself - not that some other class provides a
way to support iteration over the pair. After all, there is *always*
some way to support iteration of *anything*.

But maybe I'm just being overliteral.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

[David Abrahams]

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

On Sun, 28 Sep 2003 11:22:11 -0400, David Abrahams
<da**@boost-consulting.com> wrote:

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

Sorry, what specialization?

Presumably template specialisation - such that the special case of
std::pair<T,T> picks up the iterating functionality that
std::pair<T,U> lacks (begin, end etc). That is what I thought you were
saying.

Or am I still getting this wrong?
Yeah, slightly. You don't need a begin() member function in order to
make an iterator. The interface might look like:

std::for_each(pair_iterator<T>(my_pair), pair_iterator<T>(), f);

Decoupling is the way to go, man! :^)

Ah - I get it! - std::pair doesn't exactly support iteration itself,
but a support class can be used to add that capability.

You can do this in any language.

Yes; I never implied otherwise.
For instance, did you know that Python classes supports iterating
through the subset of their attribute that have names beginning with
"a", interleaved with insults?
I never, anywhere, said "std::pair supports..."
Yes, all you need is to use this
generator...

def A_Attrib_Gen (p_Instance) :
for i in dir (p_Instance) :
if i[0] = "a" :
yield i
yield "stupid stupid stupid"

Well, OK, maybe this is a little unfair - this generator isn't exactly
in the library, but with a little luck you see my point.
Your sarcasm is briefly amusing, but unwarranted.
When you say "you can in fact iterate on std::pair<T,T> with the usual
C++ iterator protocol" it implies to me that std::pair<T,T> provides
the iterator protocol itself
Hey, it's not my fault you read what you want to see into what I
posted.
- not that some other class provides a
way to support iteration over the pair. After all, there is *always*
some way to support iteration of *anything*.

But maybe I'm just being overliteral.

No, you just don't know what "the usual iterator protocol" means. It
has to do with the protocol for using iterators, and begin()/end() are
nowhere in the iterator requirements. They're part of the container
requirements. There are many iterators that have nothing to do with
containers and have never been passed through a begin()/end().
Pointers to built-in arrays are one obvious example.

This whole discussion started out talking about what the Python
protocol for manipulating iterators should be. The fact that
iterators must themselves have an __iter__ method in Python may just
be making this more confusing than it needs to be.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

[Stephen Horne]

It was my intention to explain the origins of my misunderstanding,
though certainly in a slightly less than serious way and with a big
dollop of its-not-all-my-fault-you-know. I tend to screw this kind of
thing up, and it seems I have done so again here.

Everything you have said in your last reply was at least 95% valid,
but there is a point I'd still like to make...

I never, anywhere, said "std::pair supports..." ....

When you say "you can in fact iterate on std::pair<T,T> with the usual
C++ iterator protocol" it implies to me that std::pair<T,T> provides
the iterator protocol itself

Hey, it's not my fault you read what you want to see into what I
posted.

....

But maybe I'm just being overliteral.

No, you just don't know what "the usual iterator protocol" means.

I never said, anywhere, that you said that "std::pair supports..." if
we are being that pedantic, but in the life of this thread neither of
us really has been that pedantic. I quoted your exact words for the
crucial point, which were...

"you can in fact iterate on std::pair<T,T> with the usual C++ iterator
protocol"

Pedantically speaking, this is imprecise language. Most significantly,
there is no such thing as "the usual C++ iterator protocol". An
iterator may implement any one of five different iterator protocols,
and these protocols have surprisingly little in common. All require an
operator++ and all require a dereference-style operator* and that is
it.

Actually, even the operator* isn't as common as it seems - input
iterators only support read access, output ones only write access - so
the practical commonality is limited to the operator++.

But then you weren't writing a standards document, and I wasn't
reading it as a standards document.

To most C++ programmers most of the time, the words "the usual C++
iterator protocol" don't have the pedantic meaning set by the C++
standard - they are not just about having an operator++. They have a
somewhat more pragmatic meaning, which includes the usual means of
obtaining iterators from containers. std::pair *is* a container in the
general sense of containing other objects, even though in the C++
standards document context it is not formally considered a container.

Of course there is room for misinterpretation in virtually any piece
of writing - criticism of your choice of words was certainly
intentional, but meant to be lighthearted.

But if you really believe that I "read what [i] want to see into what
[you] posted" then I'm afraid you're wrong. I saw an implication which
you never intended, but that was right at the start when I had no
reason to "want to see" anything in particular.

I do have a certain history in this kind of
minor-misunderstanding-gets-overblown storyline, as Alex Martelli I
think can confirm if he's still following the thread. Actually, he'll
probably say you should consider yourself lucky that it only got this
bad ;-)

Anyway, I'm in no doubt that I'm primarily (probably entirely)
responsible for the 'overblown' part especially with my previous post.
I appologise for that.

This whole discussion started out talking about what the Python
protocol for manipulating iterators should be. The fact that
iterators must themselves have an __iter__ method in Python may just
be making this more confusing than it needs to be.

We may think of '__iter__' as part of the iterator protocol but,
pedantically speaking, it is no more part of the Python iterator
protocol than 'begin' is part of the C++ iterator protocol.

Iterators don't have to have an '__iter__' method in Python. Iterators
only have to have a 'next' method. It is the iterable object that
implements '__iter__'. And, as with getting C++ iterators from 'begin'
etc, even that is a convention rather than a requirement.

Sometimes iterators do have an '__iter__' method, but that normally
just returns self - it's a quick-fix convenience for when iterators
end up in a context where an iterable object is expected.

I guess our mindsets aren't so different that we can't make similar
mistakes ;-)
BTW - there's no reason why an iterator can't have additional methods
beyond those required for the iterator protocol. So a container class
could, for instance, support the following...

for i in iter (container).range (begin, end).reverse () :
...

Simply by defining its iterator class as something like...

class Iter (object) :
def __init__ (self, p_Src) :
"Keep ref to container to iterate, plus other setup stuff."
self.Src = p_Src
...

def __iter__ (self) :
"Allow iterator to behave as iterable for convenience"
return self

def range (self, p_Begin, p_End) :
"Set restriction on range to be iterated"
...
return self

def reverse (self) :
"Set reverse-order iteration mode"
...
return self

def next (self) :
"Get next item"
...

Which reminds me of Paul Foleys post in "Thoughts on PEP284",
Message-ID: <m2************@mycroft.actrix.gen.nz>, about Lisp-like
for-loops - though actually it's really just a minor variation of what
Raymond suggested right from the start.

Hmmm - possibly this suggestion should be made closer to the root.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

[Stephen Horne]

On Thu, 25 Sep 2003 00:58:45 GMT, "Raymond Hettinger"
<vz******@verizon.net> wrote:

Please comment on the new PEP for reverse iteration methods.
Basically, the idea looks like this:

I have one last suggestion to make on this. Instead of adding a method
to the container, possibly it should be added to the iterator.

If the iterator class was roughly equivalent to the following...

class Iter (object) :
def __init__ (self, p_Src) :
"Keep ref to container to iterate, plus other setup stuff."
self.Src = p_Src
...

def __iter__ (self) :
"Allow iterator to behave as iterable for convenience"
return self

def reverse (self) :
"Set reverse-order iteration mode"
...
return self

def next (self) :
"Get next item"
...

We could write...

for i in iter (seq).reverse () :

Possible advantages being...

1. The need for/existence of an iterator is made explicit by the
already familiar 'iter' call.

2. Because the 'reverse' method is applied to the iterator rather
than the container, the existing spelling can be used without
worries about iterating over strings (or user classes) that
already have a 'reverse' method.

3. It's an extensible approach (other 'iterator modifiers' could be
defined in much the same way, e.g. range restriction) yet at the
same time both simple and lightweight.

The xrange and enumerate classes would probably also adopt the
'reverse' spelling for consistency...

for i in xrange(10).reverse() :
...
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

[David Abrahams]

I wasn't even going to post this to the list, because it's so full of
static and other unpythonic stuff. But then, Stephen hides his email
address, and there is one real Python-related issue at the bottom,
so...

Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> writes:

It was my intention to explain the origins of my misunderstanding,
though certainly in a slightly less than serious way and with a big
dollop of its-not-all-my-fault-you-know.
I didn't need to have an assignment of blame in order to find closure
with this thread. I was just trying to be helpful.
I tend to screw this kind of thing up, and it seems I have done so
again here.
Then I can't understand why you continue to charge about in the china
shop....
I never said, anywhere, that you said that "std::pair supports..." if
we are being that pedantic, but in the life of this thread neither of
us really has been that pedantic.
Seems like you've started.
I quoted your exact words for the crucial point, which were...

"you can in fact iterate on std::pair<T,T> with the usual C++ iterator
protocol"

Pedantically speaking, this is imprecise language.
No, there is a common subset of all iterator requirements and that's
what I was referring to.
Most significantly, there is no such thing as "the usual C++
iterator protocol". An iterator may implement any one of five
different iterator protocols, and these protocols have surprisingly
little in common. All require an operator++ and all require a
dereference-style operator* and that is it.
And that is the usual iterator protocol. I happen to know exactly
what those protocols have in common.
Actually, even the operator* isn't as common as it seems - input
iterators only support read access, output ones only write access
Actually it's subtler than that. You can have input/output iterators
which support random access which aren't random access iterators
because they don't support lvalue access. So what, though?
- so the practical commonality is limited to the operator++.
You need operator* regardless.
But then you weren't writing a standards document, and I wasn't
reading it as a standards document.
That's why I didn't understand why you were giving me such a hard
time. Because it's informal speech I'm supposed to do quadruple duty
to make sure you haven't misinterpreted me? I really was going out
of my way to explain this stuff to you politely.
To most C++ programmers most of the time, the words "the usual C++
iterator protocol" don't have the pedantic meaning set by the C++
standard - they are not just about having an operator++
And operator*.
They have a somewhat more pragmatic meaning, which includes the
usual means of obtaining iterators from containers. std::pair *is* a
container in the general sense of containing other objects, even
though in the C++ standards document context it is not formally
considered a container.
Then so is

struct { int x, y; };

Also, so is char[4], and unsigned long is a container of at least 32
bits.

This is getting ridiculous. It seems like you want to have a pedantic
debate about terms whose meaning is going to be defined by your
completely informal and subjective interpretation.
Of course there is room for misinterpretation in virtually any piece
of writing - criticism of your choice of words was certainly
intentional, but meant to be lighthearted.

But if you really believe that I "read what [i] want to see into what
[you] posted" then I'm afraid you're wrong. I saw an implication which
you never intended, but that was right at the start when I had no
reason to "want to see" anything in particular.

I do have a certain history in this kind of
minor-misunderstanding-gets-overblown storyline, as Alex Martelli I
think can confirm if he's still following the thread. Actually,
he'll probably say you should consider yourself lucky that it only
got this bad ;-)

Anyway, I'm in no doubt that I'm primarily (probably entirely)
responsible for the 'overblown' part especially with my previous post.
I appologise for that.
Thanks, I think. This is somewhat of a backhanded apology, but I'll
take it. [If you had just stopped with the last message, I wouldn't
even feel it mattered].

This whole discussion started out talking about what the Python
protocol for manipulating iterators should be. The fact that
iterators must themselves have an __iter__ method in Python may just
be making this more confusing than it needs to be.

We may think of '__iter__' as part of the iterator protocol but,
pedantically speaking, it is no more part of the Python iterator
protocol than 'begin' is part of the C++ iterator protocol.

Iterators don't have to have an '__iter__' method in Python. Iterators
only have to have a 'next' method. It is the iterable object that
implements '__iter__'. And, as with getting C++ iterators from 'begin'
etc, even that is a convention rather than a requirement.

Sorry,

http://www.python.org/doc/current/li...r.html#l2h-149

Read it twice, carefully.
Sometimes iterators do have an '__iter__' method, but that normally
just returns self
Always.
- it's a quick-fix convenience for when iterators
end up in a context where an iterable object is expected.

I guess our mindsets aren't so different that we can't make similar
mistakes ;-)

I'm afraid not. I never, ever make mistakes in the first place ;->

infallib-ly y'rs
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

[Stephen Horne]

On Mon, 29 Sep 2003 08:15:41 -0400, David Abrahams
<da**@boost-consulting.com> wrote:

That's why I didn't understand why you were giving me such a hard
time. Because it's informal speech I'm supposed to do quadruple duty
to make sure you haven't misinterpreted me? I really was going out
of my way to explain this stuff to you politely.
Nope - occasional misreadings are a fact of life and shouldn't be a
big deal. But when you said "I never, anywhere, said "std::pair
supports..."" that seemed very pedantic to me, as the issue wasn't
your precise words but the meaning behind them. And when you said
"Hey, it's not my fault you read what you want to see into what I
posted." you seemed to be claiming that there was no room for
reasonable misinterpretation in your original words and that I was
100% to blame for the misinterpretation.

The whole point of my pedanticism was to point out that your original
statement was informal and subjective and that, while that was
certainly wholy appropriate, there was room for accidental
misinterpretation. IIRC I was not even the first to misinterpret - I
simply replied to Alex Martelli who had already misinterpreted your
words the same way that I did. So being made a scapegoat seemed
unfair.

And now I seem to be whining about it far to much, but really I just
want this point to be understood - and I wish I had been clear about
it in my last post.
Then so is

struct { int x, y; };

Also, so is char[4], and unsigned long is a container of at least 32
bits.
Not in the pedantic 'C++ standard definition' sense of course, but the
C++ standard has taken an existing word and tied a more restrictive
meaning to it. In the wider world the original unrestricted meaning is
still valid.

To me both structs and char arrays are containers in the
less-restrictive sense. After all, if a C programmer talks about
containers what is he referring to? And in C# even a fixed-size array
is implemented using a library class.

An unsigned long, no - that is a single atomic item. But then again,
IIRC, in the pre-C++ days when I first learned programming, 'container
for a value' was one common way of explaining the concept of a
variable ;-)
Thanks, I think. This is somewhat of a backhanded apology, but I'll
take it. [If you had just stopped with the last message, I wouldn't
even feel it mattered].
I felt it mattered because I felt that I was being held soley and
entirely responsible for a mistake that I felt wasn't unreasonable.

I appologise for the misinterpretation because I did misinterpret, and
I particularly appologise for the overblowing because it arises out of
my oversensitivity to certain things you said - which I certainly have
no right to given the sarcastic tone of my earlier post, and in any
case I have no doubt your words resulted from frustration.

I do not, however, accept that I am enirely and soley to responsible
for the misinterpretation.

My persistence in sticking to this may seem bizarre and petty, but
there are reasons for my being bizarre and petty over such things.
Lets just call it 'desperate defending of what little self esteem I
have left' - and yes, it does tend to be counterproductive :-(
http://www.python.org/doc/current/li...r.html#l2h-149

Read it twice, carefully.
OK - you are right and I am feeling a right fool. Sorry.
I'm afraid not. I never, ever make mistakes in the first place ;->

infallib-ly y'rs

:-)
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk