{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Workshop: iterators and generators\n",
"\n",
"### Monday, February 28, 2022\n",
"\n",
"In today's workshop we'll start talking about functional programming, starting with the basics of iterators and generators and talking about map and filter operations. Then, on Wednesday, we'll talk about the more complicated (and more powerful!) aspects of functional programming, including accumulators and lambda expressions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 1: iter and next\n",
"\n",
"Let's begin by reviewing the `__next__()` and `__iter__()` methods, which are central to iteration in Python.\n",
"\n",
"Recall that an iterator is any object in Python that supports the `__next__()` method.\n",
"\n",
"Create a class `Powers` that iterates over powers of an integer.\n",
"This class should have:\n",
"\n",
"- An `__init__()` method that takes two integers as its arguments: a base `b` (any integer) and `maxiters` (non-negative integer), and sets `b` as an instance attribute `base`.\n",
"- A `__next__()` method, that returns `base` raised to a power. The first time `__next__` is called should return `base**0`, then `base**1` then `base**2`, etc. Once `maxiters` powers have been returned, the `Powers` object should stop returning values (i.e., raise a `StopIteration` error to signal that there are no more values to return). Read the documentation here for details: https://docs.python.org/3/library/stdtypes.html#iterator.__next__"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Powers:\n",
" def __init__( self, b, maxiters ):\n",
" #CODE GOES HERE.\n",
" # Don't forget to update pass.\n",
" pass\n",
" \n",
" def __next__( self ):\n",
" #CODE GOES HERE.\n",
" # Don't forget to update pass.\n",
" pass"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, consider the following code. What should it do?\n",
"\n",
"Once you've made your prediction, try running it."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[None, None, None, None, None, None, None, None, None, None]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p = Powers(2)\n",
"\n",
"[next(p) for i in range(10)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above code is possible because `Powers` supports the `__next__` method. It is an iterator.\n",
"\n",
"But it is not an iterable. That is, we cannot yet write something like `p = Powers(2); for x in p:...`"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"ename": "TypeError",
"evalue": "'Powers' object is not iterable",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0mp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mPowers\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mp\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# This should raise an error because Powers doesn't have an __iter__ method.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 3\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
"\u001b[0;31mTypeError\u001b[0m: 'Powers' object is not iterable"
]
}
],
"source": [
"p = Powers(3)\n",
"for x in p: # This should raise an error because Powers doesn't have an __iter__ method.\n",
" print(x)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recall from lecture that for us to be able to run the above code, `Powers` must support the `__iter__` method. Update the code above so that `Powers` is an iterable, then try running the previous block of code again."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 2: list comprehensions and generator expressions\n",
"\n",
"One distinction that was drawn in lecture was that between list comprehensions and generator expressions.\n",
"At first glance, these are very similar. Compare `[x for x in mylist]` with `(x for x in mylist)`.\n",
"In this exercise, we'll explore the difference between these.\n",
"\n",
"Let's begin by running the following two blocks of code."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[x**2 for x in range(10)] # Sidenote: this is an example of map: apply the square function to every element!"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
" at 0x105f48ca8>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(x**2 for x in range(10))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Okay, the first difference we see is that the list comprehension really does return a list (Jupyter notebook displays it and everything), while the generator expression returns a generator object. Let's look a bit more closely with that."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"4\n",
"9\n",
"16\n",
"25\n",
"36\n",
"49\n",
"64\n",
"81\n"
]
}
],
"source": [
"gen = (x**2 for x in range(10))\n",
"for g in gen:\n",
" print(g)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So gen is an iterable-- we can iterate over its elements.\n",
"\n",
"What is the difference, then between list comprehensions and generator expressions (other than the fact that lists and generators are different types...)?\n",
"\n",
"The key difference becomes clear when we try to iterate over an infinite set.\n",
"\n",
"Here's a slight variation on our `Powers` class above."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"class Evens: # Iterates over the even integers, starting with 0.\n",
" def __init__( self ):\n",
" self.n=0 # Counter for keeping track of how many evens we have given\n",
" def __next__( self ):\n",
" e = 2*self.n # The next even integer.\n",
" self.n+=1 # Update our counter\n",
" return e\n",
" def __iter__( self ):\n",
" return self # So that we can write for x in evens"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using the `Evens` class above, write a generator expression that generates the multiples of 4. Store the generator expression in a variable `g`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#CODE GOES HERE."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, again using the `Evens` class above, write a list comprehension that generates the multiples of 4. Store it in a variable `t`. What happens? Why?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#CODE GOES HERE."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 3: the Catalan numbers\n",
"\n",
"The Catalan numbers (https://en.wikipedia.org/wiki/Catalan_number) are a sequence given by\n",
"$$\n",
"C_n = \\frac{ (2n)! }{ n!(n+1)! }\n",
"$$\n",
"for $n=0,1,2,\\dots$.\n",
"\n",
"Write a generator expression that enumerates all and only the odd Catalan numbers from among the first 100 Catalan numbers.\n",
"\n",
"Hint: this is easiest done in two steps: a map operation followed by a filter operation.\n",
"\n",
"Second hint: you may find it useful to use the following generator, which enumerates the numbers $0,1,2,\\dots$"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"def natural_numbers(): # This is a generator. More on that in the next exercise.\n",
" n=0\n",
" while True:\n",
" yield n\n",
" n += 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#CODE GOES HERE."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 4: generators\n",
"\n",
"In addition to generator expressions, we can create more interesting/powerful generators using the `yield` keyword. This allows us to write something that looks a lot like functions, but which stores internal state.\n",
"\n",
"Generators are kind of between functions and objects.\n",
"A function, once it returns a value, \"forgets\" all the work it did-- any intermediate computations we did when producing our result disappear (unless we do something clever like store them in a file or in a global variable).\n",
"In contrast, a generator stores internal state, which remains accessible between return values.\n",
"This distinction is made by using the `yield` keyword instead of the `return` keyword.\n",
"\n",
"Implement a generator called `power_gen` with the same behavior as our `Powers` object in Problem 1 above, except it should only take a single argument, the base `b` (i.e., it should enumerate an infinite set of powers of `b`)."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [],
"source": [
"def power_gen( b ):\n",
" pass"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Discussion: Comparing this with the `Powers` class from Problem 1, which seems like the more natural solution to the problem of enumerating powers of a number?"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}