Clever Geek Handbook

Racket, how to define a recursive generator like Python?

It is a recursive algorithm for outputting all subsets of a set. equivalent Python code:

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 this 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 corresponding example in the Racket documentation. Is it possible how?

+3


source to share


2 answers


You were pretty close, with some minor issues:

  • You made the function subsets

    get the set and return the generator correctly, but then you decided to wrap the body in a loop for recur

    no good reason ... You want the recursive call to return the generator (for use as a producer), so you just need to call subsets

    .

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

  • You cannot mix for/list

    and display

    - the first is used to collect the list of results, and the second is used to display the value. Go to for

    or just release display

    to return a list of subsets.

Fixing the data 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 sides:

  • A little comment on Oscar's solution: the usage in-generator

    can be a little confusing as it is not a way to iterate over a generator, but instead it is a way to create a generator and immediately iterate over it.

  • JFYI, this is not a very good way to do it if you're interested (instead of playing with generators).

+3


source


I think the procedure could be simplified a little. The following is equivalent to 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))))


Name 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)
   ()
+2


source






More articles:


All Articles