How to combine two generators in a non-trivial way

generator, puzzle, scheme

Solution

Using a self-reading stream

You can solve this using a self-read stream:

   -----------        -----------
   |  pow 2  |------->|         |
   -----------        |         |
                      |  merge  |-------+------------>
   -----------        |         |       |
.->|   x 3   |------->|         |       |
|  -----------        -----------       |
\_______________________________________/

The first stream produces the powers of two, while the second one ensures all the generated numbers are multiplied by 3 and reinjected into the output. The merge operator ensures that the output is sorted.

Note that we must "seed" the output stream with 1, or the first element will try to produce itself when evaluated.

Here is the code:

(require srfi/41)

(define (merge s1 s2)
  (stream-match s1 ((x . xs)
    (stream-match s2 ((y . ys)
      (if (< x y)
        (stream-cons x (merge xs s2))
        (stream-cons y (merge ys s1))))))))

(define (the-stream)
  (letrec ((s
    (stream-cons 1 (merge (stream-map     (lambda (x) (* 3 x)) s)
                          (stream-iterate (lambda (x) (* 2 x)) 2)))))
  s))

It's quite simple and fast compared to my other proposal, because it uses arithmetic properties of the problem besides monotonicity. I'm wrong, it can be generalized just as well (upcoming)

$ mzscheme -f feedback.scm -e '(display (stream->list (stream-take 20 (the-stream))))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f feedback.scm -e '(display (stream-ref (the-stream) 10000))'
161968247347450370721577384417107686788864605658546176
real    0m1.746s
user    0m1.344s
sys     0m0.156s

Using generators and a queue

We can also implement this with python's generators, but we need to use a queue to store the numbers waiting in the feedback loop:

# Merge the output of two generators
def merge(g1, g2):
    v1 = g1.next()
    v2 = g2.next()
    while 1:
        if v1 < v2:
            yield v1
            v1 = g1.next()
        else:
            yield v2
            v2 = g2.next()

# Generates the powers of 2, starting with n
def pow2(n):
    while 1: yield n; n *= 2

# Generates values shifted from the given 'q' and multiplied by 3
def mul3(q):
    while 1: yield q.pop(0) * 3

# The generator we want
def pow23():
    q = []
    v = 1
    g = merge(pow2(2), mul3(q))
    while 1:
        yield v
        q.append(v)
        v = g.next()

g23 = pow23()
for i in range(10000): g23.next()
print g23.next()

This is somewhat less elegant (IMHO), but the generators are much more lightweight:

$ time python feedback.py 
161968247347450370721577384417107686788864605658546176
real    0m0.150s
user    0m0.112s
sys     0m0.012s

For what is worth, I have done a scheme implementation (using closures as generators) which shows roughly the same performance.

Problem

Original source