Reversing Sequences

Reversal of collections is another typical operation. We can code it either recursively or iteratively in Python, and as functions or class methods. Example 17-21 is a first attempt at two simple reversal functions.

Example 17-21. PP2EDstructClassics ev1.py

def reverse(list): # recursive
 if list == []:
 return []
 else:
 return reverse(list[1:]) + list[:1]

def ireverse(list): # iterative
 res = []
 for x in list: res = [x] + res
 return res

Both reversal functions work correctly on lists. But if we try reversing nonlist sequences (strings, tuples, etc.) we're in trouble: the ireverse function always returns a list for the result regardless of the type of sequence passed:

>>> ireverse("spam")
['m', 'a', 'p', 's']

Much worse, the recursive reverse version won't work at all for nonlists -- it gets stuck in an infinite loop. The reason is subtle: when reverse reaches the empty string (""), it's not equal to the empty list ([]), so the else clause is selected. But slicing an empty sequence returns another empty sequence (indexes are scaled): the else clause recurs again with an empty sequence, and without raising an exception. The net effect is that this function gets stuck in a loop, calling itself over and over again until Python runs out of memory.

The versions in Example 17-22 fix both problems by using generic sequence handling techniques:

  • reverse uses the not operator to detect the end of the sequence and returns the empty sequence itself, rather than an empty list constant. Since the empty sequence is the type of the original argument, the + operation always builds the correct type sequence as the recursion unfolds.
  • ireverse makes use of the fact that slicing a sequence returns a sequence of the same type. It first initializes the result to the slice [:0], a new, empty slice of the argument's type. Later, it uses slicing to extract one-node sequences to add to the result's front, instead of a list constant.

Example 17-22. PP2EDstructClassics ev2.py

def reverse(list):
 if not list: # empty? (not always [])
 return list # the same sequence type
 else:
 return reverse(list[1:]) + list[:1] # add front item on the end

def ireverse(list):
 res = list[:0] # empty, of same type
 for i in range(len(list)): 
 res = list[i:i+1] + res # add each item to front
 return res

These functions work on any sequence, and return a new sequence of the same type as the sequence passed in. If we pass in a string, we get a new string as the result. In fact, they reverse any sequence object that responds to slicing, concatenation, and len -- even instances of Python classes and C types. In other words, they can reverse any object that has sequence interface protocols. Here they are working on lists, strings, and tuples:

% python
>>> from rev2 import *
>>> reverse([1,2,3]), ireverse([1,2,3])
([3, 2, 1], [3, 2, 1])
>>> reverse("spam"), ireverse("spam")
('maps', 'maps')
>>> reverse((1.2, 2.3, 3.4)), ireverse((1.2, 2.3, 3.4))
((3.4, 2.3, 1.2), (3.4, 2.3, 1.2))

Introducing Python

Part I: System Interfaces

System Tools

Parallel System Tools

Larger System Examples I

Larger System Examples II

Part II: GUI Programming

Graphical User Interfaces

A Tkinter Tour, Part 1

A Tkinter Tour, Part 2

Larger GUI Examples

Part III: Internet Scripting

Network Scripting

Client-Side Scripting

Server-Side Scripting

Larger Web Site Examples I

Larger Web Site Examples II

Advanced Internet Topics

Part IV: Assorted Topics

Databases and Persistence

Data Structures

Text and Language

Part V: Integration

Extending Python

Embedding Python

VI: The End

Conclusion Python and the Development Cycle



Programming Python
Python Programming for the Absolute Beginner, 3rd Edition
ISBN: 1435455002
EAN: 2147483647
Year: 2000
Pages: 245

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net