20.7. 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 20-21 is a first attempt at two simple reversal functions.
Example 20-21. PP3E\Dstruct\Classics\rev1.py
Both reversal functions work correctly on lists. But if we try reversing nonlist sequences (strings, tuples, and so on) 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 nonlistsit 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, 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 20-22 fix both problems by using generic sequence handling techniques:
Example 20-22. PP3E\Dstruct\Classics\rev2.py
These functions work on any sequence, and they 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 leneven 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))