root/python/cybertrain/trunk/ch18/README.txt

====================================
Chapter 18: Iterators and Generators
====================================


Iterators
=========

An iterator is a general object that provides values one by one
in a series. In this sense a simple list or tuple may act as an
iterator.

  >>> for element in ('a', 'b', 'c'):
  ...     print element
  a
  b
  c

But the iterator represents a more general case of sequential
access to objects - without the need toload all the values into
memory.

All objects that basically provide sequential access may be
converted to an iterator using the ``iter`` function.

  >>> iterator = iter(('a', 'b', 'c'))
  >>> for element in iterator:
  ...     print element
  a
  b
  c

The characteristic element of an iterator is the method ''next()''.

  >>> dir(iterator)
  [..., 'next']
  >>> iterator.next()
  Traceback (most recent call last):
  ...
  StopIteration

What's that?

With the above ``for`` loop we have already exhausted the
iterator, so we have to create a new one.

  >>> iterator = iter(('a', 'b', 'c'))
  >>> iterator.next()
  'a'
  >>> iterator.next(), iterator.next()
  ('b', 'c')
  >>> iterator.next()
  Traceback (most recent call last):
  ...
  StopIteration

So the ``for`` loop just calls ``next()`` repeatedly until
the ``StopIteration`` exception is raised.

Iterable and iterator classes
-----------------------------

We can create an iterable object by providing the special
method ``__iter__()`` that will be called when the ``iter()``
function is called and should return an iterator.

  >>> class Iter1(object):
  ...     data = ('a', 'b', 'c')
  ...     def __iter__(self):
  ...         return iter(self.data)

A ``for`` loop checks if its target is iterable, i.e.
if an iterator can be derived from it.

  >>> for x in Iter1():
  ...     print x
  a
  b
  c

By defining the ``next()`` method we can directly create
an iterator.

  >>> class Iter2(object):
  ...     char = 'a'
  ...     def next(self):
  ...         char = self.char
  ...         if char > 'c':
  ...             raise StopIteration
  ...         self.char = chr(ord(char) + 1)
  ...         return char

The ``for`` loop now just calls the ``next()`` method
repeatedly.

  >>> for x in Iter1():
  ...     print x
  a
  b
  c

The ``Iter2`` class is especially interesting because it does
never create the full list of values that it provides but delivers
them one by one upon request. Thus the number of values it provides
may be arbitrarily large.

With Python 2.3 iterators can be created using a special type
of function - a generator...


Generators
==========

A generator is a function that does not ``return`` a value but
instead ``yield``s one or more values.

  >>> def greeting():
  ...     yield 'Hello'
  ...     yield 'World'

  >>> greeting
  <function greeting ...>

  >>> greeting()
  <generator object ...>

  >>> for x in greeting():
  ...     print x
  Hello
  World

Typically the ``yield`` statement is executed in a loop thus
showing the usual behaviour of an iterator.

  >>> def characters1():
  ...     char = 'a'
  ...     while char <= 'c':
  ...         yield char
  ...         char = chr(ord(char) + 1)

  >>> list(characters1())
  ['a', 'b', 'c']

A ``for`` loop may be even more compact than  a ``while`` loop.

  >>> def characters2():
  ...     for i in xrange(ord('a'), ord('d')):
  ...         yield chr(i)

  >>> list(characters2())
  ['a', 'b', 'c']

Such a generator is just a special case of an iterator - it just
provides the ``next()`` method.

  >>> generator = characters2()
  >>> generator.next()
  'a'
  >>> generator.next(), generator.next()
  ('b', 'c')
  >>> generator.next()
  Traceback (most recent call last):
  ...
  StopIteration

Excercise
---------

Write a generator that provides the Fibonacci sequence.

  >>> from cybertrain.work.work181 import fibogen
  >>> for i, fibo in enumerate(fibogen()):
  ...     if i > 6:
  ...         break
  ...     print fibo,
  0 1 1 2 3 5 8


Generator Expressions
=====================

In Chapter 9 we already met list comprehensions, a simple but
powerful construct to transform and filter a sequence of values.

We can use a list comprehension to calculate the sum of the
squares of the numbers up to 100.

  >>> squares = [i * i for i in xrange(101)]
  >>> sum(squares)
  338350

Note that this way the full list of all the numbers is created
in memory.

  >>> len(squares)
  101
  >>> squares[0]
  0
  >>> squares[-1]
  10000

This is also the case if we put everything into one expression.

  >>> sum([i * i for i in xrange(101)])
  338350

We can avoid the allocation of memory for all the numbers by
using a generator expression instead of a list comprehension.
A generator expression looks like a list comprehension but
is enclosed in parentheses.

  >>> squares = (i * i for i in xrange(101))
  >>> sum(squares)
  338350

  >>> squares
  <generator object ...>

This way one number after the other is requested from the
generator by the ``sum()`` function using the generator's
``next()`` method, thus the whole list of numbers is not
created.

When using a generator expression as the only argument in
a function call we can omit the extra parentheses.

  >>> sum(i * i for i in xrange(101))
  338350

Caveat!
-------

As any iterator a generator expression will be exhausted when
once iterated over so we have to recreate it.

  >>> len(list(squares))
  0
  >>> squares = (i * i for i in xrange(101))
  >>> len(list(squares))
  101

If a certain iterator is to be used multiple times we can
use the ``tee()`` function from the ``itertools`` module.


The ``itertools`` Module
========================

See section 6.5 of the Python library reference.

The ``itertools`` module provides a set of handy functions
for creating, processing, and filtering iterators without
having to create full lists.

These functions are especially useful when you have to deal
with a large number of object, e.g. like database records
or even infinite sequences.

Let's just look at two of them.

tee - duplicate an iterator
---------------------------

  >>> from itertools import tee

  >>> sq1, sq2 = tee(i * i for i in xrange(101))
  >>> sq1, sq2
  (<itertools.tee object ...>, <itertools.tee object ...>)

  >>> sum(sq1)
  338350
  >>> len(list(sq2))
  101

islice - take a slice from an iterator
--------------------------------------

  >>> from itertools import islice

  >>> fibo30to35 = islice(fibogen(), 30, 36)
  >>> fibo30to35
  <itertools.islice object ...>

  >>> list(fibo30to35)
  [832040, 1346269, 2178309, 3524578, 5702887, 9227465]

Excercise
---------

Write a function that returns the nth Fibonacci number
using the fibogen and islice functions.

  >>> from cybertrain.work.work181 import fibonacci
  >>> fibonacci(7)
  13