Racket how to define a recursive generator like Python?

Question

This is a recursive algorithm to yield all subsets of a set. the equivalent Python code is:

def subsets(s):
    if not s:
        yield ()
    else:
        for e in subsets(s[1:]):
            yield s[:1] + e
            yield e

for s in subsets((1,2,3)):
    print(s)

Result:

>>> 
(1, 2, 3)
(2, 3)
(1, 3)
(3,)
(1, 2)
(2,)
(1,)
()

This is the Racket version I tried:

#lang racket
(require racket/generator)

(define (subsets x)
  (generator ()
   (let recur ([s x])
     (if (null? s) 
         (yield '())
         (for ([e (in-producer (recur (cdr s)))])
           (yield (cons (car s) e))
           (yield e))))))

(for/list ([j (in-producer (subsets '(1 2 3)))])
    (display j))

But it doesn't work:

Welcome to DrRacket, version 6.0.1 [3m].
Language: racket; memory limit: 128 MB.
(). . result arity mismatch;
 expected number of values not received
  expected: 1
  received: 0
  values...:               

There seems to be no related example in Racket documentation Is it possible, how?

Answer 1

You were overall pretty close, with some minor issues:

• You made the subsets function get the set and return a generator properly, but then you decided to wrap the body in the recur loop for no good reason... You want the recursive call to return a generator (to be used as a producer) so you just need to call subsets.

• The proper way to iterate over a generator is to make it return some known value when it's done, and use that as a stop-value. For example, add a (void) in the end and use it to stop.

• You shouldn't mix for/list and display -- the first is used to collect a list of results and the second is used to display a value. Either switch to for, or just drop the display to return the list of subsets.

Fixing these gives working code:

#lang racket
(require racket/generator)

(define (subsets s)
  (generator ()
    (if (null? s)
      (yield '())
      (for ([e (in-producer (subsets (cdr s)) (void))])
        (yield (cons (car s) e))
        (yield e)))
    (void)))

(for ([j (in-producer (subsets '(1 2 3)) (void))])
  (displayln j))

Two side comments:

• A minor comment about Oscar's solution: using in-generator can be a little confusing since it's not a way to iterate over a generator but instead it's a way to create a generator and immediately iterate over it.

• JFYI, this is not really a good way to do this if you care about efficiency (rather than play around with generators).

Answer 2

I think the procedure can be simplified a bit. The following is equivalent to the code in Python, and notice how we use in-generator:

(require racket/generator)

(define (subsets s)
  (if (null? s) 
      (yield '())
      (for ([e (in-generator (subsets (cdr s)))])
        (yield (cons (car s) e))
        (yield e))))

Call it like this:

(for ([e (in-generator (subsets '(1 2 3)))])
  (displayln e))

=> (1 2 3)
   (2 3)
   (1 3)
   (3)
   (1 2)
   (2)
   (1)
   ()