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.

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: