set - Racket - 一个以集合为输入并输出其幂集的函数

Question

我正在尝试编写一个函数，它将一个集合作为参数并返回其幂集，也作为一组集合。

示例使用：

(power-set (set 1 2)) 
; is supposed to output
=> (set (set) (set 1) (set 2) (set 1 2))

我到目前为止是这样的：

(define (power-set st)
  (if (set-empty? st) (set (set))
    (let ((ps (power-set (set-rest st))))
      (set-union ps 
                 (set-map (lambda (subset) 
                              (set-add (set-first st) subset)) 
                          ps)))))

但相反，DrRacket 在包含以下内容的行上抛出错误set-map：

我可以对我的功能做些什么来使其正确执行吗？似乎“ set-map”或“ lambda”有问题？

标签： setschemeracketpowerset

Answer 1

在发布的代码中有两件事让您感到悲痛：几个过程调用中的参数顺序，以及一个过程调用的返回类型。

该set-add过程将 aset作为其第一个参数，因此此处的参数需要互换：

(set-add subset (set-first st))

类似地，set-map将 aset作为其第一个参数，将一个过程作为其第二个参数：

(set-map ps
         (lambda (subset) (set-add subset (set-first st))))

现在，有点违反直觉，set-map返回 a list，而不是 a set; 但是，set-union正在寻找一个set. 为了提供set-union它想要的东西，您可以使用从以下list->set构造一个：setlist

(list->set (set-map ps
                    (lambda (subset) (set-add subset (set-first st)))))

综合起来：

(define (power-set st)
  (if (set-empty? st) (set (set))
      (let ((ps (power-set (set-rest st))))
        (set-union ps
                   (list->set
                    (set-map
                     ps
                     (lambda (subset) (set-add subset (set-first st)))))))))

几个示例运行：

scratch.rkt> (power-set (set 1 2))
(set (set 1) (set) (set 1 2) (set 2))
scratch.rkt> (power-set (set 1 2 3))
(set (set 1) (set 1 3) (set 1 3 2) (set 3 2) (set) (set 1 2) (set 2) (set 3))