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.

Advertisements

Pages: 1 2

2 Responses to “Generator Push-Back”

  1. chaw said

    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.

  2. Paul said

    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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: