Today's spicy recitation is themed around lazy programming. The core idea of lazy programming is that you do not evaluate something until you NEED to evaluate it. This allows us to create objects called generators which can theoretically yield something infinite, without having to evaluate all infinity values first.
A generator is like a factory that produces what you need when you need it. Every time your for loop begins a cycle, it requests a value from the generator, the generator calculates and yields the value and then waits until the next request, then the for loop sets i (or whatever variable name you use) equal to the output of the generator. A yield statement is like a return statement except that instead of breaking out of the function, it pauses until the next iteration of the loop.
Below is a function that mimicks the builtin range() generator:
def myRange(start, stop, step):
i = start
while i < stop:
yield i # Yield returns i but PAUSES instead of breaking out of the function
i += step
for i in myRange(5, 10, 2):
print(i)
Write the following basic generators:
iRange(start, step) # the same as range except it goes on forever
fibonacci() # generates all numbers in the fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...)
iIter() # takes in a function f, a value seed and yields seed, f(seed), f(f(seed)), f(f(f(seed)))...
def iRange(start, step):
i = start
while True:
yield i
i += step
def fibGen():
yield 0
yield 1
a, b = 0, 1
while True:
a, b = b, a+b
yield b
def iIter(f, seed):
while True:
yield seed
seed = f(seed)
def double(x): return x * 2
# for i in iRange(1,1):
# print(i)
# if i >= 100: break
# for i in fibGen():
# print(i)
# if i >= 100: break
# for i in iIter(double,3):
# print(i)
# if i >= 100: break
Write nthPrime() using a while loop, and then a for loop; isPrime() is already written. Then, write a generator which spits out the prime numbers up to the nth.
def isPrime(n):
if n < 2: return False
for i in range(2,n):
if n % i == 0: return False
return True
def nthPrime(n):
found = 0
for guess in iRange(0, 1):
if isPrime(guess):
found += 1
if found > n:
return guess
# assert(nthPrime(0) == 2)
# assert(nthPrime(1) == 3)
# assert(nthPrime(2) == 5)
# assert(nthPrime(4) == 11)
# assert(nthPrime(8) == 23)
# assert(nthPrime(16) == 59)
def nPrimes(n):
found = 0
for guess in iRange(0, 1):
if isPrime(guess):
found += 1
yield guess
if found > n:
break
# for p in nPrimes(10):
# print(p, end=" ")
The next() function will spit out the next item in the generator. However, if the generator is consumed completely, an exception is caused. If not, then you can theoretically keep calling next() on it forever.
def evensBelowN(n):
i = 0
while i < n:
yield i
i += 2
evensBelow10 = evensBelowN(10)
# Gradually uncomment the following lines:
# print(next(evensBelow10))
# print(next(evensBelow10))
# print(next(evensBelow10))
# print(next(evensBelow10))
# print(next(evensBelow10))
# print(next(evensBelow10))
Therefore, you can think of a for loop as the following abstraction of a while loop:
While I do not recieve the StopIteration error:
i = next(generator)
<< for loop body >>
There is a way to catch errors like this, which we will do next time in spicy
Before we get more into this idea of mapping and filtering functions, lets discuss a much shorter way to declare functions.
Below are 2 very different looking pieces of code that are actually identical. The second is referred to as an anonymous function, also known as a lambda function, because it doesn't have a name until we say "square =", which is optional. Therefore, we can pass "lambda x: x**2" around like an ordinary variable without having to decalre the function first.
The downside is that lambda functions are 1-line functions and cannot have any statements.
def square(x): return x**2
# ↓ Pretend there is a return statement here
square = lambda x: x**2
# Here are a couple more:
def isEven(x):
return x % 2 == 0
isEven = lambda x: x % 2 == 0
def minimum(x, y):
if x < y:
return x
else:
return y
minimum = lambda x, y: x if x < y else y
def distance(x, y):
return
distance = lambda x, y: (x ** 2 + y ** 2) ** 0.5
These are referred to as Higher-Order-Functions (HOFs) since they are functions that take in functions as inputs. Besides map and filter, one of the most common HOFs is a function called "reduce" (or, in other languages, "combine" or "fold") which combines all the elements of a sequence using a combination function. We will just focus on these 2 for now.
import math
nSquares = map(lambda x: x**2, range(10))
nEvens = filter(lambda x: x%2 == 0, range(10))
# for s in nSquares:
# print(s)
# for e in nEvens:
# print(e)
# More examples:
# Concatenates each number to itself
# for i in map(lambda x: int(str(x)*2), range(20,30)):
# print(i)
# Swaps the 1s and 10s digit
# for i in map(lambda x: x//10 + 10*(x%10), range(20,30)):
# print(i)
# Converts each number to binary
# for i in map(bin, range(20, 30)):
# print(i)
# Only keeps the perfect squares
# for i in filter(lambda x: int(x**0.5) == x**0.5, range(100)):
# print(i)
# Only keeps numbers that are multiples of 2 and 3 and and 5
# or not multiples of 2 or 3 or 5
# for i in filter(lambda x: x % 2 == x % 3 == x % 5, range(100)):
# print(i)
# Only keeps the palindromes
# for i in filter(lambda x: str(x)[::-1] == str(x), range(100)):
# print(i)
Below is a function that returns True if a positive number n is a palindrome (without using strings!). The function is written as a rather nasty 1-liner so a normal version is also included for refrence.
Note: the all() function takes in a generator/iterable and returns True if all of the values inside evaluate as True.
Use this function to write a generator that spits out ALL palindromic numbers.
import math
# The normal verison:
def isPalindrome(n):
count = int(math.log10(n))
for k in range(1 + count):
digit = (n // (10 ** k) % 10)
mirrorDigit = (n // (10 ** (count - k)) % 10)
if digit != mirrorDigit:
return False
return True
# The 1-line version:
isPalindrome = lambda n: all(map(lambda k: (n // (10 ** k) % 10) == (n // (10 ** (int(math.log10(n)) - k)) % 10),
range(1 + int(math.log10(n)))))
iPalindromes = filter(isPalindrome, iRange(1, 1))
for i in iPalindromes:
if i > 3000: break
print(i)
Now write a 1-line isPrime function and an infinite prime generator.
Note: The all() function may be useful, but alternatively you could use the any() function which takes in a generator/iterable and returns True if any of the values inside evaluate as True.
isPrime = lambda n: n >= 2 and not any(map(lambda i: n % i == 0, range(2, n)))
def isPrime(n):
if n < 2: return False
for i in range(2,n):
if n % i == 0: return False
return True
primes = filter(isPrime, iRange(1, 1))
for p in primes:
if p > 200: break
print(p)
Try to reason about what the following lines of code will print:
def koz(koz):
koz = koz()
def koz():
koz = lambda koz: koz
return koz(koz)
return koz
koz = koz(lambda: koz)()
print(koz("Taylor"))
Attendance Link: https://tinyurl.com/wedRecitation2F20)