Programming Praxis

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.

Pages: 1 2