#functional-programming #set #scheme
Вопрос:
Если вы представляете наборы по их характеристическим функциям, таким образом, что набор-это функция, которая принимает элемент и возвращает значение true, если элемент является членом набора, как бы вы проверили, что набор является подмножеством другого, не пробуя каждый элемент во вселенной (обычно невозможно)?
Вот представление такого набора в схеме. Я хочу определить функцию (подмножество? set1 set2).
(define EMPTY-SET (lambda (x) #f)) (define (set-contains? maybe-elem set) (set maybe-elem)) (define (set-add to-add set) (lambda (x) (or (equal? x to-add) (set x)))) (define (list-gt;set l) (foldr set-add EMPTY-SET l)) (define (intersect set1 set2) (lambda (x) (and (set-contains? x set1) (set-contains? x set2)))) ; examples: (define ex-set-1 (list-gt;set (list 1 2 3 4))) (define ex-set-2 (list-gt;set (list 3 4 5 6))) (display (set-contains? 2 (intersect ex-set-1 ex-set-2))) ; false (display (set-contains? 3 (intersect ex-set-1 ex-set-2))) ; true Комментарии:
1. Для этого современное программное обеспечение использует двоичные диаграммы принятия решений для наборов кодирования. Я подробно рассказываю здесь о том, как вы можете кодировать характеристические функции с помощью BDD, как вы можете найти самостоятельно. Я также несколько раз публиковал ответы на эту тему.
Ответ №1:
Вы не можете сделать это с заданным интерфейсом, который вы определили. Вам нужно каким-то образом составить список членов первого набора, чтобы запросить второй набор для каждого из них. В некоторых случаях вы можете запросить всю вселенную, как вы предлагаете; или вы можете добавить в набор интерфейс с передачей сообщений, чтобы, например
(set 'contains? x) отвечает на первоначальный вопрос, и
(set 'list) возвращает список всех его участников.