Iterator Pattern

CHAPTER 13 Iterator Pattern

e wheels of the bus go round and round, round and round, round and round

Data structures and algorithms form an integral part of the software design and development process. Often, different data structures have different uses, and using the right data structure for a specific problem might mean a lot less work and a lot more efficiency. Choosing the correct data structure and matching it with the relevant algorithm will improve your solution.

Since data structures have different implementations, we are tempted to implement the algorithms that operate on them differently. For instance, if we were to consider a binary tree that looks something like this:

class Node(object):

def __init__(self, data):

self.data = data self.left = None self.right = None

traversing the elements of the tree to make sure you visit each one might look something like this:

class Node(object):

def __init__(self, data):

self.data = data self.left = None self.right = None

def tree_traverse(node):

if node.left is not None:

tree_traverse(node.left)

203

' Wessel Badenhorst 2017

W. Badenhorst, Practical Python Design Patterns, https://doi.org/10.1007/978-1-4842-2680-3_13
CHAPTER 13 ITERATOR PATTERN

print(node.data)

if node.right is not None:

tree_traverse(node.right)

if __name__ == "__main__":

root = Node("i am the root")

root.left = Node("first left child") root.right = Node("first right child")

root.left.right = Node("Right child of first left child of root") tree_traverse(root)

Contrast this to when you want to traverse a simple list:

lst = [1, 2, 3, 4, 5]

for i in range(len(lst)):

print(lst[i])

I know I used the for loop in a way that is not considered pythonic, but if you come from a C/C++ or Java background, this will look familiar. I do this because I want to illustrate how you could traverse a list and a binary tree and how they are distinctly different processes that produce a similar result.

Alexander Stepanov, advocate of generic programming and as the primary designer and implementer of the C++ Standard Template Library, spent a lot of time thinking about the techniques of generic programming, where the code is written in terms of algorithms that operate on data types to be defined at some future time. He married ideas from pure mathematics and algebra with computer science and concluded that most algorithms can be defined in relation to an algebraic data type called containers.

By decoupling the algorithm from the specific type and implementation of a container, you become free to describe the algorithm without paying any attention to the actual implementation details of the specific type of container. The result of this decoupling is more general, more reusable code.

We want to be able to traverse a collection without worrying about whether we are dealing with a list or a binary tree or some other collection.

To do this, we want to create an interface that a collection data type can inherit, which would allow it to generalize the action of traversing the contents of the collection. We do this by using the following components.

204
CHAPTER 13 ITERATOR PATTERN

First, we define an interface that defines a function that gets the next item in the collection, and another function to alert some external function that there are no more elements left in the collection to return.

Second, we define some sort of object that can use the interface to traverse the collection. This object is called an iterator.

Following the traditional approach, we can implement this idea as follows:

classic_iter.py

import abc

class Iterator(metaclass=abc.ABCMeta):

@abc.abstractmethod def has_next(self): pass

@abc.abstractmethod

def next(self): pass

class Container(metaclass=abc.ABCMeta):

@abc.abstractmethod def getIterator(self): pass

class MyListIterator(Iterator):

def __init__(self, my_list):

self.index = 0 self.list = my_list.list

def has_next(self):

return self.index < len(self.list)

def next(self):

self.index += 1

return self.list[self.index - 1]

class MyList(Container):

def __init__(self, *args):

self.list = list(args)

205
CHAPTER 13 ITERATOR PATTERN

def getIterator(self):

return MyListIterator(self)

if __name__ == "__main__":

my_list = MyList(1, 2, 3, 4, 5, 6) my_iterator = my_list.getIterator()

while my_iterator.has_next(): print(my_iterator.next())

This prints out the following result:

1 2 3 4 5 6

This idea of traversing some collection is so widespread that it has a name the iterator pattern.

Python Internal Implementation of the Iterator Pattern

As you have probably guessed by now, Python makes implementing the iterator pattern extremely simple. In fact, you have used iterators already in this book. The way for loops are implemented in Python uses the iterator pattern.

Take, for instance, this for loop:

for i in range(1, 7): print(i)

This is analogous to the iterator pattern implementation we saw in the previous

section.

This convenience in Python is accomplished by defining an iterator protocol that is used to create objects that are iterable and then returning some object that knows how to iterate over these iterable objects.

206
CHAPTER 13 ITERATOR PATTERN

Python uses two specific method calls and one raised exception to provide the iterator functionality throughout the language.

The first method of an iterable is the __iter__() method, which returns an iterator object. Next, a __next__() method must be provided by the iterator object; it is used to return the next element in the iterable. Lastly, when all the elements have been iterated over, the iterator raises a StopIteration exception.

We often see the iterable collection in Python return an instance of itself, given that the class in question also implements the __next__() method and raises the StopIteration exception. An iterator similar to the classic implementation we looked at before might look something like this:

class MyList(object):

def __init__(self, *args):

self.list = list(args) self.index = 0

def __iter__(self):

return self

def __next__(self):

try:

self.index += 1

return self.list[self.index - 1] except IndexError:

raise StopIteration()

if __name__ == "__main__":

my_list = MyList(1, 2, 3, 4, 5, 6)

for i in my_list:

print(i)

This time, you will notice that we used the Python for loop to iterate over the elements in the list, which is only possible because our MyList class has the functions required by the Python iterator protocol.

207
CHAPTER 13 ITERATOR PATTERN

If we were to implement the binary tree we saw at the beginning of this chapter as a Python iterable, it would be implemented as follows:

bin_tree_iterator.py

class Node(object):

def __init__(self, data):

self.data = data self.left = None self.right = None

class MyTree(object):

def __init__(self, root):

self.root = root

def add_node(self, node):

current = self.root

while True:

if node.data <= current.data: if current.left is None:

current.left = node return

else:

current = current.left

else:

if current.right is None:

current.right = node return

else:

current = current.right

def __iter__(self):

if self.root is None:

self.stack = [] else:

self.stack = [self.root] current = self.root

208
CHAPTER 13 ITERATOR PATTERN

while current.left is not None:

current = current.left self.stack.append(current)

return self

def __next__(self):

if len(self.stack) <= 0:

raise StopIteration

while len(self.stack) > 0:

current = self.stack.pop() data = current.data

if current.right is not None:

current = current.right self.stack.append(current)

while current.left is not None:

current = current.left self.stack.append(current)

return data raise StopIteration

if __name__ == "__main__":

tree = MyTree(Node(16)) tree.add_node(Node(8)) tree.add_node(Node(1)) tree.add_node(Node(17)) tree.add_node(Node(13)) tree.add_node(Node(14)) tree.add_node(Node(9)) tree.add_node(Node(10)) tree.add_node(Node(11))

for i in tree: print(i)

209
CHAPTER 13 ITERATOR PATTERN

We keep the Node class exactly as we defined it earlier, only now we have added a Container class, namely MyTree. This class implements the iterator protocol, and as such can be used in a normal Python for loop, as we have seen in the list iterator. We also included a convenience function that allows us to build a binary tree by simply calling the add_node method on the tree instance of MyTree. This allows us to forget about how exactly the tree is implemented. The process of inserting a new node into the tree simply involves looking at the current node and going left if the node to be added s data value

is less than or equal to that of the current node in the tree. We keep doing this until an empty spot is found, and the new node is placed at this empty spot.

To traverse the tree, we keep a stack of nodes, then we start pushing repeatedly, moving left and pushing the current node onto the stack. This happens until there are no more left children. Then, we pop the top node from the stack and check if it has a right child. If it does, the right child gets pushed onto the stack, along with the leftmost branch of the tree from that node. We then return the value of the node popped from the stack. The stack is maintained as an instance variable of the tree object, and as such we are able to continue where we left off every time the __next__() method is called.

This results in an ordered sequence being printed, as follows:

1 8 9 10 11 13 14 16 17

We could use existing Python functions and constructs to interface with the binary tree, like for loops and max and sum functions. Just for fun, look at how easy it is to use these constructs with a completely custom data type.

You have seen that for loops work as expected; now, we will use the same code as we did in bin_tree_iterator.py, but we will add a max and sum call to the last if statement. As such, only the if statement is included in the code snippet.

210
CHAPTER 13 ITERATOR PATTERN

if __name__ == "__main__":

tree = MyTree(Node(16)) tree.add_node(Node(8)) tree.add_node(Node(1)) tree.add_node(Node(17)) tree.add_node(Node(13)) tree.add_node(Node(14)) tree.add_node(Node(9)) tree.add_node(Node(10)) tree.add_node(Node(11))

for i in tree: print(i)

print("maximum value: {}".format(max(tree)))

print("total of values: {}".format(sum(tree))) As you would expect, the results are as follows:

1

8

9

10

11

13

14

16

17

maximum value: 17 total of values: 99

The algorithms for each of these constructs were implemented completely decoupled of the data types that would later use them. Interestingly enough, you can create a list object that is iterable using a list comprehension (which is almost like a shorthand for creating iterable objects) as above, only the if statement is changed, so once again I will only include the code for the if and the code needed to transform the tree into a list.

211
CHAPTER 13 ITERATOR PATTERN

if __name__ == "__main__":

tree = MyTree(Node(16)) tree.add_node(Node(8)) tree.add_node(Node(1)) tree.add_node(Node(17)) tree.add_node(Node(13)) tree.add_node(Node(14)) tree.add_node(Node(9)) tree.add_node(Node(10)) tree.add_node(Node(11))

print([x for x in tree]) Resulting in an ordered list of values

[1, 8, 9, 10, 11, 13, 14, 16, 17]

List comprehensions are fairly simple to understand. They take a function or operation and map it to an iterable. You could also add some sort of conditional statement after the iteration to exclude certain elements.

Let s alter the comprehension we just looked at to now ignore all multiples of 3.

once again a list comprehension with an if x % 6 != 0

if __name__ == "__main__":

tree = MyTree(Node(16)) tree.add_node(Node(8)) tree.add_node(Node(1)) tree.add_node(Node(17)) tree.add_node(Node(13)) tree.add_node(Node(14)) tree.add_node(Node(9)) tree.add_node(Node(10)) tree.add_node(Node(11))

print([x for x in tree if x % 3 != 0])

As you would hope, the 9 is not included in the final list:

[1, 8, 10, 11, 13, 14, 16, 17]

212
CHAPTER 13 ITERATOR PATTERN

Itertools

I m sure you are convinced of the usefulness of iterators by now. So, I will add a quick mention of the Itertools package included in the standard library. It contains a number of functions that allow you to combine and manipulate iterators in some interesting ways. These building blocks have been taken from the world of functional programming and languages like Haskell and reimagined in a pythonic way.

For an extensive list of these, do yourself a favor and read the documentation for the Itertools library. To introduce you to the library, I just want to mention three functions.

The first is chain(), which allows you to chain multiple iterators one after the other.

import itertools

print(list(itertools.chain([1, 2, 3, 4], range(5,9), "the quick and the slow")))

This iterates over every value in each of the three iterables and converts them all to a single list that is printed, as follows:

[1, 2, 3, 4, 5, 6, 7, 8, ’t’, ’h’, ’e’, ’ ’, ’q’, ’u’, ’i’, ’c’, ’k’, ’ ’, ’a’, ’n’, ’d’, ’ ’, ’t’, ’h’, ’e’, ’ ’, ’s’, ’l’, ’o’, ’w’]

Next, we have the infinite iterator cycle(), which allows you to create an iterator that will keep cycling over the elements passed to it indefinitely.

import itertools

cycler = itertools.cycle([1, 2, 3]) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__()) print(cycler.__next__())

213
CHAPTER 13 ITERATOR PATTERN

Every time the cycler reaches the last element, it just starts back at the beginning.

1 2 3 1 2 3

1 2

The third and final function you can look at is zip_longest(), which combines a set of iterables and returns their matched elements on each iteration.

zip_longest example import itertools

list1 = [1, 2, 3] list2 = [’a’, ’b’, ’c’]

zipped = itertools.zip_longest(list1, list2) print(list(zipped))

The result is a set of pairs where the first pair contains the first elements of both lists, the second pair contains the second elements of both lists, and so on.

[(1, ’a’), (2, ’b’), (3, ’c’)]

There are many other interesting things you can do with iterators, and many of them will help you find simple solutions for tricky problems. As is probably the case with most libraries included in the Python standard library, it is worth your effort to explore and master the Itertools package.

Generator Functions

Before we begin exploring generator expressions, let s write a quick script to demonstrate what they do.

214
CHAPTER 13 ITERATOR PATTERN

gen_ func.py

def gen_squares(n):

i = 0

while i < n:

yield i*i print("next i") i += 1

if __name__ == "__main__": g = gen_squares(4) print(g.__next__()) print(g.__next__()) print(g.__next__()) print(g.__next__()) print(g.__next__())

The result you get from requesting next is the next square, as you can see here:

0

next i

1

next i

4

next i

9

next i

Traceback (most recent call last):

File "gen_func.py", line 15, in

print(g.__next__())

StopIteration

There are a couple of interesting things you will observe from the output, the first of which is that every time you call the function the output changes. The second thing you should note is that the function starts executing from just below the yield statement and continues until it hits the yield again.

215
CHAPTER 13 ITERATOR PATTERN

When the interpreter encounters the yield statement, it keeps a record of the

current state of the function and returns the value that is yielded. Once the next value

is requested via the __next__() method, the internal state is loaded and the function continues from where it left off.

Generators are a great way to simplify the creation of iterators since a generator is a function that produces a sequence of results and follows the interface for collections that can be iterated over as per the Python implementation of the iterator pattern. In the case of a generator function, the Python internals take care of the iterator protocol for you.

When a generator function is called, it returns a generator object but does not begin any execution until the __next__() method is called the first time. At that time, the function starts executing and runs until the yield is reached. Once the generator reaches its end, it raises the same exception as iterators do. The generator returned by the generator function is also an iterator.

Generator Expression

Much like we used list comprehensions as a shorthand to create iterators, there is a special shorthand for generators called generator expressions.

Look at the example generator expression that follows. It is simply an alternative for the generator function we defined earlier.

g = (x*x for x in range(4))

Generator expressions can be used as arguments to certain functions that consume iterators, like the max() functions.

print(max((x*x for x in range(4))))

This prints the number 9.

With Python, we can drop the parentheses around a generator if there is only one argument in the calling function.

print(max(x*x for x in range(4)))

This is a little bit neater.

216
CHAPTER 13 ITERATOR PATTERN

Parting Shots

Iterators and generators will help you do a lot of heavy lifting as you explore the world of Python, and getting comfortable using them will help you code faster. They also extend your code into the realm of functional programming, where you are more focused on defining what the program must do rather than how it must be done.

Speaking of coding faster, here are a couple of tips to improve your development speed.

Learn to touch type. It is like being able to read and write. If you are

going to do something every day, learning to do that as effectively as possible is a major force multiplier.

Study and master your editor or IDE of choice, whether that be Vim,

Emacs, Pycharm, or whatever else you use, and make sure to learn all the shortcuts.

Eliminate distractions, as every time you need to switch context, you will take up to 30 minutes to find your groove again. Not worth it.

Make sure your tests run fast. e slower your tests are, the greater

the temptation is to skip them.

Every moment spent searching online for an answer or example is

coding and thinking time gone to waste, so learn the field, master the language, and reduce your time on forums.

Pay down technical debt as if your life depended on it your

happiness sure does.

Exercises

Implement a Fibonacci sequence iterable using both a generator and

a regular iterator.

Create a binary tree iterator using generator functions.

217