473,549 Members | 5,201 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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_backw ards():
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 3703
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_backw ards():
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***@dalkescie ntific.com
Jul 18 '05 #2
Overall impression: I like it.
More comments interspersed.

John Roth

"Raymond Hettinger" <vz******@veriz on.net> wrote in message
news:HA******** *******@nwrdny0 3.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_backw ards():
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******@veriz on.net> wrote in message
news:HA******** *******@nwrdny0 3.gnilink.net.. .
for i in xrange(n).iter_ backwards():
print seqn[i]

for elem in seqn.iter_backw ards():
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****@mindspr ing.com> wrote in message
news:hJ******** ********@newsre ad4.news.pas.ea rthlink.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_backw ards():
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***@dalkescie ntific.com
Jul 18 '05 #6
"Raymond Hettinger" <vz******@veriz on.net> wrote in message
news:HA******** *******@nwrdny0 3.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_backw ards():
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).backw ards:
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(iterab le)" (or
ireverse(iterab le)) 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(enumera te(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_han dlers() uses::
while _exithandlers:
func, targs, kargs = _exithandlers.p op()
. . .
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.i ter_backwards() :
. . .
del _exithandlers

* difflib.get_clo se_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.rev erse();
for t in testfolders:
do('mh.deletefo lder(%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(verfi les)-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.ifilt er 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***@dalkescie ntific.com
Jul 18 '05 #9
On Wed, 24 Sep 2003 00:30:31 GMT, "Raymond Hettinger"
<vz******@veriz on.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_backw ards():
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

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

Similar topics

21
10184
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 rendering of <pre> in a fixed width font. To change that I'd have to specify a proportional font family, thereby falling into the size pitfall that...
7
18519
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 solid; color:red;
2
2776
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 do this in CSS? <STYLE TYPE="text/css"> pre{ font-size:xx-large;
5
718
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 preserve formatting (white space and line feeds). However, this is not true when doing the same with the <code> tag listing (it will all be pasted on one...
8
3770
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
2734
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 tags will remain making the page safe (I have to convert the linefeeds to <BR>s because the Server.EncodeHTML does not do that it seems). The...
9
5531
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 shell pieces like this: <pre><code> #!/bin/sh ftp -i -n ftp.server.com&lt; &lt;EOF user username password epsv4 cd /
23
3597
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 so-called pre-fix notation or algebraic notation. Algebraic notations have the concept of operators, meaning, symbols placed around arguments. In...
14
3611
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 readibility on browsers w/o css-support. For important notes, warnings etc I use the <pre> tag, which shows in a neat bordered box when viewed...
0
7455
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7962
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7480
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7814
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
1
5373
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5092
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3486
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1949
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
0
769
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

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.