方案 - 如何返回無限量集合的交集？

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'是一個休息參數。

不過我還是設法寫一個聯盟函數，它集無限量：

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

您可能注意到，工會*功能和路口*功能外觀幾乎一樣。那是因爲我試圖拼命地在交點*函數上使用與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))))))