Von Fröschen und Tischlampen

Aus ProgrammingWiki

(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 ()))))

Inhaltsverzeichnis 1 Der Lampen-Stream 2 Frosch-Sprünge mit verschiedenen Weiten 3 Unendlich viele Frösche springen über unendlich viele Tischlampen 4 Auswertung

Der Lampen-Stream

Zunächst definieren wir den Stream (abzählbar) unendlich vieler Tischlampen, die alle ausgeschaltet sind.
Jede Lampe ist mit einem Schalter ausgestattet, mit dem die Lampe entsprechend ihres Betriebszustandes entweder ein- oder ausgeschaltet werden kann:

(define lamp-stream (stream-cons 'off lamp-stream)) (define switch (lambda (lamp) (if (eqv? lamp 'off) 'on 'off)))

(show-stream lamp-stream 20)

ausführen

Frosch-Sprünge mit verschiedenen Weiten

Um jede n-te Lampe schalten zu können, erweitern wir die Stream-Sprachelemente mit der Prozedur höherer Ordnung(stream-map-n <n>).
In Analogie zu stream-map bewirkt ein Aufruf von (stream-map-n <n>) die Anwendung einer Prozedur proz auf jedes n-te Element eines Streams stm:

(define stream-map-n (lambda (n) (lambda (proz stm) (letrec ([help-stream (lambda (stm s) (if (= s n) (stream-cons (proz (stream-car stm)) (help-stream (stream-cdr stm) 1)) (stream-cons (stream-car stm) (help-stream (stream-cdr stm) (+ s 1)))))]) (help-stream stm 1)))))

In folgendem Beispiel wird jede dritte Lampe eingeschaltet...

(show-stream ((stream-map-n 3) switch lamp-stream) 20)

ausführen

... bzw. ein- und wieder ausgeschaltet:

(show-stream ((stream-map-n 3) switch ((stream-map-n 3) switch lamp-stream)) 20)

ausführen

Nun können wir Frosch-Sprünge mit aufsteigenden Sprungweiten definieren:

(define jump (lambda (w) (lambda (stm) (stream-cons (switch (stream-car stm)) ((jump (+ 1 w)) ((stream-map-n w) switch (stream-cdr stm)))))))

Unendlich viele Frösche springen über unendlich viele Tischlampen

(define frog-lamp-stream ((jump 1) lamp-stream))

(show-stream frog-lamp-stream 20)

ausführen

Auswertung

Um das Resultat besser verallgemeinern zu können, fassen wir die Nummern der Lampen zusammen, die nach allen Frosch-Sprüngen eingeschaltet sind. In der Vermutung, dass das (abzählbar) unendlich viele Lampen sind, soll dieses Ergebnis wiederum als Stream repräsentiert werden:

(define result-stream (lambda (stm) (letrec ([help-stream (lambda (stm i) (if (eqv? (stream-car stm) 'on) (stream-cons i (help-stream (stream-cdr stm) (+ i 1))) (help-stream (stream-cdr stm) (+ i 1))))]) (help-stream stm 1))))

(show-stream (result-stream frog-lamp-stream) 15)

ausführen

Ergebnis: Offensichtlich sind nach den Frosch-Sprüngen alle Lampen eingeschaltet, deren Nummern Quadratzahlen sind.

Zurück zu Streams.