//
you're reading...
Uncategorized

Python’s iterables and generators

Here is a short introduction to the Python’s iterables and related generator functions, which the use of the idioms of yield/next.

First we look “under the hood” of a “for” statement in Python, which can be used with any iterable object. Language-defined iterable objects in Python include lists, tuples, strings, dicts, and files. You can always use a “for loop” over an iterable object as follows.

for i in iterable:
    print i,

Many functions consume iterable objects:

• Reductions: sum(s), min(s), max(s)

• Constructors: list(s),tuple(s),set(s), dict(s)

• Boolean operator in: if item in s

Any object that supports two functions __iter()__ and next() is said to be “iterable.” Iterables do not have to perform their own iteration. To take a very simple case, list objects are iterables but not iterators. That is, they define an __iter__() method, but not a next() method. Rather than returning the list itself, __iter__() returns a listiterator object.

items = [1, 4, 5]
it = iter(items)
it.next() #=> 1
it.next() #=> 4
it.next() #=> 5
it.next() #=> Traceback (most recent call last):
          #    File "", line 1, in
          #     StopIteration

User-defined objects can support iteration. Here is an example of a “fibonacci” iterable.

for x in Fib(100):
   print x,

#=> 0 1 1 2 3 5 8 13 21 34 55 89

To do this, you just have to implement __iter__() and next() methods. Here is the classic Fibonacci numbers implemented as a iterable or iterator type.

class Fib:
'''iterator that yields numbers in the Fibonacci sequence'''

def __init__(self, max):
    self.max = max

def __iter__(self):
    self.a = 0;  self.b = 1
    return self

def next(self):
   fib = self.a
   if fib > self.max:
       raise StopIteration
   self.a, self.b = self.b, self.a + self.b
   return fib

From Iterables to Generators

Generators differ only slightly from iterable type objects as they are functions, and therefore provides cleaner modes of expression. Calling a generator function creates an generator object. However, it  does not start running the function until a next() call is made. Like  iterables, this syntax lends itself to be used in a natural way with  “for” statements.

Generators work off the “yield” construct which  suspends the state of the function, and is continued from precisely that point when the generator.next() is called. This call of the next() method is done automatically and behind the scenes of a for statement.

def countdown(n):
    print "Counting down from", n
    while n > 0:
       yield n
       n -= 1

for i in countdown(3):
   print i,

#=>Counting down from 3
#  3 2 1

x = countdown(10)
x #=> generator object at 0x163e418;
x.next()
#=> Counting down from 10
#   10
x.next()
#   9

In the definition of a generator the operator “yield” produces a  value, but suspends the function and its state. The function resumes on  next call to next(). If the function ends then an exception is thrown. “For loop”  handle such exceptions easily. Here are some example simple generators.

#The classic Fibonacci sequence as a generator
def all_fibs():
   a, b = 0, 1
   while 1:
      yield b
      a, b = b, a+b

for i in all_fibs():
  print i,

#=> 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025

Since generators are functions, they are amenable to the use of recursion in their definition. We will often make use of the recursive partition tree of the object to help us create correct generators.

We now define a generator that produces all bitstrings of length n, recursively.

The base case is when n==1, and the generator produces all bitstrings by  appending first a 0, then a 1, to each generated bitstring of length n-1. Note that the generator will produce a listing of all bitstrings in lexicographic order.

def all_bitstrings(n):
if n >= 1:
    for sub in all_bitstrings(n-1):
        yield sub + '0'
        yield sub + '1'
    else:
        yield ''

for b in all_bitstrings(5):
   print b,

# 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111
# 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

Recall that we can generate all functions from k items to n items using a simple partition tree. This defines a recursion function for generating all functions from k to n.


def all_fun(n,k):
    if n==0 or k==0:
        return
    if k ==1:
        for i in range(1,n+1):
            yield [i]
    else:
        for i in range(1,n+1):
            for d in all_fun(n,k-1):
                yield [i] + d
# Recall the partition tree for all subsets of a given set,
# or all substrings of a given string as follows.

def all_subsets(str):
    if len(str) < 1:
        yield str
    else:
        for sub in all_subsets(str[1:]):
            yield str[0:1] + subset
            yield subset

for s in all_subsets(['a','b','c','d']):
   print s,

#['a', 'b', 'c', 'd'] ['b', 'c', 'd'] ['a', 'c', 'd'] ['c', 'd'] ['a', 'b', 'd'] ['b', 'd']
# ['a', 'd'] ['d'] ['a', 'b', 'c'] ['b', 'c'] ['a', 'c'] ['c'] ['a', 'b'] ['b'] ['a'] []
for s in all_subsets("abcd"):
    print s,

# abcd bcd acd cd abd bd ad d abc bc ac c ab b a
[/sourcecode]

We end with a look at generating all decreasing functions from set k_ to the set n_, that is k-tuples of integers from 1 to n that are decreasing. A simple recursive generator is given by first generating all k-tuples from 1 to n-1, then followed by k-tuples that begin with n concatenated with decreasing k-1-tuples from 1 to n-1. Note that the definition will yield functions in lexicographic order. Here is the generator function:



def all_dec(n,k):
    if n==0 or k==0:
        return
    if k ==1:
        for i in range(1,n+1):
            yield [i]
    else:
        if k <= n:
            for d in all_dec(n-1,k):
                 yield d
            for d in all_dec(n-1,k-1):
                 yield [(n)]+ d

for d in all_dec(4,3):
   print d,

#[3, 2, 1] [4, 2, 1] [4, 3, 1] [4, 3, 2]
Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: