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:

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))

Категории