;; 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 property_set-ordered-list) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ()))) ; Schnittstelle für Mengen reeller Zahlen: ; Mengensignatur: set (provide set empty-set add-set elem? intersect) ; Implementierung von Mengen als geordnete Listen (define set (signature (list-of real))) ; Leere Menge (: empty-set set) (define empty-set empty) ; Hinzufügen eines Elementes (: add-set (real set -> set)) ; Wichtig: Reihenfolge der Listenelemente muss garantiert werden! (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))))))) ; Ist ein Element in der Menge? (: elem? (real set -> boolean)) (define elem? (lambda (x s) (cond ((empty? s) #f) ((= x (first s)) #t) ((< x (first s)) #f) (else (elem? x (rest s)))))) ; Vereinigung ;(: union (set set -> set)) (define set13 (add-set 1 (add-set 3 empty-set))) (define set12 (add-set 2 (add-set 1 empty-set))) (check-expect (elem? 1 set13) #t) (check-expect (elem? 1 set12) #t) (check-expect (elem? 3 set12) #f) ; Durchschnitt (: intersect (set set -> set)) (check-expect (intersect set13 empty-set) empty-set) (check-expect (intersect empty-set set12) empty-set) (check-expect (elem? 1 (intersect set12 set13)) #t) (check-expect (elem? 2 (intersect set12 set13)) #f) (check-expect (elem? 3 (intersect set12 set13)) #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 number) (s set)) (elem? x (add-set x s)))) (check-property (for-all ((x number) (s1 set) (s2 set)) (expect (elem? x (intersect s1 s2)) (and (elem? x s1) (elem? x s2)))))