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