Почему моя процедура объединения набора A и набора B возвращает набор A и ничего больше?

Question

Я работаю над упражнением SICP 2.59, которое просит читателя «реализовать операцию объединения-набора для представления неупорядоченных списков наборов» . Объединение двух множеств, обозначаемых A∪B, - это множество элементов, которые находятся в A, в B, или в A и B.

Вот код, который я написал для выполнения этой операции:

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(define (union a b)
  (cond ((null? a) b)
        ((null? b) a)
        (element-of-set? (car b) a)
          (union a (cdr b))
        (else (cons (car b) a))))

Я протестировал его на множествах шансов и четностей, (define odds '(1 3 5)) (define evens '(0 2 4 6)) (union odds evens), и получил результат (1 3 5), когда ожидаемый результат был (1 3 5 0 2 4 6). Может кто-нибудь объяснить, почему я получаю этот вывод и как переписать код, чтобы получить ожидаемый вывод?

Вот пример процедуры рабочего объединения:

(define (union-set s1 s2) 
   (if (null? s1) 
     s2 
     (let 
       ((e (car s1))) 
       (union-set 
         (cdr s1) 
         (if (element-of-set? e s2) s2 (cons e s2)))))) 

Answer 1

Есть две проблемы с вашим кодом:

• Вы забыли пару () в третьем условии
• В последнем условии мы также должны вызвать рекурсию

Это должно исправить это:

(define (union a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((element-of-set? (car b) a)
         (union a (cdr b)))
        (else (cons (car b) (union a (cdr b))))))

В качестве альтернативы, если вы хотите сохранить точный тот же порядок, что и в примере вывода вопроса:

(define (union a b)
  (cond ((null? a) b)
        ((null? b) a)
        ((not (element-of-set? (car a) b))
         (cons (car a) (union (cdr a) b)))
        (else (union (cdr a) b))))

Answer 2

В вашем предложении else вы не звоните union, поэтому вы теряете все в cdr b.

Возможно:

(else (union (cons (car b) a) (cdr b)))