Generator and Traversal
When I was first introduced to lazy evaluation in Haskell, I was sold by the idea of working with infinite series. Here is the simple program that creates an infinite series of integers and outputs only first ten digits.
-- |It creates a list of integers from 1 to infinity
list = [1..]
take 10 list-- | Prints out first 10 digits from the list
=> [1,2,3,4,5,6,7,8,9,10]
This idea of evaluating a computation only when needed was later implemented in many programming languages such as C#, Python, Javascript(ES6), Kotlin etc. All these languages implemented this idea of lazy evaluation in the form of “Generator”. Let’s see how generator works in python.
def sample_generator_function():
print('Before yield')
yield
print('After yield')
We can create a simple generator function in python by introducing a keyword called “yield”. When there is a yield statement inside the function, suddenly your function gets a special magic power and that is the ability to pause the execution of function anywhere in the middle where “yield” appears and thus releasing the control back to the caller of that generator function. Unlike other function, we have to execute generator function a bit differently.
The way we can execute above generator function is as follows:
# calling the generator function will just return you a generator object unlike the normal function.generator_func = sample_generator_function()# now we need to pass this generator object to a built-in function called nextnext(generator_func)#this will print 'Before yield'# since we hit the yield statement, generator function is suspended
# in order to execute later statements, we need to again call next on itnext(generator_func)#this will print 'After yield'
This is the whole idea of generator function. Thus in an essence, Generator function are those special function that has an ability to suspend its execution when needed.
Okay this is cute, but what could i do with this???
There are way more applications than I could possibly think of. You might have possibly used generators without actually realizing it. For example, async/await in Python, Javascript, C#, Swift all uses generators behind the scenes. Some of the notable area where generators are widely used are Iteration, Context Manager, Traversal, Lazy state machine, Pipeline or wherever you might want to leave a low memory footprint in your program while evaluating huge computation.
I could go forever on when and where can you write your own generators, but today I would like to show you few ways you can use generators for Iteration and Traversal since this will be the good starting point for using generators and wrapping your head around. ;)
Lets first start by implementing a infinite series and printing out first three digits:
def infinite_series():
a = 0
while True:
yield a
a += 1# start the generator
gen = infinite_series()print(next(gen)) # 0
print(next(gen)) # 1
print(next(gen)) # 2# this looks way too much of work, however there are standard library in rescue to do just thatfrom itertools import islice
print(list(islice(gen, 3)))# [3, 4, 5]print(list(islice(gen, 3)))# [6, 7, 8]
Let’s write a program that generates fibonacci series using generator. I will choose javascript here since implementation is similar in both languages.
function* fib() {
let a = 0;
let b = 1;
while (true) {
yield a;
temp = a;
a = b;
b = temp + b;
}
}// Let's execute it manually
const fibGenerator = fib();const firstValue = fibGenerator.next().value
const secondValue = fibGenerator.next().value
const thirdValue = fibGenerator.next().value// lets write a utility function to abstract out the manual executionfunction take(n, gen) {
const result = [];
while(n--) {
const val = gen.next().value;
result.push(val);
}
return result;
}// now we can write something like thisconst series = take(5, fibGenerator);
console.log(series) // [2, 3, 5, 8, 13]
Notice that there are no any upper or lower bound checks and the function can produce infinite number of fibonacci numbers when needed. Now let’s get into more fun stuff that we can do with generator. But before we dive into, We need to understand about “generator delegation”.
Let’s write a simple generator function that yields a list of number up-to given upper limit “n”.
''' Generator function that yields a value from 0 to < n'''
def range(n):
i = 0
while i < n:
yield i
i += 1Note: This above generator function can be driven by “for loop” like so
for val in range(5):
print(val, end=' ')# output
# 0 1 2 3 4
But what if I want to write another generator function that would yield the value “done!” at the end, when range(5) is finished.
def my_another_generator():
for i in range(5):
yield i
yield 'done'
The way we would run such generator would be again something like this:
for val in my_another_generator():
print(val, end=' ')# output
# 0 1 2 3 4 'done'
DID YOU NOTICE SOMETHING LABORIOUS?
If you look closely at “my_another_generator” function, you can see that we are driving the “range(5)” generator to yield its value and then finally yielding “done”. In other words, We are manually taking care of driving that “range” generator function instead of delegating that task to itself. Since, “range” generator function knows how to yield the value itself, why don’t we tell it to do the job of driving it’s own generator. That’s exactly where delegation comes in where we delegate the job of driving the generator function. The above code can be then written as:
def my_another_generator():
yield from range(5) # notice the "from" keyword
yield 'done'for val in my_another_generator():
print(val, end=' ')# output
# 0 1 2 3 4 'done'
“yield from” basically means, delegating the task of driving the generator function. Here we are delegating the task of driving to “range(5)”. In human friendly words, “yield from range(5)” simply means “Hey there range(5), I don’t want to do the job of driving you, why don’t you take of yourself and I will take care of mine!!”
So here is a quiz, what do you think this generator function would do?
def ping_pong():
yield 'ping'
yield 'pong'
yield from ping_pong()# lets first make a generator objectgen = ping_pong()# lets drive thisnext(gen) # "ping"
next(gen) # "pong"
next(gen) # "ping"
next(gen) # "pong"
next(gen) # "ping"
next(gen) # "pong"# it goes on forever
The above generator is initially yield “ping” and “pong” and delegates to itself thus calling “ping” and “pong” again and does this forever. A.K.A “Recursive Generator function”.
When I was first getting to know these type of generator function which delegates to itself and thus giving whole new definition of recursion using generator, I was sold instantly.
I could go on forever explaining how awesome these recursive generators are, but that might be too much specially when you are just getting started on generators. However I will leave few snippets below that will hopefully change the way you look at generators again.
'''Fibonacci series using recursive generator delegation'''def fib(a, b):
yield a
yield from fib(b, a + b)
Traversal on Linked List:
class Node:
def __init__(self, val, next_node=None):
self.val = val
self.next_node = next_node def __repr__(self):
return f'Node({self.val})'# function to convert normal list to linked list
def from_list(alist):
if len(alist) == 1:
return Node(alist[0])
return Node(alist[0], next_node=from_list(alist[1:]))alist = [4, 5, 6, 7, 8]#converting to linked list
linked_list = from_list(alist)
A generator function to traverse a linked list:
def traverse(node):
if node:
yield node
yield from traverse(node.next_node)Similarly traversing a tree would be something like this:
def traverse_tree(node):
if node:
yield from traverse_tree(node.left)
yield node
yield from traverse_tree(node.right)
If you think I need to write more on generator and go on much more detail on generator and it’s usage. Leave a comment. Thanks a ton!
