Решение упражнения 2.59 из SICP

11 February, 2008 (20:43) | Решения упражнений

Для реализации операции объединения множеств мы можем применить рекурсивную стратегию, близкую по задумке к той, которая приводится при описании операции пересечения множеств в тексте книги. А именно, воспользуемся следующими тремя правилами при объединении множеств set1 и set2:

  1. Если set1 пусто, то объединение set1 и set2 есть set2.
  2. Если элемент x из set1 содержится в set2, то объединение set1 и set2 - это то же, что и объединение set1 без элемента x и set2.
  3. Если элемент x из set1 не содержится в set2, то объединение set1 и set2 - это то же, что и объединение set1 без элемента x и set2, к которому добавлен элемент x.

Воспользовавшись этими тремя правилами и выбирая в качестве элемента x первый элемент списка, представляющего множество set1, получим следующее определение union-set:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else
         (cons (car set1)
               (union-set (cdr set1) set2)))))

Оно очень похоже на определение intersection-set.

Comments

Comment from anton0xf
Date: August 22, 2009, 2:46 am

логичнее и короче было бы использовать accumulate и filter

(define (element-of-set? x set)
(accumulate (lambda (head rest)
(or (equal? head x) rest))
#f
set))
(define (intersection-set s1 s2)
(filter (lambda (e) (element-of-set? e s2) s1))
(define (union-set s1 s2)
(accumulate adjoin-set s2 s1))

Comment from anonymous
Date: December 6, 2010, 10:47 am

“логичнее и короче было бы использовать” adjoin-set :)
(define (union-set set1 set2)
(if (null? set1) set2
(union-set (cdr set1) (adjoin-set (car set1) set2))))

Write a comment