;; Die ersten drei Zeilen dieser Datei wurden von DrScheme eingefügt. Sie enthalten Metadaten
;; über die Sprachebene dieser Datei in einer Form, die DrScheme verarbeiten kann.
#reader(lib "DMdA-vanilla-reader.ss" "deinprogramm")((modname kapitel-10) (read-case-sensitive #f) (teachpacks ()) (deinprogramm-settings #(#f write repeating-decimal #f #t none explicit #f ())))
; Kapitel 10

; Ringzähler
(define Counter (contract natural))

; Ringzähler-Modulus, - 1
(: p natural)
(define p 2)

; initialer Zähler
(: reset Counter)
(define reset 0)

; heraufzählen
(: inc (Counter -> Counter))
(check-expect (inc (inc reset)) 2)
(check-expect (inc (inc (inc reset))) 0)

(define inc
  (lambda (n)
    (if (= n p)
        0
        (+ n 1))))

; herunterzählen
(: dec (Counter -> Counter))
(check-expect (dec (inc (inc reset))) 1)
(check-expect (dec (inc (inc (inc reset)))) 2)

(define dec
  (lambda (n)
    (if (= n 0)
        p
        (- n 1))))

; Listen

; nichtleere Liste konstruieren
(: construct (%a (list %a) -> (list %a)))
(define construct make-pair)

; erstes Element einer Liste selektieren
(: head ((list %a) -> %a))
(define head first)

; Rest einer Liste selektieren
(: tail ((list %a) -> (list %a)))
(define tail rest)

; leere Liste
(: emptylist empty-list)
(define emptylist empty)

; feststellen, ob Liste leer ist
(: emptylist? ((list %a) -> boolean))
(define emptylist? empty?)

; Suchbare Mengen
(define Searchable (contract (list %a)))

; leere Menge
(: emptyset  Searchable)

(define emptyset empty)

; feststellen, ob Menge leer
(: emptyset? (Searchable -> Boolean))

(define emptyset? empty?)

; Element in Menge einfügen
(: insert (%a Searchable -> Searchable))

(define insert make-pair)

; feststellen, ob Wert Element der Menge ist
(: member? (%a Searchable -> Boolean))
(check-expect (member? "Mike" (insert "Martin" (insert "Mike" (insert "Herb" emptyset)))) #t)
(check-expect (member? "Eric" (insert "Martin" (insert "Mike" (insert "Herb" emptyset)))) #f)

(define member?
  (lambda (e lis)
    (cond
     ((emptyset? lis) #f)
     ((pair? lis)
      (if (string=? e (first lis))
          #t
          (member? e (rest lis)))))))

; Listen-Mengen

;;;;; parametric besser?

; Eine Suchliste list-set besteht aus
; - einer Liste der Elemente der Suchmenge
; - einer Prozedur die die Elemente auf Gleichheit prüft
(: make-list-set ((list %a) (%a %a -> boolean) -> list-set))
(: list-set? (%b -> boolean))
(: list-set-list (list-set -> (list %a)))
(: list-set-element-equal-proc (list-set -> (%a %a -> boolean)))

(define-record-procedures list-set
  make-list-set list-set?
  (list-set-list list-set-element-equal-proc))

; leere Menge herstellen
(: list-set-empty ((%a %a -> boolean) -> list-set))

(define list-set-empty
  (lambda (equal-proc)
    (make-list-set empty equal-proc)))

; Element einfügen
(: list-set-insert (%a list-set -> list-set))

(define list-set-insert
  (lambda (element list-set)
    (make-list-set
      (make-pair element
                 (list-set-list list-set))
      (list-set-element-equal-proc list-set))))

; feststellen, ob Element in Menge ist
; list-set-member? : e list-set(e) -> boolean

(define ls-1 (list-set-insert 2 (list-set-empty =)))
(define ls-2 (list-set-insert 7 ls-1))
(define ls-3 (list-set-insert 5 ls-2))

(check-expect (list-set-member? 7 ls-3) #t)
(check-expect (list-set-member? 6 ls-3) #f)
(check-expect (list-set-member? 7 ls-1) #f)

(define list-set-member?
  (lambda (element list-set)
    (let ((equal-proc (list-set-element-equal-proc list-set)))
      (any? (lambda (an-element)
              (equal-proc an-element element))
            (list-set-list list-set)))))

; any? ist eine Übungsaufgabe