1. How iterators work

When Python loops through an object, what happens is:

1. The for statement calls iter() on the object, returning an iterator
2. This iterator has  a __next__() method which accesses the elements in the object
3. When there are no more objects, __next__() raises a StopIteration exception

>>> s = 'abc'
>>> it = iter(s)
>>> it
<iterator object at 0x00A1DB50>
>>> next(it)
'a'
>>> next(it)
'b'
>>> next(it)
'c'
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
    next(it)
StopIteration

2. Creating an iterator

Define an __iter__() method which returns an object with a __next__() method. (Here it retuns self since the class itself defines __next__().

class Reverse:
    def __init__(self, data):
        self.data = data
        self.index = len(data)

    def __iter__(self):
        return self

    def __next__(self):
        if self.index == 0:
            raise StopIteration

        self.index = self.index - 1
        return self.data[self.index]

rev = Reverse('lol')
for char in rev:
    print(char)

3. Creating an iterator using generators

A generator is a function that returns stuff before it is finished (using yield), and can be resumed from where they left off (using next), until it hits StopIteration

Some examples:

>>> def myGen(n):
...     yield n + 1
...     yield n + 2
... 
>>> g = myGen(0)
>>> next(g)
1
>>> next(g)
2
>>> next(g)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Looping through all natural numbers:

>>> def infinite():
...     i = 0
...     while True:
...         yield i
...         i += 1

The same code for reversing a string as before

def reverse(data):
    for index in range(len(data)-1, -1, -1):
        yield data[index]

4. Generator expressions

Generator expressions is much like list comprehensions, but the object is evaluated when it is needed and not when it is created.

gen = (x for x in range(999999))

This saves a ton of memory, since it doesn’t create the whole list upfront.

5. Generator VS generator expressions

They are basically the same thing. Trivia example:

# generator
def uc_gen(text):
    for char in text:
        yield char.upper()

# generator expression
def uc_genexp(text):
    return (char.upper() for char in text)

6. Lazy evaluation, or why do I need generators

Lazy evaluation is an evaluation strategy which delays the evaluation of an expression until its value is needed.
Typical useage: I have to compute a large set of results but I don’t know if I’m going to need them all; or maybe I just don’t want to allocate the memory for all the results at the same time; I have a function that takes long time to execute (think search on a huge domain) and I want to show intermediate results while I get them, instead of waiting for the search to be over.

7. Using generators to loop through a linked list

def looper(self):
    n = self.head
    while n is not None:
        yield n
        n = n.next

# how cool is that?
x = [ n.value for n in l.looper() if n.value > 10 ]

8. Using generators to do a inorder() traversal of a BST

# Python 2
def inorder(t):
    if t:
        for key in inorder(t.left):
            yield key
        yield t.key
        for key in inorder(t.right):
            yield key

Python 3 adds some neat syntax:

# Python 3
def inorder(t):
    if t:
        yield from inorder(t.left)
        yield t.key
        yield from inorder(t.right)