473,324 Members | 2,370 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Pre-PEP: reverse iteration methods

Here is a discussion draft of a potential PEP.
The ideas grew out of the discussion on pep-284.
Comments are invited. Dart throwing is optional.
Raymond Hettinger

-------------------------------------------------------------

PEP: 323
Title: Add Reverse Iteration Methods
Version: $Revision: 1.1 $
Last-Modified: $Date: 2003/03/11 04:49:44 $
Author: Raymond Hettinger <python at rcn.com>
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Created: 23-Sep-2003
Python-Version: 2.4
Post-History: 23-Sep-2003
Abstract
========

This proposal is to extend the API of several sequence types
to include methods for iterating over the sequence in reverse.
Motivation
==========

For indexable objects, current methods for reverse iteration are
error prone, unnatural, and not especially readable::

for i in xrange(n-1, -1, -1):
print seqn[i]

One other current approach involves reversing a list before iterating
over it. That technique wastes computer cycles, memory, and lines of
code. Also, it only works with lists (strings, for example, do not define
a reverse method)::

rseqn = list(seqn)
rseqn.reverse()
for elem in rseqn:
print elem

Reverse iteration is much less common than forward iteration, but it
does arise regularly in practice.
Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem

The new protocol would be applied to lists, strings, xranges objects,
and possibly other sequence objects as well (depending on use cases
and implementation issues). It would not apply to unordered collections
like dicts and sets.

No language syntax changes are needed.
Open Issues
===========

* Should tuples be included? In the past they have been denied some list
like behaviors such as count() and index().

* Should file objects be included? Implementing reverse iteration may not
be easy though it would be useful on occasion.

* Should enumerate() be included? It would only provide reverse iteration
whenever the underlying sequence supported it.
Copyright
=========

This document has been placed in the public domain.

Jul 18 '05 #1
35 3684
Raymond Hettinger:
Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem


What about letting 'iter_backwards' be a builtin which
looks for __riter__ and if it doesn't exist, get the length
and do old-fashioned offset indexing?

Something like this untested code

def iter_backwards(obj):
try:
riter = getattr(obj, "__riter__")
except AttributeError:
n = len(obj)
while n != 0:
n = n -1
yield obj[n]
else:
for term in riter():
yield term

which would be used like

for i in iter_backwards(xrange(n)):
print seqn[i]

for elem in iter_backwards(seqn):
print elem

Andrew
da***@dalkescientific.com
Jul 18 '05 #2
Overall impression: I like it.
More comments interspersed.

John Roth

"Raymond Hettinger" <vz******@verizon.net> wrote in message
news:HA***************@nwrdny03.gnilink.net...
Here is a discussion draft of a potential PEP.
The ideas grew out of the discussion on pep-284.
Comments are invited. Dart throwing is optional.
Raymond Hettinger

-------------------------------------------------------------

PEP: 323
Title: Add Reverse Iteration Methods
Version: $Revision: 1.1 $
Last-Modified: $Date: 2003/03/11 04:49:44 $
Author: Raymond Hettinger <python at rcn.com>
Status: Draft
Type: Standards Track
Content-Type: text/x-rst
Created: 23-Sep-2003
Python-Version: 2.4
Post-History: 23-Sep-2003
Abstract
========

This proposal is to extend the API of several sequence types
to include methods for iterating over the sequence in reverse.
Motivation
==========

For indexable objects, current methods for reverse iteration are
error prone, unnatural, and not especially readable::

for i in xrange(n-1, -1, -1):
print seqn[i]

One other current approach involves reversing a list before iterating
over it. That technique wastes computer cycles, memory, and lines of
code.
It also has the "returns None instead of an object" wart.
Also, it only works with lists (strings, for example, do not define
a reverse method)::

rseqn = list(seqn)
rseqn.reverse()
for elem in rseqn:
print elem

Reverse iteration is much less common than forward iteration, but it
does arise regularly in practice.
Absolutely.

Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem

The new protocol would be applied to lists, strings, xranges objects,
and possibly other sequence objects as well (depending on use cases
and implementation issues). It would not apply to unordered collections
like dicts and sets.
I presume that the result of iter_backwards() is an iterator
object with the desired behavior. In other words, it's not
the original object that has methods to handle the iteration
protocol.

No language syntax changes are needed.
Open Issues
===========

* Should tuples be included? In the past they have been denied some list
like behaviors such as count() and index().
I'd say yes, but I don't know the reason why tuples are missing methods.

* Should file objects be included? Implementing reverse iteration may not
be easy though it would be useful on occasion.
Are we talking text files or binary files here? Offhand, I'm not even
sure there is a binary file iterator, although if there is reverse iteration
shouldn't be difficult. Reverse iteration for text files simply means
implementing
the reverse scan in C, since the standard library doesn't support it. For
small enough files, it may be easier to simply internally use getlines() and
then use iter_reverse() on the list.

* Should enumerate() be included? It would only provide reverse iteration
whenever the underlying sequence supported it.
I don't see why not.

In general, I support the notion that a concept should be implemented
pervasively, unless there's a clear reason not to do it in a special case.
Special cases are just that - if they really are special, you trip over them
once and then remember them. What gets messy is something that's
partially implemented, where there is no clear rule to determine when
it is and when it isn't.

John Roth

Copyright
=========

This document has been placed in the public domain.

Jul 18 '05 #3

"Raymond Hettinger" <vz******@verizon.net> wrote in message
news:HA***************@nwrdny03.gnilink.net...
for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem


I would prefer a much shorter name, such as riter for reverse/right
iter. This goes along with current nomenclature such as rfind, etc.

Terry J. Reedy

Jul 18 '05 #4

"Andrew Dalke" <ad****@mindspring.com> wrote in message
news:hJ****************@newsread4.news.pas.earthli nk.net...
Raymond Hettinger:
Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem


What about letting 'iter_backwards' be a builtin which
looks for __riter__ and if it doesn't exist, get the length
and do old-fashioned offset indexing?


There are objects that support iteration that
don't support len(), such as file objects.
This has got the advantage, of course, that it would
automatically work on all objects that support
an sequence-like protocol, though.

Frankly, I prefer the notion of a method.
Maybe make it a method of object that
automatically works on all new style
objects that support a sequence-like
protocol?

John Roth

Jul 18 '05 #5
John Roth:
There are objects that support iteration that
don't support len(), such as file objects.
Sure. Then it'll given an exception. The implementation
should turn around and raise the proper exception there
instead of a "len doesn't exist" one.

There's also a problem that len works on a dict but
__getitem__(int) will only work if the dict stores 0->n-1
as keys.
This has got the advantage, of course, that it would
automatically work on all objects that support
an sequence-like protocol, though.
Yup.
Frankly, I prefer the notion of a method.


While I don't. There are many, many ways to
iterate through a list. (What about all evens
followed by all odds?) Right now they are all
done by using a function which creates an iterator
across a container. If it's a method then you've
said that reverse_iter is special enough that it
must be a method, which seems strange for something
which is so infrequently used.

Andrew
da***@dalkescientific.com
Jul 18 '05 #6
"Raymond Hettinger" <vz******@verizon.net> wrote in message
news:HA***************@nwrdny03.gnilink.net...
Here is a discussion draft of a potential PEP. [snip] Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem


Hi.
This will mostly just be some alternate naming suggestions:

How about just ".backwards", where backwards acts like a read-only property
that returns a generator for reverse iteration?

for i in xrange(n).backwards:
print seqn[i]

for elem in seqn.backwards:
print elem

It's not as explicit as iter_backwards(), but it's shorter, cleaner, and
appears
obvious (to me, anyway). Or, perhaps, 'ibackwards', or 'ireverse' ; or
ibackwards() or ireverse(). (being reminiscent of imap() and izip())
'.reverse' would be good, but, of course, it's already taken...

If one could be made, a fast** general purpose "reverse(iterable)" (or
ireverse(iterable)) function would be my preference (at the very least, it
would
avoid having to add iter_backwards() to several type definitions).

# e.g.
for i in reverse(xrange(n)):
print seqn[i]

for index, item in reverse(enumerate(seqn)):
print "index:%s item:%s"%(index, item)

# that sort of thing...

** Yep, fast. Something where xrange(n-1, -1, -1) is not exorbitantly
faster than reverse(xrange(n)). Similarly, for sequence types, you'd
want reverse(list) to be atleast somewhere near as quick as:

# python-faq, entry 4.6
list.reverse()
try:
for x in list:
"do something with x"
finally:
list.reverse()
Jul 18 '05 #7
[Raymond Hettinger]
Reverse iteration is much less common than forward iteration, but it
does arise regularly in practice.

[John Roth] Absolutely.


Because the question will arise, I did a quick use case analysis from
the standard library. I'll attach the following to the PEP. Feel free
to comment or add other use cases.
Raymond Hettinger

--------------------------------------------------------------------------
Use Case Analysis
=================

Here are some instances of reverse iteration taken from the standard
library and comments on why reverse iteration was necessary:

* atexit.exit_handlers() uses::
while _exithandlers:
func, targs, kargs = _exithandlers.pop()
. . .
The application dictates the need to run exit handlers in the
reverse order they were built. The "while alist: alist.pop()"
form is readable and clean; however, it would be slightly faster
and clearer with:
for func, target, kargs in _exithandlers.iter_backwards():
. . .
del _exithandlers

* difflib.get_close_matches() uses::
result.sort() # Retain only the best n.
result = result[-n:] # Move best-scorer to head of list.
result.reverse() # Strip scores.
return [x for score, x in result]
The need for reverse iteration arises from a requirement to return
a portion of a sort in an order opposite of the sort criterion. The
list comprehension is incidental (the third step of a Schwartzian
transform). This particular use case can met with extended slicing,
but the code is somewhat unattractive and hard to visually verify::
result.sort()
return result[:-n-1:-1]

* heapq.heapify() uses "for i in xrange(n//2 - 1, -1, -1)" because
higher-level orderings are more easily formed from pairs of
lower-level orderings. A forward version of this algorithm is
possible; however, that would complicate the rest of the heap code
which iterates over the underlying list in the opposite direction.

* mhlib.test() uses::
testfolders.reverse();
for t in testfolders:
do('mh.deletefolder(%s)' % `t`)
The need for reverse iteration arises because the tail of the underlying
list is altered during iteration.

* platform._dist_try_harder() uses "for n in range(len(verfiles)-1, -1, -1)"
because the loop deletes selected elements from "verfiles" but needs to
leave the rest of the list intact for further iteration. This use
case could be more efficiently met with itertools.ifilter but the
lambda condition and functional style would render it less readable.

* random.shuffle uses "for i in xrange(len(x)-1, 0, -1)" because the
algorithm is most easily understood as randomly selecting elements
from an ever diminishing pool. In fact, the algorithm can be run in
a forward direction but is less intuitive and rarely presented that
way in literature.

* rfc822.Message.__delitem__() uses:
list.reverse()
for i in list:
del self.headers[i]
The need for reverse iteration arises because the tail of the underlying
list is altered during iteration.


Jul 18 '05 #8
Sean Ross:
This will mostly just be some alternate naming suggestions:

How about just ".backwards", where backwards acts like a read-only property that returns a generator for reverse iteration?


-1 from me. 'backwards' looks to me like something which changes
the list ordering in place, like what 'reverse' does. Or something
which returns a new list but in reverse order. It's an adjective,
when it should be a verb.

ibackwords would work, but so would riter or reviter or
variations thereof.

Andrew
da***@dalkescientific.com
Jul 18 '05 #9
On Wed, 24 Sep 2003 00:30:31 GMT, "Raymond Hettinger"
<vz******@verizon.net> wrote:
Proposal
========

Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::

for i in xrange(n).iter_backwards():
print seqn[i]

for elem in seqn.iter_backwards():
print elem
That is a pretty long name. Can we use the convention from itertools
where an 'i' prefix is sufficient to suggest an iterator, giving
'ibackwards' or 'ireverse' or similar.

Second, I'm not quite ready to drop my property idea ;-)

An advantage is that the object returned by the property can sensibly
support more than just iteration - e.g. slicing (as touched on in the
PEP284 thread). So for instance...
x = range(10)
list(x.backward) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] list(x.backward [::2])

[8, 6, 4, 2, 0]
* Should file objects be included? Implementing reverse iteration may not
be easy though it would be useful on occasion.
IMO no - doing this essentially needs the whole file to be read into
memory, in which case you may as well read the whole file into a list
and then iterate the list backwards.
* Should enumerate() be included? It would only provide reverse iteration
whenever the underlying sequence supported it.


Why not...

for i, j in enumerate (listname.iter_backwards ()) :

in other words, as enumerate can handle the already-reversed
sequence/iteration, I don't see the point.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #10
On Wed, 24 Sep 2003 04:44:21 GMT, "Andrew Dalke"
<ad****@mindspring.com> wrote:
-1 from me. 'backwards' looks to me like something which changes
the list ordering in place, like what 'reverse' does. Or something
which returns a new list but in reverse order. It's an adjective,
when it should be a verb.


I disagree with this. IMO something that modifies a value in place
should be named using a verb (such as reverse, or sort, or update...).
Something that returns a value without modifying its parameters/object
should be named to describe what it returns - normally a noun or
adjective (such as globals, len, isinstance).

So if we had a sorting function that returns a sorted version of the
parameter without modifying its parameter, I'd want it to be called
'sorted' as opposed to the current in-place 'sort'.

Of course there are non-modifying functions that are named as verbs
(map, filter and reduce being particularly obvious), but that does
seems slightly wrong to me - though for the ones I've listed there is
basically an overriding convention (they are well known names).
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #11
On Wed, 24 Sep 2003 04:44:21 GMT, "Andrew Dalke"
<ad****@mindspring.com> wrote:
-1 from me. 'backwards' looks to me like something which changes
the list ordering in place, like what 'reverse' does. Or something
which returns a new list but in reverse order. It's an adjective,
when it should be a verb.


I disagree with this. IMO something that modifies a value in place
should be named using a verb (such as reverse, or sort, or update...).
Something that returns a value without modifying its parameters/object
should be named to describe what it returns - normally a noun or
adjective (such as globals, len, isinstance).

So if we had a sorting function that returns a sorted version of the
parameter without modifying its parameter, I'd want it to be called
'sorted' as opposed to the current in-place 'sort'.

Of course there are non-modifying functions that are named as verbs
(map, filter and reduce being particularly obvious), but that does
seems slightly wrong to me - though for the ones I've listed there is
basically an overriding convention (they are well known names).
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #12
On Wed, 24 Sep 2003 02:13:48 GMT, "Andrew Dalke"
<ad****@mindspring.com> wrote:
Frankly, I prefer the notion of a method.


While I don't.


To me, the reason to use a method (or property) is simply that most
types cannot be efficiently 'backwardised'. For instance, iterators in
general would have to be buffered into a list an then the resulting
list iterated backwards. That could be useful, but the overhead is
sufficient that I think explicitly writing 'list (x).backward ()'
rather than 'x.backward ()' would be a good thing.

Having a method (or property) explicitly associates it with the
object/class being handled.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #13
On Wed, 24 Sep 2003 02:13:48 GMT, "Andrew Dalke"
<ad****@mindspring.com> wrote:
Frankly, I prefer the notion of a method.


While I don't.


To me, the reason to use a method (or property) is simply that most
types cannot be efficiently 'backwardised'. For instance, iterators in
general would have to be buffered into a list an then the resulting
list iterated backwards. That could be useful, but the overhead is
sufficient that I think explicitly writing 'list (x).backward ()'
rather than 'x.backward ()' would be a good thing.

Having a method (or property) explicitly associates it with the
object/class being handled.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #14
"Andrew Dalke" <ad****@mindspring.com> wrote in message news:<w5*****************@newsread4.news.pas.earth link.net>...
Sure. Then it'll given an exception. The implementation
should turn around and raise the proper exception there
instead of a "len doesn't exist" one.

There's also a problem that len works on a dict but
__getitem__(int) will only work if the dict stores 0->n-1
as keys.

How about using a temporary sequence if __riter__ isn't defined?
It's slow, but would work with all non-infinite iterators that
don't have strange side effects (vast majority).
def riter(obj):
try:
rit = getattr(obj, "__riter__")
except AttributeError:
# assuming list has __riter__, the following could be:
# for x in riter(list(obj)):
# yield x
seq = list(obj)
n = len(seq)
while n != 0:
n -= 1
yield seq[n]
else:
for term in rit():
yield term

# reverse iteration of file
f = file('riter.py')
try:
for line in riter(f):
print line,
finally:
f.close()

# reverse iteration of a dictionary
for x in riter({'foo':1, 'bar':2}):
print x,
I changed it to use a shorter name as suggested by Reedy, to be similar
with rfind etc. I also prefer a function instead of a method, as the function
can provide (slow) default behaviour for iterators that don't explicitely
support reverse iteration.
Jul 18 '05 #15
> PEP: 323
Title: Add Reverse Iteration Methods
Version: $Revision: 1.1 $


I don't need this often enough to want it as a method or a builtin
function.
But it would ne nice to have a function in the itertool module.

I would call it riter(), it should work on any sequence with len()
support or on any object wich define the __riter__ special method.

In practice, I mostly use reverse iteration when I most remove some
few objects on the sequence I'm itering to, so I have more neeed for a
renumerate() function:

for index, value in itertools.renumerate(sequence):
if not value:
del sequence(index)
Jul 18 '05 #16
[Raymond Hettinger]
for elem in seqn.iter_backwards():
print elem
[Stephen Horne]
That is a pretty long name. Can we use the convention from itertools
where an 'i' prefix is sufficient to suggest an iterator, giving
'ibackwards' or 'ireverse' or similar.
That sounds reasonable to me. I'll add that alternative to the PEP.

If the discussion on enumerate() is any indication, then the naming
discussion will be much more lively than on the idea itself. Perhaps,
Alex will once again be able to suggest a musically perfect, beautiful
Italian name.

BTW, if you think iter_backwards is long, then take a look at some
of the method names in the sets module.

Second, I'm not quite ready to drop my property idea ;-)

An advantage is that the object returned by the property can sensibly
support more than just iteration - e.g. slicing (as touched on in the
PEP284 thread). So for instance...
x = range(10)
list(x.backward) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]


I'm not clear on the details of what you're proposing. What is
type(x.backward)?
Please show what a pure python version would look like
(taking UserList as an example).
* Should file objects be included? Implementing reverse iteration may not
be easy though it would be useful on occasion.


IMO no - doing this essentially needs the whole file to be read into
memory, in which case you may as well read the whole file into a list
and then iterate the list backwards.


Oh, it could be done using seeks and whatnot;
however, the code might be grotesque.
* Should enumerate() be included? It would only provide reverse iteration
whenever the underlying sequence supported it.


Why not...

for i, j in enumerate (listname.iter_backwards ()) :

in other words, as enumerate can handle the already-reversed
sequence/iteration, I don't see the point.


The point is that enumerate will starting numbering from zero
for the last item:
mystr = 'abc'
list(enumerate(mystr.iter_backwards())) [(0, 'c'), (1, 'b'), (2, 'a')]

If you want the indices to match their original position, then you
would need something like:
list(enumerate(mystr).iter_backwards())

[(2, 'c'), (1, 'b'), (0, 'a')]

The implementation would need to access both mystr.iterbackwards()
and mystr.__len__().

At first glance, this is a can of worms, a pandora's box,
a gordian knot, or some unnamed code smell unsuitable
for this mixed metaphor.

Raymond Hettinger

Jul 18 '05 #17

"Stephen Horne" <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> wrote in
message news:f4********************************@4ax.com...
On Wed, 24 Sep 2003 00:30:31 GMT, "Raymond Hettinger"
<vz******@verizon.net> wrote:
Proposal
========
* Should file objects be included? Implementing reverse iteration may not be easy though it would be useful on occasion.


IMO no - doing this essentially needs the whole file to be read into
memory, in which case you may as well read the whole file into a list
and then iterate the list backwards.


Actually, it doesn't. It does require that the file be read into the
buffers backwards, but from there it's simply a matter of doing
a reverse scan for the line ending characters. The difficulty is that
the entire algorithm would have to be done in C, without any
significant help from the standard library.

John Roth
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk

Jul 18 '05 #18
Stephen Horne <$$$$$$$$$$$$$$$$$@$$$$$$$$$$$$$$$$$$$$.co.uk> wrote in message news:<f4********************************@4ax.com>. ..
* Should enumerate() be included? It would only provide reverse iteration
whenever the underlying sequence supported it.


Why not...

for i, j in enumerate (listname.iter_backwards ()) :

in other words, as enumerate can handle the already-reversed
sequence/iteration, I don't see the point.


That's not the same:
list(enumerate([10,11,12])) [(0, 10), (1, 11), (2, 12)] list(enumerate([10,11,12].riter())) [(0, 12), (1, 11), (2, 10)] list(enumerate([10,11,12]).riter())

[(2, 12), (1, 11), (0, 10)]

Indices would also be reversed.
Jul 18 '05 #19
Raymond Hettinger wrote:
If you want the indices to match their original position, then you
would need something like:
>>> list(enumerate(mystr).iter_backwards()) [(2, 'c'), (1, 'b'), (0, 'a')]

The implementation would need to access both mystr.iterbackwards()
and mystr.__len__().

At first glance, this is a can of worms, a pandora's box,
a gordian knot, or some unnamed code smell unsuitable
for this mixed metaphor.


You can count down starting at -1 for reverse enumeration and keep that can
of pandora's knots closed :-)

The only drawback I see would be that the following behaviour might not be
what you expect:
[(i, c, "uvwxyz"[i]) for i, c in reverse_enumerate("abc")] [(-1, 'c', 'z'), (-2, 'b', 'y'), (-3, 'a', 'x')]


Peter
Jul 18 '05 #20
Raymond Hettinger wrote:
If you want the indices to match their original position, then you
would need something like:
>>> list(enumerate(mystr).iter_backwards()) [(2, 'c'), (1, 'b'), (0, 'a')]

The implementation would need to access both mystr.iterbackwards()
and mystr.__len__().

At first glance, this is a can of worms, a pandora's box,
a gordian knot, or some unnamed code smell unsuitable
for this mixed metaphor.


You can count down starting at -1 for reverse enumeration and keep that can
of pandora's knots closed :-)

The only drawback I see would be that the following behaviour might not be
what you expect:
[(i, c, "uvwxyz"[i]) for i, c in reverse_enumerate("abc")] [(-1, 'c', 'z'), (-2, 'b', 'y'), (-3, 'a', 'x')]


Peter
Jul 18 '05 #21
I like the idea of having some iterator.backwards, backwards(iterator) etc.

However especially reading Andrew Dalke's postings and replies (and
having thought about using internally len() and so on --- but then
thinking of iterator maybe having *no* __len__)
I now think that reverse iteration is not well defined when __len__
can't be defined (and sometimes even if it is). This is not the case for
list-like objects as they
have a predictable fixed length (even if the __len__-method isn't
actually implemented).
Let me give an example:

class NaturalNumbers:
def __init__(self):
self.n= 0
def __iter__(self):
return self
def next(self):
self.n+=1
return self.n
This is surely ordered but defining the reverse-order is difficult.
Maybe it should always return infty then.

Or think about a "Tape-Iterator". An object that reads data from e.g. a
file forwards/next and backwards/iter_backwards.
What would you expect to get if tape is at position x and you say
tape.backwards()?
Should it be the last byte of the file or maybe that on position x-1 ?
This shows that we can get into trouble when we have already iterated
"in the right direction" and then start to do "backwards".

While reverse-iteration is a sound idea we need a clear definition of
what is meant!
I thought of the following (I give multiple possibilies named a,b,c, ...
finally only one may be used):
1. If iterator has fixed/determined length (so it could be converted
into a regular list):
a) iterator.iter_backwards() creates an independent reverse-iterator:
1.1)
l2= list(iterator)
l1= list(iterator.iter_backwards())
l2.reverse()
l1 and l2 have to be equal
1.2)
l1= list(iterator.iter_backwards())
l2= list(iterator)
l2.reverse()
l1 and l2 have to be equal
(next cases as examples for simplicity)
1.3)
it= range(4)
it.next()
l1= list(it.iter_backwards())
l2= list(it)
-> l1 == [3,2,1]
l2 == [1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwards()
l1= [itBack.next(), itBack.next(), itBack.next()]
l2= [it.next(), it.next(), it.next()]
-> l1= [3,2,1]
l2= [0,1,2]
b) iterator.iter_backwards() creates a dependent reverse-iterator:
1.1) 1.2) like in a)
(next cases as examples for simplicity)
1.3)
it= range(4)
it.next()
l1= list(it.iter_backwards())
l2= list(it)
-> l1 == [0,]
l2 == [0,1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwards()
l1= [itBack.next(), itBack.next(), itBack.next()]
l2= [it.next(), it.next(), it.next()]
-> l1= [3,2,1]
l2= [1,2,3]
2. Infinite/non-determined iterators:
They should implement reverse-iteration in a way that
iterator.next()
iterator.iter_backwards().next()
is a nop
and
iterator.iter_backwards().next()
iterator.next()
is a nop, too.
Or if there are more backward than forward-steps should raise some
StopBackwardIterator

I'm sure there are a lot more and probably better definitions, so I hope
we will find a useful one.
Christoph Becker-Freyseng



Jul 18 '05 #22
On Wed, 24 Sep 2003 00:30:31 GMT, rumours say that "Raymond Hettinger"
<vz******@verizon.net> might have written:
Abstract
========

This proposal is to extend the API of several sequence types
to include methods for iterating over the sequence in reverse.


-0

I believe this should be a function in itertools.

For indexable sequences, a little modification of itertools.islice would
do the trick, since it can't at the moment; it's designed for forward
iteration.

Helpful error messages:
itertools.islice(lst, len(lst)-1, -1, -1) ValueError: Stop argument must be an integer or None. itertools.islice(lst, len(lst)-1, None, -1)

ValueError: Step must be one or larger for islice().

For non-indexable sequences (eg a file object), things get hairier, but
given enough memory, it's not hard.
--
TZOTZIOY, I speak England very best,
Microsoft Security Alert: the Matrix began as open source.
Jul 18 '05 #23
Raymond Hettinger wrote:
Add a method called iter_backwards() to sequence objects that can benefit
from it. The above examples then simplify to::
I'm not too fond of the name "iter_backwards". I think it is too long
(with respect to the already existing "iter" built-in function).

It's just my feeling towards the name, but to me "iter_backwards" sounds
more like an action that is performed on the object it is called on
(a real method so to speak, not a factory method):
"seq.iter_backwards()" reads to me at first glance: 'iterate over the
seq in backward direction'. Not: 'return a reverse iterator object'.
('iter' reads like the verb/action 'iterate' instead of a noun).

Instead, "backwards_iter", "back_iter" or preferrably just "riter"
reads more natural to me:
"seq.back_iter()" reads to me at first glance: 'get a backwards iteration
object for seq'. ('iter' reads like the noun 'iterator', not a verb).
No language syntax changes are needed.
Making it a method, indeed. But then there is this difference
between *forward* iteration and *backward* iteration, right?

iter(seq) --> get a (forward) iterator for seq
seq.riter() --> get a (backward) iterator for seq

How is this easily explained to new people? Why not keep it
orthogonal:

iter(seq) and riter(seq)
~or~
seq.iter() and seq.riter()

For what it's worth (probably nothing, but hey), in C++ STL
we have seq.begin() that returns a forward iterator, and
seq.rbegin() that returns a backward iterator.

* Should tuples be included? Don't really care. Are there any reasons why they shouldn't?
* Should file objects be included? Don't care. I've never had to read a file in reverse.
* Should enumerate() be included?

I think it should.
--Irmen de Jong

Jul 18 '05 #24
At 06:30 PM 9/23/2003, you wrote:
Here is a discussion draft of a potential PEP.
The ideas grew out of the discussion on pep-284.
Comments are invited. Dart throwing is optional.

The discussion so far has focused on how to modify the operand of for x in.

There is another viewpoint: consider that we are modifying the behavior of
for x in

In APL we often modify the behavior of a primitive operator by adding
something to the operator itself. For example
+/A means apply + along the last last dimension of the array A. (e.g. sum
the elements in each row of the matrix A)
To sum along the columns change the expression to =+/[1]A where the index
modifies the / operator.

Could this open the door to some fundamentally new Python syntax that
would support the modification of keyword behavior? e.g.:

for x in[-1] list:
for[-1] x in list:
for x in[-1] list:for x in[-1] list:
for.reverse x in list:
for x out list:
rof x in list:

Let's brainstorm?


Bob Gailer
bg*****@alum.rpi.edu
303 442 2625
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.506 / Virus Database: 303 - Release Date: 8/1/2003

Jul 18 '05 #25
[Raymond]
Abstract
========

This proposal is to extend the API of several sequence types
to include methods for iterating over the sequence in reverse.
[Christos TZOTZIOY Georgiou]
-0

I believe this should be a function in itertools.

For indexable sequences, a little modification of itertools.islice would
do the trick, since it can't at the moment; it's designed for forward
iteration.

Helpful error messages: itertools.islice(lst, len(lst)-1, -1, -1) ValueError: Stop argument must be an integer or None. itertools.islice(lst, len(lst)-1, None, -1)

ValueError: Step must be one or larger for islice().

For non-indexable sequences (eg a file object), things get hairier, but
given enough memory, it's not hard.


Here's a quick and dirty implementation of your idea (kept separate
from islice for clarity). On the plus side, it is somewhat clean and
easy to use. On the minus side:
* It's slower than custom iterator methods
* It behaves badly with infinite iterators as inputs
* For non-indexables, it silently transitions into a
non-lazy, memory intensive mode with a long
delay on the first call. In my opinion, this defeats
the purpose of using iterators in the first place.

def ireverse(obj):
assert not hasattr(obj, 'keys')
try:
for i in xrange(len(obj)-1, -1, -1):
yield obj[i]
except (AttributeError, TypeError):
x = list(obj) # XXX fails with infinite iterators
x.reverse()
for elem in x:
yield elem

for i in ireverse(xrange(5)):
print i

for c in ireverse('abcde'):
print c

for elem in ireverse(['atom', 'beta', 'curry']):
print elem

for line in ireverse(file('/autoexec.bat')):
print line.rstrip()

for x in reverse(itertools.count()):
# Never gets here and Python dies with a MemoryError
# from the infinite loop
pass
Raymond Hettinger

Jul 18 '05 #26
Raymond Hettinger wrote:
* It behaves badly with infinite iterators as inputs
[...]
def ireverse(obj):
assert not hasattr(obj, 'keys')
# let inifinite iterators identify themselves
assert not hasattr(obj, 'infinite')
try:
for i in xrange(len(obj)-1, -1, -1):
yield obj[i]
except (AttributeError, TypeError):
x = list(obj) # XXX fails with infinite iterators
x.reverse()
for elem in x:
yield elem


As infinite iterators are rare, it would not be too cumbersome to let them
identify themselves as such.

Peter
Jul 18 '05 #27
Stephen Horne:
To me, the reason to use a method (or property) is simply that most
types cannot be efficiently 'backwardised'.
Which is why my function looks for an '__riter__' under
the covers, so that an object can provide a specialized
implementation, if possible.

If it can't, I then proposed an implementation which will
iterate in reverse through lists and list-like interfaces (things
indexed by 0, 1, ... len(obj)-1). There is a problem though
in that my attempt at a 'generic' reverse implementation
will give strange errors in dictionary-like interfaces.
For instance, iterators in
general would have to be buffered into a list an then the resulting
list iterated backwards. That could be useful, but the overhead is
sufficient that I think explicitly writing 'list (x).backward ()'
rather than 'x.backward ()' would be a good thing.


Those objects which implement a 'reverse_iterate' /
'backward' / whatever are identical to those which would
implement a __riter__ accessed under the covers.

My question is, what to do about objects which *don't*
provide a special method. Should there still be a standard
way to do a reverse iteration through them?

The only two I can think of are:
- assume
for i in range(len(obj)-1, -1, -1): yield obj[i]
works as a backup. It doesn't quite work because of
dictionaries.

- assume that storing all elements in a temporary
list and doing a reverse on the temp list is okay.
As you point out, it is the most generic but doesn't
work if memory is a problem. (There's also a
concern about proper destruction order if you want
to delete elements from a list starting from the end.)

- (There's a third, which is O(n**2). At every request,
iterate through the list to find the last element.)

If there is an acceptable solution (which needn't be
perfect, just practicable) then it's a good reason to
have it be a builtin over a special method.

I still point out that there are many other ways of
doing iteration and I don't see what makes reverse
iteration so important to get its own method.

Andrew
da***@dalkescientific.com

Jul 18 '05 #28
Me:
The only two I can think of are: for i in range(len(obj)-1, -1, -1): yield obj[i]


Peter Otten proposed a nice variation; assume negative
indicies work. Then there's no need to assume len
works.

Andrew
da***@dalkescientific.com
Jul 18 '05 #29
On Wed, 24 Sep 2003 20:46:16 +0200, rumours say that Peter Otten
<__*******@web.de> might have written:
# let inifinite iterators identify themselves
assert not hasattr(obj, 'infinite')

As infinite iterators are rare, it would not be too cumbersome to let them
identify themselves as such.


This is an interesting idea.
--
TZOTZIOY, I speak England very best,
Microsoft Security Alert: the Matrix began as open source.
Jul 18 '05 #30
> > # let inifinite iterators identify themselves
assert not hasattr(obj, 'infinite')

As infinite iterators are rare, it would not be too cumbersome to let them
identify themselves as such.


It would be quite cumbersome to have to identify simple generators as
infinite or finite manually, and impossible (halting problem) to do so
reliably automatically.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #31
|> >As infinite iterators are rare, it would not be too cumbersome to
|> >let them identify themselves as such.

David Eppstein <ep******@ics.uci.edu> wrote previously:
|It would be quite cumbersome to have to identify simple generators as
|infinite or finite manually, and impossible (halting problem) to do so
|reliably automatically.

Humans cannot solve the halting problem either, FWIW. Just because a
programmer THINKS an iterator is finite, it don't mean it is!

Actually, to my mind, infinite iterators are the RULE not the exception.
Or if not actually infinite, iterators tend to be *indefinitely* large.
That is, I use an iterator because I want to deal with something at
runtime whose size is unbounded at programming time (e.g. an external
file, or data from a socket).

Overall, this makes me -1 on the whole idea of reverse iteration.

Moreover, even iterators that are known to be finite and even of
reasonable size will often be SLOW. For example, I might naturally
write a simple generator to get data from a socket. Each time a block
of data comes in, I take some action based on it. I want those actions
to happen as soon as the relevant chunk of data is available, even
though the socket is probably much slower than the CPU. If my GUI needs
to wait for ALL the data in order to play the event in reverse, that
might cause very uncomfortable pauses in the interface. On the other
hand, if the widget updates every second (even for a couple minutes
total), that seems reasonable enough.

Yours, Lulu...

--
_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY: Postmodern Enterprises _/_/_/
_/_/ ~~~~~~~~~~~~~~~~~~~~[me***@gnosis.cx]~~~~~~~~~~~~~~~~~~~~~ _/_/
_/_/ The opinions expressed here must be those of my employer... _/_/
_/_/_/_/_/_/_/_/_/_/ Surely you don't think that *I* believe them! _/_/
Jul 18 '05 #32
In article <ma**********************************@python.org >,
Lulu of the Lotus-Eaters <me***@gnosis.cx> wrote:
David Eppstein <ep******@ics.uci.edu> wrote previously:
|It would be quite cumbersome to have to identify simple generators as
|infinite or finite manually, and impossible (halting problem) to do so
|reliably automatically.

Humans cannot solve the halting problem either, FWIW. Just because a
programmer THINKS an iterator is finite, it don't mean it is!


Well, true, but if you are a programmer and don't know whether your
program is always going to halt, you probably shouldn't have written it
that way.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #33
Stephen Horne:
I disagree with this. IMO something that modifies a value in place
should be named using a verb (such as reverse, or sort, or update...).


You are correct. And I can't even blame it on lack of sleep. ;)

Andrew
da***@dalkescientific.com
Jul 18 '05 #34
|> Humans cannot solve the halting problem either, FWIW. Just because a
|> programmer THINKS an iterator is finite, it don't mean it is!

David Eppstein <ep******@ics.uci.edu> wrote previously:
|Well, true, but if you are a programmer and don't know whether your
|program is always going to halt, you probably shouldn't have written it
|that way.

Sure, I generally agree. But creating a special __finite__ attribute
(or whatever) introduces a new source of potentially rather bad errors.
Doing a reverse iteration on an iterator that turns out to be infinite
(or even just VERY big) will presumably either freeze the system or
cause a memory overrun.

Moreover, I can see a class of cases where it's not obvious about
halting. A generator that depends on some runtime data might halt for
all the "normal" cases, but wind up running infinitely long for special
(untested) cases. Some attractors, for example, with the right
parameters (or wrong, depending on how you think of it) are strange, if
you know what I mean :-).

Yours, Lulu...

--
mertz@ | The specter of free information is haunting the `Net! All the
gnosis | powers of IP- and crypto-tyranny have entered into an unholy
..cx | alliance...ideas have nothing to lose but their chains. Unite
| against "intellectual property" and anti-privacy regimes!
-------------------------------------------------------------------------
Jul 18 '05 #35
On Wed, 24 Sep 2003 09:57:18 GMT, "Raymond Hettinger"
<vz******@verizon.net> wrote:
Second, I'm not quite ready to drop my property idea ;-)

An advantage is that the object returned by the property can sensibly
support more than just iteration - e.g. slicing (as touched on in the
PEP284 thread). So for instance...
>>> x = range(10)
>>> list(x.backward) [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]


I'm not clear on the details of what you're proposing. What is
type(x.backward)?


Some made-up proxy class that understands that certain operations will
work as if the list was reversed.

For integer lists, I'd use much the same thing but on the
set-of-all-integers object I proposed in the earlier thread. So I
could write...

for i in integers.backwards [:10] :
print i

....to do the same as your...

for i in xrange (10).iter_backwards () :
print i

....though I'm also having this idea about using the 'int' type object
to implement these again. It makes a certain sense for type names to
also act as abstract sets of possible values. For typechecking
purposes, for instance, it might be nice to be able to write...

if x in float :
do stuff with float value

Of course that's a long way from compelling given that we already have
the isinstance function, but what is attracting me is that these two
ideas...

1. Provide objects (or extend the type name objects) to provide
the abstraction of a set of values of that type, implementing
whatever operations are practical and useful for that
abstraction.

2. Provide properties of objects (including that abstract set of
integers) which act as proxies for the object, but providing
an modified view of that object (including a backward view of a
sequence object, but possibly other things too).

....seem to provide, either alone or in combination, natural solutions
to several problems. For instance, you don't just get the ability to
loop through a range of integers backwards...

for i in integers.ibackwards [:50] :

But equally the ability to iterate through a sequence backwards...

for i in x.ibackwards [:50] :

And basically you are doing the same thing in each case - its just
that the first example slices an abstract sequence as opposed to one
that is physically held in memory.
Please show what a pure python version would look like
(taking UserList as an example).


I didn't use UserList, but I did post example code in the "Comment on
PEP-0322: Reverse Iteration Methods" thread. I wasn't so keen in that
post, but I seem to like the idea again now.
>* Should enumerate() be included? It would only provide reverse iteration
> whenever the underlying sequence supported it.


Why not...

for i, j in enumerate (listname.iter_backwards ()) :

in other words, as enumerate can handle the already-reversed
sequence/iteration, I don't see the point.


The point is that enumerate will starting numbering from zero
for the last item:


Yes - I wasn't thinking straight, sorry about that. Just to put a
thought in based on those two ideas above, though, how about...
x=["a", "b", "c"]
print x.enumerated [(0, "a"), (1, "b"), (2, "c")] print x.backwards.enumerated [(0, "c"), (1, "b"), (2, "c")] print x.enumerated.backwards

[(2, "c"), (1, "b"), (0, "c")]

'enumerated' need not create the list or iterator immediately - again,
it returns a proxy which implements the modified behaviour. Having a
proxy to a proxy gives IMO quite a neat solution.
--
Steve Horne

steve at ninereeds dot fsnet dot co dot uk
Jul 18 '05 #36

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

21
by: Headless | last post by:
I've marked up song lyrics with the <pre> tag because it seems the most appropriate type of markup for the type of data. This results in inefficient use of horizontal space due to UA's default...
7
by: Alan Illeman | last post by:
How do I set several different properties for PRE in a CSS stylesheet, rather than resorting to this: <BODY> <PRE STYLE="font-family:monospace; font-size:0.95em; width:40%; border:red 2px...
2
by: Buck Turgidson | last post by:
I want to have a css with 2 PRE styles, one bold with large font, and another non-bold and smaller font. I am new to CSS (and not exactly an expert in HTML, for that matter). Is there a way to...
5
by: Michael Shell | last post by:
Greetings, Consider the XHTML document attached at the end of this post. When viewed under Firefox 1.0.5 on Linux, highlighting and pasting (into a text editor) the <pre> tag listing will...
8
by: Jarno Suni not | last post by:
It seems to be invalid in HTML 4.01, but valid in XHTML 1.0. Why is there the difference? Can that pose a problem when such a XHTML document is served as text/html?
7
by: Rocky Moore | last post by:
I have a web site called HintsAndTips.com. On this site people post tips using a very simply webform with a multi line TextBox for inputing the tip text. This text is encode to HTML so that no...
9
by: Eric Lindsay | last post by:
I can't figure how to best display little snippets of shell script using <pre>. I just got around to organising to bulk validate some of my web pages, and one of the problems occurs with Bash...
23
by: Xah Lee | last post by:
The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully Functional Notations Xah Lee, 2006-03-15 Let me summarize: The LISP notation, is a functional notation, and is not a...
14
by: Schraalhans Keukenmeester | last post by:
I am building a default sheet for my linux-related pages. Since many linux users still rely on/prefer viewing textmode and unstyled content I try to stick to the correct html tags to pertain good...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.