;; Mengenrepräsentation durch charakteristische Funktionen

(define cf-set-type (make-type 'cf-set))

(define make-cf-set
  (let ((construct (typed-value-maker cf-set-type)))
    (lambda (= cf)
      (construct (cons = cf)))))

(define cf-set-value (typed-value-selector cf-set-type))
(define cf-set-cf
  (lambda (cf-set)
    (cdr (cf-set-value cf-set))))
(define cf-set-=
  (lambda (cf-set)
    (car (cf-set-value cf-set))))

(define cf-set? (typed-value-predicate cf-set-type))
  
(define make-empty-cf-set
  (lambda (=)
    (make-cf-set
     = (lambda (x) #f))))

(define cf-set-member?
  (lambda (element cf-set)
    ((cf-set-cf cf-set) element)))

(define adjoin-cf-set
  (lambda (element cf-set)
    (let ((old-cf (cf-set-cf cf-set))
	  (= (cf-set-= cf-set)))
      (make-cf-set
       =
       (lambda (x)
	 (or (= x element)
	     (old-cf element)))))))

;; Generische Operationen für Mengen

(define adjoin-set
  (lambda (element set)
    ((cond
      ((cf-set? set) adjoin-cf-set)
      ((search-tree? set) search-tree-insert)
      ((list? set) cons))
     element set)))

(define set-member?
  (lambda (element set)
    ((cond
      ((cf-set? set) cf-set-member?)
      ((search-tree? set) search-tree-member?)
      ((list? set) member))
     element set)))

;; Generische Operationsauswahl

(define choose-set-op
  (lambda (set
           cf-set-op search-tree-op list-op)
    (cond
       ((cf-set? set) cf-set-op)
       ((search-tree? set) search-tree-op)
       ((list? set) list-op))))

(define set-member?
  (lambda (element set)
    ((choose-set-op set
                    cf-set-member?
                    search-tree-member?
		    member)
     element set)))
;; Message-Passing-Style

;; Message-Passing-Style für Mengen durch Listen

(define list->list-set-proc
  (lambda (= list)
    (lambda (message)
      (cond
       ((equal? 'adjoin message)
        (lambda (element)
	  (list->list-set-proc = (cons element list))))
       ((equal? 'member? message)
        (lambda (element)
          (member? = element list)))))))

(define member?
  (lambda (= element list)
    (any (lambda (x)
	   (= element x))
	 list)))

(define make-empty-list-set-proc
  (lambda (=)
    (list->list-set-proc = '())))

(define adjoin-list-set-proc
  (lambda (element list-set-proc)
    ((list-set-proc 'adjoin) element)))

(define list-set-proc-member?
  (lambda (element list-set-proc)
    ((list-set-proc 'member?) element)))

;; Message-Passing-Style für Mengen durch
;; charakteristische Funktionen

(define make-cf-set-proc
  (lambda (= cf)
    (lambda (message)
      (cond
       ((equal? 'adjoin message)
	(lambda (element)
	  (make-cf-set-proc =
			    (lambda (x)
			      (or (= element x)
				  (cf element))))))
       ((equal? 'member? message)
	(lambda (element)
	  (cf element)))))))

(define make-empty-cf-set-proc
  (lambda (=)
    (make-cf-set-proc = (lambda (x) #f))))

(define adjoin-cf-set-proc
  (lambda (element cf-set-proc)
    ((cf-set-proc 'adjoin) element)))

(define cf-set-proc-member?
  (lambda (element cf-set-proc)
    ((cf-set-proc 'member?) element)))

;; Generische Prozeduren mit Message-Passing-Style

(define adjoin-set
  (lambda (element set)
    ((set 'adjoin) element)))

(define set-member?
  (lambda (element set)
    ((set 'member?) element)))