Generator Push-Back
September 1, 2017
Generators are a useful programming tool; we provide an implementation in the Standard Prelude. Here is a Python prime-number generator that we discussed in a previous exercise:
def primegen(): # http://stackoverflow.com/a/20660551
yield 2; yield 3 # prime (!) the pump
ps = primegen() # sieving primes
p = next(ps) and next(ps) # first sieving prime
D, q, c = {}, p*p, p # initialize
def add(x, s): # insert multiple/stride
while x in D: x += s # find unused multiple
D[x] = s # save multiple/stride
while True: # infinite list
c += 2 # next odd candidate
if c in D: # c is composite
s = D.pop(c) # fetch stride
add(c+s, s) # add next multiple
elif c < q: yield c # c is prime; yield it
else: # (c == q) # add sqrt(c) to sieve
add(c+p+p, p+p) # insert in sieve
p = next(ps) # next sieving prime
q = p * p # ... and its square
I recently needed to interrupt a prime generator, then restart it; I needed all the primes up to a limit, but of course I didn’t know I had reached the limit until the generator produced the first prime past the limit. I could have saved the too-large prime, then used it before restarting the generator, but that’s inconvenient; it needs a separate variable for the saved prime, and a test to determine if a saved prime is available each time through the restarted generator. A better solution is to push back the value onto the generator:
def pushback(val,gen):
yield val
while True:
yield next(gen)
Your task is to add push-back to the generator of your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Just a quick note that if we use SRFI 121 (Generators) with standard R7RS Scheme, then pushback is provided by the gcons* procedure from the SRFI. Of course, that may not be in the spirit of exercising. On a related note, primegen may be definied conveniently (following the Python/pseudocode template) using make-coroutine-generator.
A different approach in Python. biter is a iterator that can step back one item. Using takewhile will always eat up one item too much and you do not even know the value of it.
class biter(object): sentinel = object() def __init__(self, iterable): self.it = iter(iterable) self.cache = biter.sentinel self.use_cache = False def __iter__(self): return self def __next__(self): if self.use_cache: value, self.use_cache = self.cache, False else: value = self.cache = next(self.it) return value def back(self): if self.use_cache or self.cache == biter.sentinel: raise ValueError("Cannot go back") self.use_cache = True p = lazyprime() print(list(takewhile(lambda x: x < 20, p))) print(next(p)) # prints: [2, 3, 5, 7, 11, 13, 17, 19] # prints: 29 g = biter(lazyprime()) print(list(takewhile(lambda x: x < 20, g))) g.back() print(next(g)) # prints: [2, 3, 5, 7, 11, 13, 17, 19] # prints: 23