[Edu-sig] Some design patterns with iterators

[Kirby Urner]

The construct:

for i in collection:
    do something with i

is extremely common.  The collection is most simply a list or tuple,
but may in fact be any iterable object.  So the construct might be
rewritten:

for i in iterable:              # construct (1)
    do something with i

But how do we ensure that this is not an infinite loop?  I.e. the
collection returned by iterable may be inherently open-ended, e.g.
the sequence of fibonacci numbers 1 1 2 3 5 8 13...

A common modification to deal with such cases is:

for i in iterable:              # construct (2)
    if test(i): break
    do something with i

An alternative to the above is to return to the original construct (1),
but have the iterable become self-terminating.  The syntax:

iterable = iter(obj,sentinel)

uses the builtin iter() to compare a callable to a sentinel, and
stops iterating when they match.  So lets define an object that
returns the next fibonacci number whenever called, and which
internalizes a test, which, if positive, will return the sentinel
value:

----
# iters.py

class Fib(object):
     def __init__(self,start=0,next=1,test=False,sentinel=-1):
         self.start    = start
         self.next     = next
         self.sentinel = sentinel
         self.test     = test
     def __call__(self):
         self.start,self.next = self.next, self.start + self.next
         if self.test(self.start): return self.sentinel
         return self.start

def t(x):
     """x > 1000"""
     return x > 1000

fibobj = Fib(test=t)
iterable = iter(fibobj,-1)
for i in iterable:
    print i,
----

If you run the above script you'll get a listing of Fibonacci numbers less than
or equal to 1000:

Sun 03/30/2003 11:57:21.79
D:\Program Files\Python22>python ./work/iters.py
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Why go to all the trouble of passing in a test function, if we can simply set
a sentinel value to abort iteration?  The Fibonacci example suggests the 
answer:
we don't know in advance exactly what the collection will be (or think of
prime numbers), so we're not in a position to use a simple value to abort
iteration -- we need something like a comparison, or a more complicated set
of criteria, which is why we pass in a test.

A callable object, turned into an iterator by way of iter(), behaves much the
same as a generator object -- which objects may be functions.  The Fib object
might be rewritten as a generator, still accepting a test function as a
parameter:

  >>> def fibfunc(test):
         data = [1,1]
         while not test(data[0]):
            yield data[0]
            data[0],data[1] = data[1],data[0]+data[1]
         return

  >>> iterable = fibfunc(t)  # t is a test function
  >>> for i in iterable: print i,

  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

In this case, fibfunc automatically returns an iterable.

What is the advantage of passing a test into an iterable, versus simply going
with construct (2)?   From a readability point of view, this approach has the
advantage of binding the test to the iterable at the time of definition.  The
same for-loop might handle lots of iterators, and needn't worry about which 
test
to use.  The test logically belongs with the iterator.

For example, let's modify iters.py (keeping original Fib object intact):

----
def testfunc(max):
     """a factory for test functions"""
     def t(x):
         return x > max
     t.__doc__ = "stop when x > %s" % max
     return t

t1 = testfunc(1000)
t2 = testfunc(5000)

def looper(iterable):
     # generic loop, doesn't worry about when to break
     for i in iterable:
         print i,
     print

print t1.__doc__
looper(iter(Fib(test=t1),-1))
print t2.__doc__
looper(iter(Fib(test=t2),-1))
----

  >>> reload(iters)
  stop when x > 1000
  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
  stop when x > 5000
  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
  <module 'iters' from 'D:\Program Files\Python22\work\iters.py'>

In this case, the same test functions will work with the generator version.
Example:

  >>> iterable = fibfunc(t2)
  >>> for i in iterable: print i,

  1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181


--- Kirby