recursion - Racket如何像Python一样定义一个递归生成器？

Question

这是一种递归算法，用于生成集合的所有子集。等效的 Python 代码是:

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)

结果:

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

这是我尝试过的 Racket 版本:

#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))

但它不起作用:

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...:               

Racket文档中似乎没有相关示例是否可以，如何实现？

Answer 1

您总体上非常接近，但有一些小问题:

• 您使 subsets 函数获取集合并返回生成器 正确，但随后您决定将主体包装在 recur 循环中 没有充分的理由......你希望递归调用返回一个 生成器(用作生产者)，所以你只需要调用 子集。

• 迭代生成器的正确方法是让它返回一些 完成后已知值，并将其用作停止值。为了 例如，在末尾添加一个 (void) 并用它来停止。

• 你不应该混合使用for/list和display——第一个用于 收集结果列表，第二个用于显示值。 切换到 for，或者直接删除 display 以返回列表 子集。

修复这些问题可以提供工作代码:

#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))

两侧评论:

• 关于 Oscar 解决方案的一个小评论:使用 in-generator 可以是 有点令人困惑，因为它不是迭代生成器的方法，但是 相反，它是一种创建生成器并立即迭代的方法 超过它。

• JFYI，如果您关心的话，这确实不是一个好方法 效率(而不是玩弄发电机)。