Streams

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Potenziell unendliche Mengen 2 Sprachelemente 3 Aufgaben 4 Zum Weiterarbeiten 4.1 Von Fröschen und Tischlampen

Potenziell unendliche Mengen

Mengen, die sich eindeutig auf die Menge der natürlichen Zahlen abbilden lassen, heißen abzählbar oder potenziell unendliche Mengen.
Mit dem Konzept der verzögerten Evaluation wollen wir diese "Unendlichkeit" im Computer repräsentieren.
Wir definieren dazu Streams, d.h. unendliche Datenströme:

(define stream-car car) (define stream-cdr (lambda (stm) (force (cdr stm)))) (define-macro (stream-cons head tail) `(cons ,head (delay ,tail))) (define stream? (lambda (stm) (and (pair? stm) (promise? (cdr stm))))) (define stream-map (lambda (proz stm) (stream-cons (proz (stream-car stm)) (stream-map proz (stream-cdr stm))))) (define show-stream (lambda (stm n) (letrec ([show (lambda (stm n ls) (if (= n 0) (apply display (append ls (list "..."))) (show (stream-cdr stm) (- n 1) (append ls (list (stream-car stm) ", ")))))]) (show stm n ()))))

Streams haben also in Scheme die folgende Struktur:

stream = (kopfglied . reststream)

Dabei sind:

kopfglied	das erste Glied des Streams
reststream	der Reststream, dessen Evaluation "aufgeschoben" wird

Nun können wir unseren ersten Datenstrom implementieren.
Naturgemäß soll das die potenziell unendliche Menge der natürlichen Zahlen sein:

(define natstream (lambda (n) (stream-cons n (natstream (+ n 1))))) (define natzahlen (natstream 0))

(show-stream natzahlen 30)

ausführen

Sprachelemente

Zur Arbeit mit Streams benötigen wir die folgenden Sprachelemente:

	Syntax	Semantik
Selektoren	stream-car	gibt das Kopfglied zurück
	stream-cdr	gibt den Reststream zurück
Konstruktor	stream-cons	erzeugt aus Kopfglied und Reststream einen Stream
Prädikat	stream?	gibt #t zurück, wenn das Argument ein Stream ist, anderenfalls #f
Operatoren	stream-map	wendet eine Prozedur auf die Glieder eines Streams an und gibt das Resultat als Stream zurück
	stream-filter	filtert mit einem Prädikat Glieder eines Streams heraus und gibt diese in einem Stream zurück
Ausgabe	show-stream	gibt die Elemente eines Streams in einer beliebigen Anzahl auf dem Bildschirm aus

Die meisten dieser Sprachelemente haben wir oben bereits definiert.
Implementieren Sie die Prozedur stream-filter.

(define stream-equal? (lambda (stm1 stm2 n) (cond [(= n 0) #t] [(not (equal? (stream-car stm1) (stream-car stm2))) #f] [else (stream-equal? (stream-cdr stm1) (stream-cdr stm2) (- n 1))]))) (define gerade? (lambda (n) (= (modulo n 2) 0)))

(define stream-filter (lambda (proz stm) ...))

Aufgaben

1. Gegeben sind die Definitionen:

   (define gerade? (lambda (n) (= (modulo n 2) 0))) (define ungerade (lambda (n) (+ (* 2 n) 1)))

   Definieren Sie mit dem Prädikat gerade? den Streams aller geraden Zahlen.

   (define geradzahlen ...)

   (show-stream geradzahlen 30)

   ausführen

   Implementieren Sie nun den Stream aller ungeraden Zahlen mit der Prozedur ungerade.

   (define ungeradzahlen ...)

   (show-stream ungeradzahlen 30)

   ausführen

2. Wir kennen bereits einen effizienten Primzahlprüfer:

   (define primzahl? (lambda (n) (letrec ([prim? (lambda (n t) (cond [(< (sqrt n) t) #t] [(= (modulo n t) 0) #f] [else (prim? n (+ t 2))]))]) (cond [(= n 2) #t] [(or (< n 2) (= (modulo n 2) 0)) #f] [else (prim? n 3)]))))

   Definieren Sie den Stream unendlich vieler(!) Primzahlen.

   (define primzahlen ...)

   (show-stream primzahlen 30)

   ausführen

Zum Weiterarbeiten

Von Fröschen und Tischlampen In einer Reihe stehen (abzählbar) unendlich viele Tischlampen. Jede besitzt in ihrer Bodenplatte einen Schalter, der auf "AUS" steht. Vor der ersten Lampe sitzen (abzählbar) unendlich viele Frösche. Sie springen nun von Lampenschalter zu Lampenschalter nach folgendem Prinzip: Der erste Frosch springt auf jeden Schalter. Der zweite Frosch springt auf jeden zweiten Schalter, der dritte auf jeden dritten Schalter usw. Bei jeder Schalterberührung wird die Lampe entsprechend ihres Zustandes entweder ein- oder ausgeschaltet. In welchem Zustand befinden sich die Tischlampen, wenn unendlich viele Frösche über unendlich viele Tischlampen gesprungen sind? Zur Problemlösung.