Ракетка - функция, которая принимает набор в качестве входа и выводит свой набор мощности - PullRequest
Новая
       83

Ракетка - функция, которая принимает набор в качестве входа и выводит свой набор мощности

1 голос
/ 16 апреля 2020

Я пытаюсь написать функцию, которая принимает набор в качестве аргумента и возвращает его набор мощности, также в виде набора наборов.

Пример использования: 

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

Thrown Error Message

Могу ли я что-нибудь сделать со своей функцией, чтобы она выполнялась правильно? Кажется, что-то не так с "set-map" или "lambda", возможно?

1 Ответ

4 голосов
/ 16 апреля 2020

Есть две вещи, которые вызывают у вас горе в опубликованном коде: порядок аргументов в паре вызовов процедур и тип возврата одного вызова процедуры.

Процедура set-add занимает set в качестве первого аргумента, поэтому аргументы здесь необходимо поменять местами: 

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

Аналогично, set-map принимает set в качестве первого аргумента и процедуру в качестве второго: 

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

Теперь, несколько нелогично, set-map возвращает list, а не set; Но set-union ищет set. Чтобы дать set-union то, что он хочет, вы можете использовать list->set для построения set из list: 

(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))
...