# Iterators, Generators and Lazy Evaluation

### 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):
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)