Iterator / Iteratable confusion

[Michael Spencer]

Francis Girard wrote:
> """
> ================================================================================
> Example 8
> ================================================================================
> Running after your tail with itertools.tee
> 
> 
> The beauty of it is that recursive running after their tail FP algorithms
> are quite straightforwardly expressed with this Python idiom.
> """
> 
> def Ex8_Fibonacci():
>   print "Entering Ex8_Fibonacci"
>   def _Ex8_Fibonacci():
>     print "Entering _Ex8_Fibonacci"
>     yield 1
>     yield 1
>     fibTail.next() # Skip the first one
>     for n in (head + tail for (head, tail) in izip(fibHead, fibTail)):
>       yield n
>   fibHead, fibTail, fibRes = tee(_Ex8_Fibonacci(), 3)
>   return fibRes
>   
> print
> print sEx8Doc
> print
> print list(islice(Ex8_Fibonacci(), 5))
> 
Absolutely: ever since you brought up the Hamming sequence I've been interested 
in this approach.  However, if iterators could be extended in place, these 
solutions would be even more attractive.

Here are some examples for infinite series constructed with an extendable 
iterator.  This iterator is returned by an iterable class 'Stream', shown below 
the examples:

def factorial():
     """
     >>> f = factorial()
     >>> f.tolist(10)
     [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
     """

     factorial = Stream([1])
     factorial.extend(factorial * it.count(1))

     return factorial

def fib():
     """Example:
     >>> f = fib()
     >>> f.tolist(10)
     [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"""
     fib = Stream([1,1])
     fib.extend(x+y for x, y in it.izip(fib, fib[1:]))
     return fib



def multimerge(*iterables):
     """Yields the items in iterables in order, without duplicates"""
     cache = {}
     iterators = map(iter,iterables)
     number = len(iterables)
     exhausted = 0
     while 1:
         for it in iterators:
             try:
                 cache.setdefault(it.next(),[]).append(it)
             except StopIteration:
                 exhausted += 1
                 if exhausted == number:
                     raise StopIteration
         val = min(cache)
         iterators = cache.pop(val)
         yield val

def hamming():
     """
     Example:
     >>> h = hamming()
     >>> list(h[20:40])
     [40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125, 
128, 135, 144]
     >>> h[10000]
     288555831593533440L
     """

     hamming = Stream([1])
     hamming.extend(i for i in multimerge(2 * hamming, 3 * hamming, 5 * hamming))
     return hamming


def compounds():
     """Extension of Hamming series to compounds of primes(2..13)
     Example:
     >>> c = compounds()
     >>> list(c[20:30])
     [24, 25, 26, 27, 28, 30, 32, 33, 35, 36]"""
     compounds = Stream([1])
     compounds.extend(i for i in multimerge(2 * compounds, 3 * compounds, 5 * 
compounds, 7 * compounds, 9 * compounds, 11 * compounds, 13 * compounds))
     return compounds


# Stream class for the above examples:

import itertools as it
import operator as op

class Stream(object):
     """Provides an indepent iterator (using tee) on every iteration request
         Also implements lazy iterator arithmetic"""

     def __init__(self, *iterables, **kw):
         """iterables: tuple of iterables (including iterators).  A sequence of
         iterables will be chained
         kw: not used in this base class"""
         self.queue = list(iterables)
         self.itertee = it.tee(self._chain(self.queue))[0] # We may not need 
this in every case

     def extend(self,other):
         """extend(other: iterable) => None
             appends iterable to the end of the Stream instance
         """
         self.queue.append(other)

     def _chain(self, queue):
         while queue:
             for i in self.queue.pop(0):
                 self.head = i
                 yield i

     # Iterator methods:

     def __iter__(self):
         """Normal iteration over the iterables in self.queue in turn"""
         return self.itertee.__copy__()

     def _binop(self,other,op):
         """See injected methods - __add__, __mul__ etc.."""
         if hasattr(other,"__iter__"):
             return (op(i,j) for i, j in it.izip(self,other))
         else:
             return (op(i,other) for i in self)

     def __getitem__(self,index):
         """__getitem__(index: integer | slice)
         index: integer => element at position index
         index: slice
             if slice.stop is given => Stream(it.islice(iter(self),
                         index.start, index.stop, index.step or 1)))
             else: consumes self up to start then => Stream(iter(self))
                 Note slice.step is ignored in this case
         """
         if isinstance(index, slice):
             if index.stop:
                 return (it.islice(iter(self),
                         index.start or 0, index.stop, index.step or 1))
             else:
                 iterator = iter(self)
                 for i in range(index.start):
                     iterator.next()
                 return iterator
         else:
             return it.islice(iter(self), index,index+1).next()

     def getattr(self,attrname):
         """__getattr__/getattr(attrname: string)
         => Stream(getattr(item,attrname) for item in self)
         Use the getattr variant if the attrname is shadowed by the Stream class"""

         return (getattr(item,attrname) for item in self)
     __getattr__ = getattr


     # Representational methods

     def tolist(self, maxlen = 100):
         return list(it.islice(iter(self),maxlen))

     def __repr__(self):
         return "Stream instance at:%x: %s" % (id(self),
         repr(self.queue))


# Inject special methods for binary operations:
_binopdoc = """%(func)s(other: constant | iterable, op: binary function)
         other: constant => Stream(op.%(op)s(i,other) for i in self))
         other: iterable => Stream(op.%(op)s(i,j) for i, j in it.izip(self,other))
         """

[setattr(Stream,attr, func(argspec = "self, other",
                             expr = "self._binop(other, op.%s)" % opfunc,
                             doc=_binopdoc % {"func":attr, "op":opfunc},
                             name=attr)
         )
         for attr, opfunc in {
                             "__mul__":"mul",
                             "__add__":"add",
                             "__sub__":"sub",
                             "__div__":"div",
                             "__mod__":"mod",
                             "__pow__":"pow",
                             }.items()
]
# End inject special methods