BuK/IIm11/BuK-Übung03
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
==== Aufgabe 1 <tt>(Felix Nitsche, Stefan Lüttke)</tt> ====
ÜA: Wie viele berechenbare charakteristische Funktionen gibt es?
Hinweis: Potenzmenge unendlicher Mengen
Lösung:
[[Bild:Sistluet_AStern.png]]
Die Wortmenge $A^*$ ist abzählbar unendlich. Für Jede Teilmenge M (entspricht einem Wort) gibt es eine Funktion chi die entweder $true$ oder $false$ zurückgibt.
Von der Wortmenge $A^*$ wird nun die Potenzmenge $P(A^* )$ erzeugt, welche überabzählbar unendlich ist. Für Jedes Element von $P$ kann man nun ebenfalls eine eine Funktion chi erzeugen, was dazu führt das es ebenfalls überabzähbar unendlich viele Funktionen chi gibt, trotzdem nicht jede dieser Funktionen berechenbar ist.
==== Aufgabe 2 <tt>(Jens Heider, Daniel Tasche)</tt> ====
Zeigen Sie, dass die beiden folgenden Mengen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für
die jeweilige charakteristische Funktion (ProgrammingWiki).
'''Beispiel 1:'''
M ist die Menge aller Wörter aus $A^*$, die die Länge 3 besitzen, d.h.:
$A^* = \{a, b\}^* \text{ und } M \subset A^* = \{w \mid w \in A^*\text{ und } |w| = 3\}$
''Lösung:''
Die Mengen sind (absolut) entscheidbar, wenn es eine charakteristische Funktion gibt, die "wahr" zurückgibt, wenn das Element in der Menge enthalten ist und "falsch", wenn es definitiv nicht enthalten ist.
Da es sich um eine endliche Menge handelt, kann eine Iteration über die Elemente der Menge erfolgen, wobei das jeweilige Element mit dem gesuchten verglichen wird. Bei Übereinstimmung wird "wahr" zurückgegeben. Wird die Iteration erfolglos beendet, wird "falsch" zurückgegeben.
$$
\chi_M(w) = \begin{cases}
wahr, & \text{wenn } w \in M;\\
falsch, & \text{sonst}
\end{cases}
$$
<code id="4f781a7f02fb4">
(define M (list "aaa" "aba" "aab" "baa" "bab" "abb" "bba" "bbb"))
(define chi
(lambda (w)
(letrec
((suche
(lambda (menge)
(cond
[(null? menge) #f]
[(string=? (car menge) w) #t]
[else
(suche (cdr menge))
]
)
)
))
(suche M)
)
)
)
</code>
<run id="4f781a7f0309a">
(chi "aab")
</run>
<language>Javascript</language>
<language>Javascript</language>
<language>Javascript</language>
===== Javascript Alternative =====
<code id="58e0c338181ea">
var M = ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb'];
function chi(w) {
var suche = function (menge) {
if (menge.length == 0)
return false;
else if (menge[0] == w)
return true;
else {
menge.shift();
return suche(menge);
}
};
return suche(M.slice(0)); //Gebe Kopie an Funktion
};
</code>
<run id="58e0c33818266">
chi("aaa");
</run>
===== zweite Lösungsmöglichkeit Scheme =====
Eine alternatie Möglichkeit besteht in der Überprüfung, ob das Wort den Regeln entspricht (Wortlänge von 3, Alphabet enthält nur 'a' und 'b'):
<code id="4f7820dd05781">
(define chi2
(lambda (w)
(letrec
((suche
(lambda (liste index)
(cond
[(and (null? liste) (<= index 3)) #f]
[(null? liste) #t]
[(> index 3) #f]
[(not (or (char=? #\a (car liste)) (char=? #\b (car liste)))) #f]
[else
(suche (cdr liste) (+ index 1))
]
)
)
))
(suche (string->list w) 1)
)
)
)
</code>
<run id="4f7820dd059e9">
(chi2 "aaaa")
</run>
'''Beispiel 2''' abzählbar unendliche Menge
$ M $ ist die Menge aller Wörter, die aus beliebeig vielen $ a $'s und $ b $'s bestehen und mit $ a $ beginnen: $ A^* = \{a,b\}^* $ und $ M \subset A^* = \{w = aw' | w' \in A^* \} $ .
'''Lösung'''
Die Menge M ist entscheidbar, da folgende charakteristische Funktion existiert:
$$ \chi_M(w) = \begin{cases}
wahr, & \text{wenn das erste Zeichen von } w \text{ ein '}a\text{' ist und } w \in A^*\text{, mit } A^* = \{a,b\}^*;\\
falsch, & \text{sonst};
\end{cases} $$
Die Funktion liefert wahr, wenn das erste Zeichen des Wortes $w$ ein '$a$' ist und der Rest des Wortes aus dem Alphabet $ A^* $ ist. Falsch, wenn nicht.
<code id="4f78262e3b2bc">
(define b2
(lambda (w)
(let ((l (string->list w)))
(letrec
((helper
(lambda (a)
(if (or (char=? #\a (car a)) (char=? #\b (car a)))
(if (not (null? (cdr a)))
(helper (cdr a))
#t
)
#f
)
)
))
(if (and (not (null? l)) (char=? #\a (car l)))
(helper (cdr l))
#f
)
)
)
)
)
</code>
<run id="4f78262e3b3c4">(b2 "ababbababab")</run>
==== Aufgabe 3 <tt>(Max Wielsch, Raik Bieniek)</tt> ====
ÜA: Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.
aufzählbar: abzählbar + berechenbar
abzählbar: $\exists g$: $\N \mapsto G$, $G$ sei die Menge der geraden Zahlen
$g$: surjektiv
berechenbar: Es gibt einen Algorithmus für $g$
$g(n) = 2n$
<div align="right">$\square$</div>
Algorithmus:
<code id="4f7afc9e7e9b0">(define g
(lambda (n)
(* n 2)
)
)</code>
<run id="4f7afc9e7ea18">
(g 1)
</run>
ÜA: Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.
aufzählbar: abzählbar + berechenbar
abzählbar: $\exists p$: $\N \mapsto P$, $P$ sei die Menge der Primzahlen
$p$: surjektiv
berechenbar: Es gibt einen Algorithmus für $p$
Funktion:
$p(n) = \left\{\begin{array}{cc}
n; wenn\ prime?(n)\\
2; sonst\\
\end{array}\right.
$
Algorithmus:
<code id="4f7b5611d805e">
(define kleinster−teiler
(lambda (n)
;finde a, sodass gilt: a^n mod n = a
(finde−teiler 2 n)
)
)
(define finde−teiler
(lambda (a n)
;teile n durch a, wobei 2 < a < sqrt(n)
(cond ((> (sqrt a) n) n)
((teilt? a n) a)
(else (finde−teiler (+ a 1) n))
)
)
)
(define teilt?
(lambda (a b)
(= (modulo b a) 0 )
)
)
(define primzahl?
(lambda (n)
(= (kleinster−teiler n) n)
)
)
(define n-zu-prim
(lambda (n)
(if (primzahl? n)
n
2
)
)
)
</code>
<run id="4f7b5611d9474">
(n-zu-prim 7)
</run>
<div align="right">$\square$</div>
↦ f ist berechenbar
ÜA: Wir wissen, dass A* eine abzählbar unendliche Menge ist. Zeigen Sie, dass A* auch aufzählbar ist. Hinweis: Hierzu ist es notwendig ein Aufbauschema für A* zu entwerfen und anschließend eine Prozedur dafür zu implementieren.
Gesucht: $f: ℕ ↦ A^*; berechenbar, surjektiv$
Für endliches Alphabet:
Bsp:
[[Bild:Sirabien_A_oben_Stern.png]]
([http://www.inf.hs-zigr.de/~sirabien/A_oben_Stern.svg als SVG])
surjektiv weil jede mögliche Wortlänge vorkommt und jedes mögliche Wort für jede Länge erreicht wird.
<code id="4f7b4499759eb">
(define pow
(lambda (number exp)
(if (= exp 0)
1
(* number (pow number (- exp 1))))))
(define getElement
(lambda (set index)
(if (= index 1)
(car set)
(getElement (cdr set) (- index 1)))))
(define cardinalNumber
(lambda (set)
(if (null? set)
0
(+ 1 (cardinalNumber (cdr set))))))
(define calculateWordSize
(lambda (set index)
(letrec ((calculateWordSizeReal
(lambda (cardinalNumber index sum exp)
(if (>= sum index)
0
(+ 1
(calculateWordSizeReal
cardinalNumber
index
(+ sum (pow cardinalNumber exp))
(+ 1 exp)))))))
(calculateWordSizeReal (cardinalNumber set) index 0 1))))
;Berechnet die Anzahl der Wörter mit Länge <= letterCount
(define numberOfWords
(lambda (cardinalNumber letterCount)
(if (= letterCount 0)
0
(+
(pow cardinalNumber letterCount)
(numberOfWords cardinalNumber (- letterCount 1))))))
(define createWord
(lambda (set wordnumber cardinalNumber lettersRemaining)
(if (= 0 lettersRemaining)
""
(let ((sectionSize (pow cardinalNumber (- lettersRemaining 1))))
(let ((rest (modulo wordnumber sectionSize))
(result (quotient wordnumber sectionSize)))
(if (= 0 rest)
(string-append
(string (getElement set result))
(createWord set sectionSize cardinalNumber (- lettersRemaining 1)))
(string-append
(string (getElement set (+ result 1)))
(createWord set rest cardinalNumber (- lettersRemaining 1)))))))))
(define fCreator
(lambda (set)
(lambda (index)
(if (= index 0)
""
(let((cardinalNumber (cardinalNumber testSet))
(lettersRemaining (calculateWordSize testSet index)))
(createWord testSet (- index (numberOfWords cardinalNumber (- lettersRemaining 1))) cardinalNumber lettersRemaining))))))
</code>
<run id="4f7b449975a61">
(define testSet
'(#\a #\b #\c))
(define f
(fCreator testSet))
(f 30)
</run>
==== Aufgabe 4 <tt>(Ingo Körner, Christof Ochmann, Erik Jähne)</tt> ====
ÜA: Zeigen Sie, dass jede endliche Menge M aufzählbar ist.
''aufzählbar = abzählbar + berechenbar''
1) Jede endliche Menge ist abzählbar (per Definition).
2) Jede endliche Menge ist berechenbar.
Es gibt eine Funktion f, die als Eingabe die natürlichen Zahlen N nimmt und auf jedes Element der endlichen Menge M abbildet. f ist berechenbar, da es eine total berechenbare surjektive Funktion f : N -> M gibt.
Es wird der Reihe nach jedes Element aus N einem Element aus M zugeordnet. Ist f sujektiv, können die restlichen Elemente aus N auf ein beliebiges Element von M abgebildet werden. Somit ist f surjektiv, total und berechenbar.
'''ÜA: Die Menge G der Gitterpunkte (0, 0),(0, 1), ... einer x-y-Ebene ist aufzählbar.'''
[[Bild:Koerner_2D_Ebene.png| miniatur |Übersicht: 2D-Ebene]]
'''1 Geben Sie eine Funktion f an, die $\N_0$ bijektiv auf G abbildet.'''
<code id="4f7b544cf3270">
(define-syntax while
(syntax-rules ()
((while condition body ...)
(let loop ()
(if condition
(begin
body ...
(loop))
)))))
(define decode
(lambda (k)
(define p 1)
(define q k)
(while (<= p q)
(set! q (- q p))
(set! p (+ p 1))
)
(set! p (- p 1))
(list q (- p q))
))
</code>
<run id="4f781a7f0309a">
(decode 17)
</run>
'''2 Definieren Sie eine Ordnungsrelation $p_<$ in G.'''
Aufstellung der Paare durch intuitive Ordnung und Errechnung der Koordinatensumme:
{| border="1" cellpadding="5" cellspacing="0"
|+
! Position || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14 || 15
|-
| Gitterpunkt (x,y) || (0,0)||(0,1)||(1,0)||(0,2)||(1,1)||(2,0)||(0,3)||(1,2)||(2,1)||(3,0)||(0,4)||(1,3)||(2,2)||(3,1)||(4,0)||(0,5)
|-
| x+y || 0 || 1 || 1 || 2 || 2 || 2 || 3 || 3 || 3 || 3 || 4 || 4 || 4 || 4 || 4 || 5
|}
Aus dieser Folge ist ersichtlich, dass sich die Paare zuerst nach der Koordinatensumme (x+y) und anschließend nach der x Koordinate ordnen lassen:
$(G, p_<)$ = {(0,0) < (0,1) < (1,0) < (0,2) < (1,1) < (2,0) < (0,3) < (1,2) < (2,1) < ...}
'''3 Geben Sie eine Funktion k zur Berechnung der Platznummer k(x, y) des betrachteten Gitterpunktes (x, y) an.'''
Aus der obrigen Darstellung ist ersichtlich, dass die Summe aller vorherigen unterschiedlichen Koordinatensummen der ersten Position des Gitterpunktes mit einer neuen Koordinatensumme entsprechen. Der Offset ab dieser Position entspricht dem x Wert. Mathematisch lässt sich so folgende Plazierungsfunktion aufstellen:
:<math>
k(x,y) = \sum_{i=0}^{x+y}i + x
</math>
Mit Hilfe der gaußschen Summenformel lässt sich dieser Ausdruck umformen in die Darstellung:
: <math>k(x,y) = \frac{(x+y)+(x+y+1)}{2} + x.</math>
Diese kann nun in folgendem Programm genutzt werden:
<code id="4f7872cf68601">
(define pair
(lambda (x y)
(+ (/ (* (+ x y) (+ x y 1)) 2) x)
)
)
</code>
<run id="4f7872cf686a7">
(pair 3 2)
</run>
'''4 Geben Sie eine Aufzählprozedur für G an und begründen Sie deren Berechenbarkeit.'''
<code id="58d65d3a3f769">
(define aufzaehl
(lambda (anfang ende)
(if (> anfang ende)
'()
(cons (decode anfang) (aufzaehl (+ anfang 1) ende)
))
)
)
</code>
<run id="58d65d3a3f89d">
(aufzaehl 0 17)
</run>
Wenn zu einer Funktion eine Prozedur angegeben werden kann, dann ist die Funktion auch berechenbar. Um hier die Berechenbarkeit zu begründen, wurde die Prozedur aufzaehl angegeben.
==== Aufgabe 5 <tt>(Tobias Salzmann, Ronald Krause)</tt> ====
[[Bild:Sitosalz_Übersicht_Mengenklassen.png| miniatur |Übersicht: Mengenklassen]]
Eine Menge $M \subseteq A^*$ ist '''semi-entscheidbar''', wenn die partielle (semi-charakteristische) Funktion $\chi'_M : A^* \mapsto \{wahr\} $ mit
$$
\chi'_M(w) =
\begin{cases}
wahr, & \text{wenn } w \in M;\\
\bot, & sonst.
\end{cases}
$$
berechenbar ist.
ÜA: Weisen Sie nach, dass die Menge M aller "Wörter aus {a, b}*, die mit a beginnen, semi-entscheidbar ist.
Wie in der Übersicht zu den Mengenklassen ersichtlich, ist eine Menge auch semi-entscheidbar, wenn Sie entscheidbar ist. <br />
In Aufgabe 2 wurde die Entscheidbarkeit dieser Menge gezeigt, daraus folgt das Sie auch semi-entscheidbar sein muss.
Weiterhin kann auch eine partielle semi-charakteristische Funktion angegeben werden:
<code id="4f7b27dc2b0b9">
(define chi-a
(lambda (w)
(if (char=? (string-ref w 0) #\a)
#t
(chi-a w))))
</code>
<run id="4f7aa7165169c">
(chi-a "abbbbaaabbbb")
</run>
<run id="4f7aa7165170b">
(chi-a "babbbaaabbbb")
</run>
ÜA: Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese
Aussage.
Man kann eine Prozedur haelt? angeben, welche angewand auf eine Prozedur f true zurück gibt falls f terminiert und ansosnten ewig weiter läuft, für diesen Fall also nicht definiert ist. <br />
Das Halteproblem ist somit semi-entscheidbar, weil eine partielle Funktion hierfür angegeben werden kann.
<code id="4f7b282a6e321">
(define (haelt? f n)
(f n) #t)
(define eternity
(lambda (n)
(eternity n)))
(define (square n)
(* n n))
</code>
<run id="4f7b198fc5f50">
(haelt? square 4)
</run>
<run id="4f7b198fc5fa7">
(haelt? eternity 4)
</run>
<code id="4f7b5611d8442" hidden>
(define stream-car car)
(define stream-cdr
(lambda (s)
(force (cdr s))))
(define-syntax stream-cons
(syntax-rules ()
((_ head tail) (cons head (delay tail)))))
(define stream-map
(lambda (f s)
(stream-cons
(f (stream-car s))
(stream-map f (stream-cdr s)))))
(define nat-stream
(lambda (start)
(stream-cons start (nat-stream (+ start 1)))))
(define stream->list
(lambda (str n)
(if (<= n 0)
'()
(cons
(stream-car str)
(stream->list (stream-cdr str) (- n 1))))))
(define print-stream
(lambda (str items)
(if (<= items 0)
(begin
(display "...")(newline))
(begin
(write (stream-car str))
(display ", ")
(print-stream (stream-cdr str)(- items 1))))))
(define natzahlen (nat-stream 0))
(define fib_menge print-stream) ; angepasster Prozedurnamen
(define generiere_fib_menge
(lambda (f)
(stream-map number->string (stream-map f natzahlen))))
</code>
ÜA: Geben Sie fur die Menge FIBS der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit.
Weisen Sie nach, dass FIBS eine semi-entscheidbare Menge ist.
Zeigen Sie, dass FIBS sogar entscheidbar ist.
Laut der Definition aus der Vorlesung Berechenbarkeitstheorie und Kreativität ist eine Menge aufzählbar, wenn es eine totale berechenbare Funktion '''f''' gibt, welche die Menge $\N$ auf eine Menge '''M''' abbildet.
In diesem Beispiel handelt es sich bei der Menge '''M''' um die Fibonacci-Zahlwörter. Die Aufzählprozedur '''f''' lautet wie folgt:
$$f(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in \text{ M};\\
0, & sonst.
\end{cases}$$
Damit die Funktion '''f''' eine surjektiv Abbildung der natürlichen Zahlen auf die Menge der Fibonacci-Zahlwörter und berechenbar ist, wird die Aufzählfunktion '''g''' benötigt.
$$g(n) = \begin{cases}
0, & \text{wenn } n=0;\\
1, & \text{wenn } n=1;\\
(n-1) + (n-2), & sonst.
\end{cases}$$
Scheme-Prozedur für die Aufzählfunktion '''g''':
<code id="4f7a9eb44d422">
(define g
(lambda (n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (g(- n 1)) (g(- n 2)))))))
</code>
<run id="4f7a9ddac7082">
(g 10)
</run>
Erzeugen der Menge M an Fibonacci-Zahlwörter:
<code id="4f7b5611d87a6">
(define fibonacci_zahlen (generiere_fib_menge g))
</code>
<run id="4f7b5611d953d">
(fib_menge fibonacci_zahlen 5)
</run>
Um nachweisen zu können, dass die Funktion '''f''' semi-entscheidbar ist, muss es wie oben definiert folgende Funktion geben
$$\chi'_{M}(w) = \begin{cases}
wahr, & \text{wenn } w \in \text{ M};\\
\bot, & sonst.
\end{cases}$$
welche berechenbar ist. Mit Hilfe der Prozedur '''semi_chi_fib''' ist dies nachweisbar.
<code id="4f7b5611d88df">
(define semi_chi_fib
(lambda (m w)
(letrec
(( helfer
( lambda ( stm )
(if (string=? w (stream-car stm ))
#t
(helfer (stream-cdr stm ))))))
(helfer m ))))
</code>
<run id="4f7b5611d9602">
(semi_chi_fib fibonacci_zahlen "5")
</run>
<run id="4f7b5611d96df">
(semi_chi_fib fibonacci_zahlen "-1") ;user break
</run>
ÜA: Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 |n \in \N\}.$
Analog zur vorhergehenden Übungsaufgabe lässt sich folgende Aufzählprozedur '''f''' aufstellen:
$$f(n) = \begin{cases}
g(n), & \text{wenn } g(n) \in \text{ M};\\
1, & sonst.
\end{cases}$$
Die Auzählfunktion g2, welche die Menge der quadtratischen Zahlen zurückgibt ist folgende:
<code id="4f7b5611d8aeb">
(define g2
(lambda (n)
(* n n)))
</code>
Erzeugen der Menge M an Quadratzahlen:
<code id="4f7b5611d8c28" hidden>
(define quad_menge print-stream)
(define generiere_quad_menge
(lambda (f)
(stream-map f natzahlen)))
</code>
<code id="4f7b5611d8eef">
(define quad_zahlen (generiere_quad_menge g2))
</code>
<run id="4f7b5611d97aa">
(quad_menge quad_zahlen 9)
</run>
Nachweis das die Funktion '''f''' semi-entscheidbar ist: Prozedur '''semi_chi_quad'''
<code id="4f7b5611d9036" hidden>
(define generiere_quad_menge_wortmenge
(lambda (f)
(stream-map number->string (stream-map f natzahlen))))
(define quad_zahlen_2 (generiere_quad_menge_wortmenge g2))
</code>
<code id="4f7b5611d9153">
(define semi_chi_quad
(lambda (m w)
(letrec
(( helfer
( lambda ( stm )
(if (string=? w (stream-car stm ))
#t
(helfer (stream-cdr stm ))))))
(helfer m ))))
</code>
<run id="4f7b5611d9877">
(semi_chi_quad quad_zahlen_2 "9")
</run>
<run id="4f7b5611d9942">
(semi_chi_quad quad_zahlen_2 "3"); user break
</run>
Nachweis das die Funktion ebenfalls entscheidbar ist:
<code id="4f7b5611d924b" hidden>
(define f_help
(lambda (n ls)
(cond
((null? ls) #f)
((= n (car ls)) #t)
(else (f_help n (cdr ls))))))
</code>
<code id="4f7b5611d932d">
(define f
(lambda (n)
(if (f_help (g2 n) (stream->list quad_zahlen (+ n 1)))
(g2 n)
1)))
</code>
<run id="4f7b5611d9a07">
(f 10)
</run>
<run id="4f7b5611d9b0a">
(f 10.1)
</run>
==== Aufgabe 6 <tt>(Robert Rosenberger, Stefan Scheumann)</tt> ====
ÜA: Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki die 30 ersten Elemente der Vereinigungsmenge (in aufsteigender Sortierung) auszugeben.
Gegeben:
$ A = {0,1,2,3,4,5,6,7,8,9} $
$ A^{*} = { \epsilon,0,1,2,...,10,11,12,...,100,101,...} $
Menge der geraden Zahlwörter $ M_{1}$ mit:
$ M_{1} \subseteq A^{*}$
$ f: \N \rightarrow M_{1} \text{ mit } f(x) = 2x $
Menge der ungeraden Zahlwörter $ M_{1}$ mit:
$ M_{2} \subseteq A^{*}$
$ g: \N \rightarrow M_{2} \text{ mit } g(x) = 1+2x $
Vereinigung:
$ M_{1} \cup M_{2} \subseteq A^{*}$
$h: \N \rightarrow M_{1} \cup M_{2}$
$$
h(i) = \begin{cases}
f(\frac{i}{2}), & \text{wenn } 2|i;\\
g(\frac{i - 1}{2}), & \text{sonst}.
\end{cases}$$
<code id="4f7830628f1bf" hidden>
(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)))))
(define stream-item
(lambda (str k)
(if (= k 0)
(stream-car str)
(stream-item (stream-cdr str) (- k 1)))))
(define print-stream
(lambda (stm n)
(cond
((<= n 0) (display "...\n"))
(else
(display (number->string(stream-car stm)))
(display ", ")
(print-stream (stream-cdr stm) (- n 1))))))
</code>
<code id="4f7830628f229">
(define nat-stream-maker
(lambda ()
(letrec ((n 0)
(nat-stream-maker-helper
(lambda (start)
(stream-cons start (nat-stream-maker-helper (+ start 1))))))
(nat-stream-maker-helper 0))))
(define stream-map
(lambda (stm proc)
(stream-cons
(proc (stream-car stm))
(stream-map (stream-cdr stm) proc))))
(define even-odd-merging-stream-maker
(lambda (oddstm evenstm)
(letrec ((n 0)
(even-odd-merging-stream-maker-helper
(lambda (n oddstm evenstm)
(if (even? n)
(stream-cons (stream-car evenstm) (even-odd-merging-stream-maker-helper (+ n 1) oddstm (stream-cdr evenstm)))
(stream-cons (stream-car oddstm) (even-odd-merging-stream-maker-helper (+ n 1) (stream-cdr oddstm) evenstm))))))
(even-odd-merging-stream-maker-helper n oddstm evenstm))))
(define natstream (nat-stream-maker ))
(define oddstream (stream-map natstream(lambda (x) (+ 1 (* 2 x)))))
(define evenstream (stream-map natstream (lambda (x)(* 2 x))))
(define mergestream (even-odd-merging-stream-maker oddstream evenstream))
</code>
<run id="4f7830628f2a5">
(display "ungerade Zahlen\n")
(print-stream oddstream 30)
(display "ungerade Zahlen\n")
(print-stream evenstream 30)
(display "Vereinigung gerade und ungerade Zahlen\n")
(print-stream mergestream 30)
</run>