Created
November 7, 2018 23:55
-
-
Save bgeron/ee06240e78cedf161d0d6240c03ee9d0 to your computer and use it in GitHub Desktop.
Fibonacci generators in Python without using the keyword yield
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Python 3. | |
# | |
# Use as follows: | |
# | |
# for f in fibs_hacky(): | |
# print(f) | |
import itertools | |
# Technically it's without yield? | |
def fibs_hacky(): | |
a, b = 0, 1 | |
def next_fib(): | |
nonlocal a, b | |
result, a, b = a, b, a+b | |
return result | |
return (next_fib() for _ in itertools.repeat(None)) | |
# Oneliners are always better. Writing this in production should be grounds | |
# for instant dismissal, of course. | |
def fibs_black_magic(): | |
return (l.append(sum(l)) or l.pop(0) | |
for l in [[0, 1]] | |
for _ in itertools.repeat(None) | |
) | |
# A more readable version of the above one: | |
def fibs_intermediate(): | |
l = [0, 1] | |
# Assigns to elements of l instead of to variables | |
def next_fib(): | |
result, l[0], l[1] = l[0], l[1], l[0]+l[1] | |
return result | |
return (next_fib() for _ in itertools.repeat(None)) | |
# Haskell style, without the laziness, so this has exponential running time. | |
# Would eventually overflow the stack, except the size of the recursion tree | |
# explodes before that happens. | |
def fibs_recursion_1(): | |
# Concatenate [0, 1] with a generator that computes the sum of pairs of | |
# elements from fibs_recursion_1 and from fibs_recursion_1[1:] . | |
# | |
# Haskell: fibs = 0 : 1 : (zipWith (+) fibs $ tail fibs) | |
return (f | |
for fs in [ | |
lambda: [0, 1], | |
lambda: map(sum, zip(fibs_recursion_1(), itertools.islice(fibs_recursion_1(), 1, None)))] | |
for f in fs() | |
) | |
# Now without itertools | |
def fibs_recursion_2(): | |
return (f | |
for fs in [ | |
lambda: [0], | |
lambda: map(sum, zip(fibs_recursion_2(), (g | |
for gs in [[1], fibs_recursion_2()] | |
for g in gs | |
))) | |
] | |
for f in fs() | |
) | |
# The grossest version I can come up with | |
def fibs_puke(): | |
return (l[0] | |
for l in [[0, 1]] | |
for _ in itertools.repeat(None) | |
for l in [[l[1], l[0] + l[1]]] | |
) | |
# Handy testing function. | |
def print8(iterable, upto=8): | |
n = 0 | |
for x in iterable: | |
if n >= upto: | |
print() | |
return | |
n += 1 | |
print(x, end=' ') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment