schnittmenge

Aus ProgrammingWiki

Archivierte Version vom 2012-04-01T15:07:20+00:00. Aktuelle Version

Streams

Wie bereits beim Hilberthotel werden zunächst einige benötigte Grundbefehle für die Arbeit mit Streams definiert:

;; Selektoren
(define stream-car car)
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

;; Konstruktoren
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

;; Praedikat
(define stream?
  (lambda (stm)
    (and (pair? stm)(promise? (cdr stm)))))

;; Operationen mit streams
(define print-stream
  (lambda (stm n)
    (cond
      ((<= n 0) (display "...\n"))
      (else
       (display (stream-car stm))
       (display ", ")
       (print-stream (stream-cdr stm) (- n 1))))))
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

Schnittmenge

(define enthalten?
  (lambda(element liste)
    (cond
      [(not (list? liste)) #f]
      [(null? liste) #f]
      [(= (car liste) element) #t]
      [else (enthalten? element (cdr liste))]
    )
  )
)

(define bilde-sm
  (lambda (f g)
    (letrec(
      (suche-element
        (lambda (f-pool g-pool index)
          (let (
                (f-element (f index))
                (g-element (g index))
            )
            (begin
              (if (enthalten? f-element g-pool)
                  (stream-cons f-element (suche-element f-pool (append g-pool (list g-element)) (+ index 1)))
                  (if (enthalten? g-element (append f-pool (list f-element)))
                    (stream-cons g-element (suche-element (append f-pool (list f-element)) g-pool (+ index 1)))
                    (suche-element (append f-pool (list f-element)) (append g-pool (list g-element)) (+ index 1))
                  )
              )
            )
          )
        )
       ))
      (suche-element '() '() 1)
    )
  )
)

Im Folgenden soll die Schnittmenge der geraden Zahlen und der Quadratzahlen angezeigt werden:

(define f (lambda (x) (* 2 x)))
(define g (lambda (x) (* x x)))
(define sm (bilde-sm f g))
(print-stream sm 10)

Es ergibt sich folgende Aufzählfunktion:

h(n) = 4n^2

schnittmenge

Streams

Schnittmenge

Suche