Grundlagen der funktionsorientierten Programmierung mit SCHEME/Von Fröschen und Tischlampen

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="5ba6aa64adda0" hidden>
(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 ()))))
</code>

[[Datei:FroschLampe.jpg|miniatur|Von Fröschen und Tischlampen]]

== Der Lampen-Stream ==

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

<code id="4b522b2b0bfdc">
(define lamp-stream
  (stream-cons 'off lamp-stream))

(define switch
  (lambda (lamp)
    (if (eqv? lamp 'off)
        'on
        'off)))
</code>

<run id="4b52203279c19">
(show-stream lamp-stream 18)
</run>

== Frosch-Sprünge mit verschiedenen Weiten ==

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

<code id="4b52259a7cc63">
(define stream-map-n
  (lambda (proz stm n)
    (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))))
</code> 

In folgendem Beispiel wird jede dritte Lampe eingeschaltet.
<run id="5be9315261e44">
(show-stream (stream-map-n switch lamp-stream 3) 20)
</run>

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

<code id="56b09139e6d9d">
(define jump
  (lambda (stm w)
    (stream-cons 
       (switch (stream-car stm))
       (jump (stream-map-n switch (stream-cdr stm) w) (+ w 1)))))
</code>

== Unendlich viele Frösche springen über unendlich viele Tischlampen ==

<code id="4b52288be2905">
(define frog-lamp-stream
  (jump lamp-stream 1))
</code>

<run id="4b52259a80ac2">
(show-stream frog-lamp-stream 18)
</run>

== 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:

<code id="4b52261eec295">
(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))))
</code>

<run id="5ba6aa64ade24">
(show-stream (result-stream frog-lamp-stream) 15)
</run>

'''Ergebnis:''' Offensichtlich sind nach den Frosch-Sprüngen alle Lampen eingeschaltet, deren Nummern ''Quadratzahlen'' sind.<br />

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Streams|Streams]].