Generator Push-Back

September 1, 2017

Here is the prime-number generator in Scheme:

(define-generator (primegen)
  (yield 2) (yield 3)
    (let* ((ps (primegen))
         (p (and (ps) (ps)))
         (q (* p p))
         (d (make-hashtable identity =)))
    (define (add m s)
      (while (hashtable-contains? d m)
        (set! m (+ m s)))
      (hashtable-set! d m s))
    (do ((c (+ p 2) (+ c 2))) (#f)
      (cond ((hashtable-contains? d c)
              (let ((s (hashtable-ref d c #f)))
                (hashtable-delete! d c)
                (add (+ c s) s)))
            ((< c q) (yield c))
            (else (add (+ c p p) (+ p p))
                  (set! p (ps))
                  (set! q (* p p)))))))

And here is the the push-back function:

(define-generator (pushback val gen)
  (yield val) (while #t (yield (gen))))

It looks like this:

> (define ps (primegen))
> (ps)
2
> (ps)
3
> (ps)
5
> (ps)
7
> (ps)
11
> (ps)
13
> (ps)
17
> (set! ps (pushback 17 ps))
> (ps)
17
> (ps)
19
> (ps)
23
> (ps)
29
> (ps)
31

That’s much more convenient than the alternative. You can run the program at https://ideone.com/buBHPn.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Generator Push-Back”

  1. chaw said
    September 1, 2017 at 9:15 PM

    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
    September 2, 2017 at 7:08 AM

    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 comment