方案-如何返回无穷多个集合的交集？

Question

我正在尝试编写一个函数，它将用于无限数量的集合，而不仅仅是只需要两个集合的普通交集函数。不过，我编写了一个普通的交集函数(只需2组)，如下所示：

(define intersection
 (lambda (s1 s2 [res '()])
  (cond ((set-empty? s1) (make-set res))
        ((member? (set-first s1) s2) (intersection (set-rest s1) s2 (set-insert (set-first s1) res)))
        (else (intersection (set-rest s1) s2 res)))))

我有一个破碎的交集函数，它试图将无限多的集合作为参数，称为“交集*”。目前的情况如下：

(define intersection*
 (lambda (s1 s2 . r)
  (cond ((set-empty? r) (intersection s1 s2))
        (else (intersection s1 (apply append s2 r))))))

其中，参数'r‘是rest参数。

然而，我确实成功地编写了一个Union函数，它占用了无限多的集合：

(define union*
 (lambda (s1 [s2 '()] . r)
  (cond ((set-empty? r) (union s1 s2))
        (else (union s1 (apply append s2 r))))))

您可能会注意到，union*函数和交集*函数看起来几乎相同。那是因为我拼命地试图在交集*函数上使用和在union*函数中相同的逻辑。我也没想到它会起作用..。我只是没什么主意了。有什么帮助吗？

Answer 1

只要正确实现intersection，您只需将前两个集合交叉在一起，然后将结果与下一个集和下一个集合交叉，以此类推。这应该是可行的：

(define (intersect* s1 s2 . r)
  (foldl intersect (intersect s1 s2) r))

上述情况与以下情况相同：

(define (intersect* s1 s2 . r)
  (let helper ((acc (intersect s1 s2)) (r r))
    (if (null? r)
        acc
        (helper (intersect (first r) acc) (rest r)))))

奖励:这个版本的短路，一旦找到一个空的交点，就返回：

(define (intersect* s1 s2 . r)
  (let helper ((acc (intersect s1 s2)) (r r))
    (cond ((null? r) acc)
          ((null? acc) '())
          (else (helper (intersect (first r) acc) (rest r))))))