Grundlagen der funktionsorientierten Programmierung mit SCHEME/Streams

Wiki-Quelltext dieser Seite.

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

<code id="5ba6a7cc69071">
(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>

Streams haben also in Scheme die folgende Struktur:

 stream = (kopfglied . reststream)

Dabei sind:

<table border="1" cellspacing="1" cellpadding="8">
<tr>
<td><tt>kopfglied</tt></td><td>das erste Glied des Streams</td>
</tr>
<tr>
<td><tt>reststream</tt></td><td>der Reststream, dessen Evaluation "aufgeschoben" wird</td> 
</tr>
</table>

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

<code id="4b276fcd45fe4">
(define natstream
  (lambda (n)
    (stream-cons n (natstream (+ n 1)))))

(define natzahlen (natstream 0))
</code> 

<run id="4b276fcd4dcdf">
(show-stream natzahlen 30)
</run>

== Sprachelemente ==

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

<table border="1" cellspacing="1" cellpadding="8">
<tr>
<td>&nbsp;</td><td><b>Syntax</b></td><td><b>Semantik</b></td>
</tr>
<tr>
<td rowspan="2" valign="top"><b>Selektoren</b></td>
<td><tt>stream-car</tt></td><td>gibt das Kopfglied zurück</td>
</tr>
<tr>
<td><tt>stream-cdr</tt></td><td>gibt den Reststream zurück</td>
</tr>
<tr>
<td valign="top"><b>Konstruktor</b></td>
<td><tt>stream-cons</tt></td><td>erzeugt aus Kopfglied und Reststream einen Stream</td>
</tr>
<tr>
<td valign="top"><b>Prädikat</b></td>
<td><tt>stream?</tt></td><td>gibt <tt>#t</tt> zurück, wenn das Argument ein Stream ist, anderenfalls <tt>#f</tt></td>
</tr>
<tr>
<td rowspan="2" valign="top"><b>Operatoren</b></td>
<td><tt>stream-map</tt></td>
<td>wendet eine Prozedur auf die Glieder eines Streams an und gibt das Resultat als Stream zurück</td>
</tr>
<tr>
<td><tt>stream-filter</tt></td>
<td>filtert mit einem Prädikat Glieder eines Streams heraus und gibt diese in einem Stream zurück</td>
</tr>
<tr>
<td valign="top"><b>Ausgabe</b></td>
<td><tt>show-stream</tt></td><td>gibt die Elemente eines Streams in einer beliebigen Anzahl auf dem Bildschirm aus</td>
</tr>
</table>

Die meisten dieser Sprachelemente haben wir oben bereits definiert.<br />
Implementieren Sie die Prozedur <tt>stream-filter</tt>.

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

<code id="4b276fcd47f1c">
(define stream-filter
  (lambda (proz stm)
    ...))
</code>

<check>
(stream-equal? (stream-filter gerade? natzahlen) (stream-map (lambda (n) (* 2 n)) natzahlen) 1000)
</check>

== Aufgaben ==

<ol>
<li>
Gegeben sind die Definitionen:

<code id="4b276fcd48ec0">
(define gerade?
  (lambda (n)
    (= (modulo n 2) 0)))

(define ungerade
  (lambda (n)
    (+ (* 2 n) 1)))
</code>

Definieren Sie mit dem Prädikat <tt>gerade?</tt> den Streams aller geraden Zahlen.

<code id="4e74ca01dc63a">
(define geradzahlen
  ...) 
</code>

<run id="4b276fcd4ec82">
(show-stream geradzahlen 30)
</run>

Implementieren Sie nun den Stream aller ungeraden Zahlen mit der Prozedur <tt>ungerade</tt>.

<code id="4e74ca01dc6cf">
(define ungeradzahlen
  ...)
</code>

<run id="4b276fcd4fc20">
(show-stream ungeradzahlen 30)
</run>
</li>

<li>
Wir kennen bereits einen effizienten Primzahlprüfer:

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

Definieren Sie den Stream unendlich vieler(!) Primzahlen.

<code id="4e74ca01dc757">
(define primzahlen
  ...)
</code>

<run id="4b276fcd50bc6">
(show-stream primzahlen 30)
</run>
</li>
</ol>

== Zum Weiterarbeiten ==

<table>
<tr>
<td>[[Bild:FroschLampe.jpg]]</td>
<td>
=== 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. <br />
Vor der ersten Lampe sitzen (abzählbar) unendlich viele Frösche.<br />
Sie springen nun von Lampenschalter zu Lampenschalter nach folgendem Prinzip:<br />
Der erste Frosch springt auf jeden Schalter. Der zweite Frosch springt auf jeden zweiten Schalter, der dritte auf jeden dritten Schalter usw.<br />
Bei jeder Schalterberührung wird die Lampe entsprechend ihres Zustandes entweder ein- oder ausgeschaltet.<br />
In welchem Zustand befinden sich die Tischlampen, wenn unendlich viele Frösche über unendlich viele Tischlampen gesprungen sind?<br />

Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Von Fröschen und Tischlampen|Problemlösung]].
</td>
</tr>
</table>