;; 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 prop-set-orderedlist) (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 geordnete 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) ((= x (first s)) #t) ((< x (first s)) #f) (else (elem? x (rest s)))))) ; Zu einer Menge ein Element hinzufügen (: add-set (integer set -> set)) (define add-set (lambda (x s) (cond ((empty? s) (cons x s)) ((= x (first s)) s) ((< x (first s)) (cons x s)) (else (cons (first s) (add-set x (rest 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 ((or (empty? s1) (empty? s2)) empty-set) ((= (first s1) (first s2)) (cons (first s1) (intersect (rest s1) (rest s2)))) ((< (first s1) (first s2)) (intersect (rest s1) s2)) (else (intersect s1 (rest s2)))))) (check-property (for-all ((x integer) (s set)) (expect (elem? x (add-set x s)) #t))) (check-property (for-all ((x integer) (s1 set) (s2 set)) (expect (elem? x (intersect s1 s2)) (and (elem? x s1) (elem? x s2)))))