;; Die ersten drei Zeilen dieser Datei wurden von DrRacket eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrRacket verarbeiten kann.
#reader(lib "DMdA-vanilla-reader.ss" "deinprogramm")((modname set-list) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Schnittstelle für Mengen:
(provide set empty-set add-set elem? intersect)

; Wir betrachten hier nur Zahlenmengen mit ganzen Zahlen: set
; Implementierung hier: Mengen als Liste ihrer Elemente

(define set (signature (list-of integer)))

; Die leere Menge
(: empty-set set)
(define empty-set empty)

; Ist ein Element in einer Menge enthalten?
(: elem? (integer set -> boolean))
(define elem?
  (lambda (x s)
    (cond ((empty? s) #f)
          ((cons? s) (if (= x (first s))
                         #t
                         (elem? x (rest s)))))))

; Zu einer Menge ein Element hinzufügen
(: add-set (integer set -> set))
(define add-set
  (lambda (x s)
    (if (elem? x s)
        s
        (cons x s))))

(define set13 (add-set 1 (add-set 3 empty-set)))
(define set12 (add-set 2 (add-set 1 empty-set)))

; Vereinige zwei Mengen
;(: union (set set -> set))

; Bilde den Durchschnitt zweier Mengen
(: intersect (set set -> set))

(check-expect (intersect empty-set empty-set) empty-set)
(check-expect (intersect empty-set set13) empty-set)
(check-expect (intersect set12 empty-set) empty-set)
(check-expect (elem? 1 (intersect set13 set12)) #t)
(check-expect (elem? 2 (intersect set13 set12)) #f)
(check-expect (elem? 3 (intersect set13 set12)) #f)

(define intersect 
  (lambda (s1 s2)
    (cond ((empty? s1) empty-set)
          ((elem? (first s1) s2) (cons (first s1)
                                       (intersect (rest s1) s2)))
          (else   (intersect (rest s1) s2)))))