Re: 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


--
http://mail.python.org/mailman/listinfo/python-list