Schéma - Comment retourner l'intersection d'une quantité INFINITE d'ensembles?

Question

J'essaye d'écrire une fonction qui fonctionnera pour une quantité infinie d'ensembles au lieu de la fonction d'intersection normale qui prend seulement deux ensembles. Je l'ai cependant écrit une fonction d'intersection normale (qui ne prend que 2 jeux) qui ressemble à ceci:

(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))))) 

J'ai une fonction cassée d'intersection qui tente de prendre une quantité infinie d'ensembles comme arguments dits « intersection * ». Il ressemble à ceci:

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

Lorsque l'argument 'r' est un argument de repos.

Cependant, j'ai réussi à écrire une fonction Union qui prend une quantité infinie de jeux:

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

Vous remarquerez que le syndicat * fonction et l'intersection * fonction apparence presque identique. C'est parce que j'ai essayé d'utiliser désespérément la même logique sur la fonction d'intersection * que dans la fonction union *. Je ne m'attendais pas à ce que ça marche non plus ... Je manque d'idées. De l'aide?

Answer 1

Tant que intersection est implémenté correctement, il suffit de croiser les deux premiers ensembles, puis le résultat avec le jeu suivant, et le suivant, et ainsi de suite. Cela devrait fonctionner:

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

Ce qui précède est le même que:

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

Bonus: cette version court-circuit et dès qu'il trouve une intersection vide, renvoie:

(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))))))