1. Operating on Iterators

17.13 Operating on Iterators Credit: Sami Hangaslammi

1.1. 问题 Problem

You need to operate on iterators (including normal sequences) with the same semantics as normal sequence operations, except that lazy evaluation is a must, because some of the iterators involved could represent unbounded sequences.

1.2. 解决 Solution

Python 2.2 iterators are easy to handle via higher-order functions, and lazy evaluation (such as that performed by the xrange built-in function) can be generalized. Here are some elementary operations that include concatenating several iterators, terminating iteration when a function becomes false, terminating iteration after the first n values, and returning every nth result of an iterator:

   1 from _ _future_ _ import generators
   2 
   3 def itercat(*iterators):
   4     """ Concatenate several iterators into one. """
   5     for i in iterators:
   6         i = iter(i)
   7         for x in i:
   8             yield x
   9 
  10 def iterwhile(func, iterator):
  11     """ Iterate for as long as func(value) returns true. """
  12     iterator = iter(iterator)
  13     while 1:
  14         next = iterator.next(  )
  15         if not func(next):
  16             raise StopIteration    # or: return
  17         yield next
  18 
  19 def iterfirst(iterator, count=1):
  20     """ Iterate through 'count' first values. """
  21     iterator = iter(iterator)
  22     for i in xrange(count):
  23         yield iterator.next(  )
  24 
  25 def iterstep(iterator, n):
  26     """ Iterate every nth value. """
  27     iterator = iter(iterator)
  28     while 1:
  29         yield iterator.next(  )
  30         # Skip n-1 values
  31         for dummy in range(n-1):
  32             iterator.next(  )

A bit less elementary, but still generally useful, are functions that transform an iterator's output, not just selecting which values to return and which to skip, but actually changing the structure. For example, here is a function that bunches up an iterator's results into a sequence of tuples, each of length count:

   1 from _ _future_ _ import generators
   2 
   3 def itergroup(iterator, count, keep_partial=1):
   4     """ Iterate in groups of 'count' values. If there aren't enough values for
   5     the last group, it's padded with None's, or discarded if keep_partial is
   6     passed as false. """
   7     iterator = iter(iterator)
   8     while 1:
   9         result = [None]*count
  10         for x in range(count):
  11             try: result[x] = iterator.next(  )
  12             except StopIteration:
  13                 if x and keep_partial: break
  14                 else: raise
  15         yield tuple(result)

And here are generalizations to lazy evaluation of the non-lazy existing built-in Python functions zip, map, filter, and reduce:

   1 from _ _future_ _ import generators
   2 
   3 def xzip(*iterators):
   4     """ Iterative (lazy) version of built-in 'zip' """
   5     iterators = map(iter, iterators)
   6     while 1:
   7         yield tuple([x.next(  ) for x in iterators])
   8 
   9 def xmap(func, *iterators):
  10     """ Iterative (lazy) version of built-in 'map'. """
  11     iterators = map(iter, iterators)
  12     count = len(iterators)
  13     def values(  ):
  14         # map pads shorter sequences with None when they run out of values
  15         result = [None]*count
  16         some_ok = 0
  17         for i in range(count):
  18             if iterators[i] is not None:
  19                 try: result[i] = iterators[i].next(  )
  20                 except StopIteration: iterators[i] = None
  21                 else: some_ok = 1
  22         if some_ok: return tuple(result)
  23         else: raise StopIteration
  24     while 1:
  25         args = values(  )
  26         if func is None: yield args
  27         else: yield func(*args)
  28 
  29 def xfilter(func, iterator):
  30     """ Iterative version of built-in 'filter' """
  31     iterator = iter(iterator)
  32     while 1:
  33         next = iterator.next(  )
  34         if func(next):
  35             yield next
  36 
  37 def xreduce(func, iterator, default=None):
  38     """ Iterative version of built-in 'reduce' """
  39     iterator = iter(iterator)
  40     try: prev = iterator.next(  )
  41     except StopIteration: return default
  42     single = 1
  43     for next in iterator:
  44         single = 0
  45         prev = func(prev, next)
  46     if single:
  47         return func(prev, default)
  48     return prev

1.3. 讨论 Discussion

This recipe is a collection of small utility functions for iterators (all functions can also be used with normal sequences). Among other things, the module presented in this recipe provides generator (lazy) versions of the built-in sequence-manipulation functions. The generators can be combined to produce a more specialized iterator. This recipe requires Python 2.2 or later, of course.

The built-in sequence-manipulation functions zip, map, and filter are specified to return sequences (and the specifications cannot be changed for backward compatibility with versions of Python before 2.2, which lacked iterators); therefore, they cannot become lazy. However, it's easy to write lazy iterator-based versions of these useful functions, as well as other iterator-manipulation functions, as exemplified in this recipe.

Of course, lazy evaluation is not terribly useful in certain cases. The semantics of reduce, for example, require that all of the sequence is evaluated anyway. While in some cases one could save some memory by looping through the sequence that the iterator yields, rather than expanding it, most often it will be more practical to use reduce(func, iterator) instead of the xreduce function presented in this recipe.

Lazy evaluation is most useful when the resulting iterator-represented sequence is used in contexts that may be able to use just a reasonably short prefix of the sequence, such as the zip function and the iterwhile and iterfirst functions in this recipe. In such cases, lazy evaluation enables free use of unbounded sequences (of course, the resulting program will terminate only if each unbounded sequence is used only in a context in which only a finite prefix of it is taken) and sequences of potentially humungous length.

1.4. 参考 See Also

PyCkBk-17-11--Recipe 17.11 and PyCkBk-17-12--Recipe 17.12 for other uses of iterators.