Skip to content

Instantly share code, notes, and snippets.

@bgeron
Created November 7, 2018 23:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bgeron/ee06240e78cedf161d0d6240c03ee9d0 to your computer and use it in GitHub Desktop.
Save bgeron/ee06240e78cedf161d0d6240c03ee9d0 to your computer and use it in GitHub Desktop.
Fibonacci generators in Python without using the keyword yield
# 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